how to customize existing igraph functions via adding additional parameters

,

Hi. I am wondering how to customize existing igraph functions by adding additional parameters. To be specific, I would like to customize "`min_separators` (igraph R manual pages)" into the one that accepts “k_value (”`k_separators`")," which represents the size of all vertex sets whose removal separates the graph into more components, rather than finding all vertex sets of the “minimum” size that the existing “`min_separators`” did.

I have tried to do this by slightly changing the C source function of “`igraph_minimum_size_separators`” into “`igraph_k_value_size_separators`” as follows:

``````int igraph_k_value_size_separators(const igraph_t *graph, igraph_vector_ptr_t *separators, long int k_value) {

long int no_of_nodes = igraph_vcount(graph);
long int no_of_edges = igraph_ecount(graph);
igraph_integer_t conn; long int k;
igraph_vector_t X;
long int i, j;
igraph_bool_t issepX;
igraph_t Gbar;
igraph_vector_t phi;
igraph_t graph_copy;
igraph_vector_t capacity;
igraph_maxflow_stats_t stats;

if (igraph_is_directed(graph)) {
IGRAPH_ERROR("Minimum size separators currently only works on undirected graphs",
IGRAPH_EINVAL);
}

igraph_vector_ptr_clear(separators);
IGRAPH_FINALLY(igraph_i_separators_free, separators);

/* ---------------------------------------------------------------- */
/* 1 Find the vertex connectivity of 'graph' */
IGRAPH_CHECK(igraph_vertex_connectivity(graph, &conn,
/* checks= */ 1)); k = conn;

/* Special cases for low connectivity, two exits here! */
if (k_value == 0) {
/* Nothing to do */
IGRAPH_FINALLY_CLEAN(1);    /* separators */
return 0;
} else if (k_value == 1) {
igraph_vector_t ap;
long int i, n;
IGRAPH_VECTOR_INIT_FINALLY(&ap, 0);
IGRAPH_CHECK(igraph_articulation_points(graph, &ap));
n = igraph_vector_size(&ap);
IGRAPH_CHECK(igraph_vector_ptr_resize(separators, n));
igraph_vector_ptr_null(separators);
for (i = 0; i < n; i++) {
igraph_vector_t *v = IGRAPH_CALLOC(1, igraph_vector_t);
if (!v) {
IGRAPH_ERROR("Minimum size separators failed", IGRAPH_ENOMEM);
}
IGRAPH_VECTOR_INIT_FINALLY(v, 1);
VECTOR(*v)[0] = VECTOR(ap)[i];
VECTOR(*separators)[i] = v;
IGRAPH_FINALLY_CLEAN(1);
}
igraph_vector_destroy(&ap);
IGRAPH_FINALLY_CLEAN(2);    /* +1 for separators */
return 0;
} else if (k_value == no_of_nodes - 1) {
long int k;
IGRAPH_CHECK(igraph_vector_ptr_resize(separators, no_of_nodes));
igraph_vector_ptr_null(separators);
for (i = 0; i < no_of_nodes; i++) {
igraph_vector_t *v = IGRAPH_CALLOC(1, igraph_vector_t);
if (!v) {
IGRAPH_ERROR("Cannot list minimum size separators", IGRAPH_ENOMEM);
}
IGRAPH_VECTOR_INIT_FINALLY(v, no_of_nodes - 1);
for (j = 0, k = 0; j < no_of_nodes; j++) {
if (j != i) {
VECTOR(*v)[k++] = j;
}
}
VECTOR(*separators)[i] = v;
IGRAPH_FINALLY_CLEAN(1);
}
IGRAPH_FINALLY_CLEAN(1);    /* separators */
return 0;
}

/* Work on a copy of 'graph' */
IGRAPH_CHECK(igraph_copy(&graph_copy, graph));
IGRAPH_FINALLY(igraph_destroy, &graph_copy);
IGRAPH_CHECK(igraph_simplify(&graph_copy, /* multiple */ 1, /* loops */ 1, NULL));

/* ---------------------------------------------------------------- */
/* 2 Find k vertices with the largest degrees (x1;..,xk). Check
if these k vertices form a separating k-set of G */
IGRAPH_CHECK(igraph_vector_init(&X, k_value));
IGRAPH_FINALLY(igraph_vector_destroy, &X);
IGRAPH_CHECK(igraph_i_minimum_size_separators_topkdeg(&graph_copy, &X, k_value));
IGRAPH_CHECK(igraph_is_separator(&graph_copy, igraph_vss_vector(&X),
&issepX));
if (issepX) {
igraph_vector_t *v = IGRAPH_CALLOC(1, igraph_vector_t);
if (!v) {
IGRAPH_ERROR("Cannot find minimal size separators", IGRAPH_ENOMEM);
}
IGRAPH_VECTOR_INIT_FINALLY(v, k_value);
for (i = 0; i < k_value; i++) {
VECTOR(*v)[i] = VECTOR(X)[i];
}
IGRAPH_CHECK(igraph_vector_ptr_push_back(separators, v));
IGRAPH_FINALLY_CLEAN(1);
}

/* Create Gbar, the Even-Tarjan reduction of graph */
IGRAPH_VECTOR_INIT_FINALLY(&capacity, 0);
IGRAPH_CHECK(igraph_even_tarjan_reduction(&graph_copy, &Gbar, &capacity));
IGRAPH_FINALLY(igraph_destroy, &Gbar);

IGRAPH_VECTOR_INIT_FINALLY(&phi, no_of_edges);

/* ---------------------------------------------------------------- */
/* 3 If v[j] != x[i] and v[j] is not adjacent to x[i] then */
for (i = 0; i < k_value; i++) {

IGRAPH_ALLOW_INTERRUPTION();

for (j = 0; j < no_of_nodes; j++) {
long int ii = (long int) VECTOR(X)[i];
igraph_real_t phivalue;
igraph_bool_t conn;

if (ii == j) {
continue;    /* the same vertex */
}
igraph_are_connected(&graph_copy, (igraph_integer_t) ii,
(igraph_integer_t) j, &conn);
if (conn) {
continue;    /* they are connected */
}

/* --------------------------------------------------------------- */
/* 4 Compute a maximum flow phi in Gbar from x[i] to v[j].
If |phi|=k, then */
IGRAPH_CHECK(igraph_maxflow(&Gbar, &phivalue, &phi, /*cut=*/ 0,
/*partition=*/ 0, /*partition2=*/ 0,
/* source= */
(igraph_integer_t) (ii + no_of_nodes),
/* target= */ (igraph_integer_t) j,
&capacity, &stats));

if (phivalue == k_value) {

/* ------------------------------------------------------------- */
/* 5-6-7. Find all k-sets separating x[i] and v[j]. */
igraph_vector_ptr_t stcuts;
IGRAPH_CHECK(igraph_vector_ptr_init(&stcuts, 0));
IGRAPH_FINALLY(igraph_i_separators_stcuts_free, &stcuts);
IGRAPH_CHECK(igraph_all_st_mincuts(&Gbar, /*value=*/ 0,
/*cuts=*/ &stcuts,
/*partition1s=*/ 0,
/*source=*/ (igraph_integer_t)
(ii + no_of_nodes),
/*target=*/ (igraph_integer_t) j,
/*capacity=*/ &capacity));

IGRAPH_CHECK(igraph_i_minimum_size_separators_append(separators,
&stcuts));
igraph_vector_ptr_destroy(&stcuts);
IGRAPH_FINALLY_CLEAN(1);

} /* if phivalue == k */

/* --------------------------------------------------------------- */
/* 8 Add edge (x[i],v[j]) to G. */
(igraph_integer_t) j));
IGRAPH_CHECK(igraph_add_edge(&Gbar, (igraph_integer_t) (ii + no_of_nodes),
(igraph_integer_t) j));
IGRAPH_CHECK(igraph_add_edge(&Gbar, (igraph_integer_t) (j + no_of_nodes),
(igraph_integer_t) ii));
IGRAPH_CHECK(igraph_vector_push_back(&capacity, no_of_nodes));
IGRAPH_CHECK(igraph_vector_push_back(&capacity, no_of_nodes));

} /* for j<no_of_nodes */
} /* for i<k */

igraph_vector_destroy(&phi);
igraph_destroy(&Gbar);
igraph_vector_destroy(&capacity);
igraph_vector_destroy(&X);
igraph_destroy(&graph_copy);
IGRAPH_FINALLY_CLEAN(6);  /* +1 for separators */

return 0;
}
``````

I tested this C source function in C environment and produced the correct results. But I would like to use this function in R environment. Do you have any ideas on transporting this C source function into igraph R? Thanks in advance!

Can you please clarify the mathematical problem you are looking to solve, just to make sure that we are on the same page?

Are you looking for all vertex sets of size k whose removal disconnects the graph? If yes, are you looking to enumerate all such sets?

Note that if you have a separator of size l < k, it can be trivially made into a size-k separator by adding k-l arbitrary vertices to it. Thus listing all size-k separators does not seem like a very useful thing to do to me. Are you perhaps looking for all minimal size-k separators? A separator set is called “minimal” if all vertices in the set must be removed to disconnected the graph; leaving in even one would fail to disconnect it. igraph already has a function to find all minimal separators: `igraph_all_minimal_st_separators()`. The corresponding R function is (IMO confusingly) called `min_st_separators()`.

In summary:

• `min_st_separators()` returns all minimal separating vertex sets.
• `min_separators()` returns all minimum separating vertex sets, i.e. the smallest size sets from the result of `min_st_separators()`
1 Like

Regarding integrating the function into R: I have little experience with this personally, so someone else will respond when they have time. Generally, the new function needs to be added to `interfaces/functions.def`, so that a wrapper can be generated for it. There are additional complications such as the fact that the R interface relies on a specific (and rather old) version (= git commit) of the C library.

1 Like

Yes. I am looking for all vertex sets of size k whose removal disconnects the graph. And yes, you are correct - I am looking for `min_st_separators` with an additional parameter k as `all_node_cuts` function in Python’s networkx (networkx.algorithms.connectivity.kcutsets.all_node_cuts — NetworkX 2.6.2 documentation). Is it easily possible to modify existing `min_st_separators` to include the k value as an additional parameter? Thank you so much!

There seems to be a misunderstanding here. `all_node_cuts` in networkx does exactly the same thing as `min_separators` (not `min_st_separators`) in R/igraph.

The `k` parameter of `all_node_cuts` does not control what the function does. It is simply a tool for efficiency. If you already know the vertex connectivity of the graph, you can communicate this to the function, so it would not have to recompute it.

It is still not clear to me what you are looking for. Are you looking for all k-separators? Are you looking for minimal k-separators only? Or something else?

2 Likes

All I want to obtain is very simple as follows:

``````import pandas as pd
import os
import networkx as nx

df = pd.DataFrame()
file_name = os.path.join("F:/practice/k_components", "cornwell_burchard_2019.txt")
data = pd.read_csv(file_name, sep=" ", names = ['target', 'source'])
df = df.append(data, ignore_index=True)
df = df + 1

df_edgelist = df.copy()
df_edgelist = df_edgelist[['target', 'source']]

G = nx.Graph()
G.add_edges_from([tuple(x) for x in df_edgelist.values])
G = G.to_undirected()

cutsets_1 = list(nx.all_node_cuts(G, 1))
cutsets_2 = list(nx.all_node_cuts(G, 2))
cutsets_3 = list(nx.all_node_cuts(G, 3))

print(cutsets_1)
print(cutsets_2)
print(cutsets_3)

# [{10}]
# [{10, 6}, {4, 6}, {4, 7}, {11, 4}, {11, 12}, {11, 6}, {4, 5}, {6, 7}, {10, 11}, {10, 7}]
# [{10, 6, 7}, {1, 2, 3}]

``````

The Python code above illustrates what I want to get from `min_separators` with k value in R environment. As shown above, I implemented `all_node_cuts` using Python’s networkx module, and depending on the k value, it produces different results.

With igraphR 's `min_st_separators`, I could produce all of the minimal k-separators as follows:

``````library(igraph)

graph <- graph + 1

graph <- graph_from_edgelist(graph, directed = FALSE)

cutsets <- min_st_separators(graph)

# > cutsets
[[1]]
+ 3/15 vertices, from 8c73875:
[1]  8  9 10

[[2]]
+ 1/15 vertex, from 8c73875:
[1] 10

[[3]]
+ 2/15 vertices, from 8c73875:
[1] 11 12

[[4]]
+ 2/15 vertices, from 8c73875:
[1] 10 11

[[5]]
+ 4/15 vertices, from 8c73875:
[1] 10 13 14 15

[[6]]
+ 4/15 vertices, from 8c73875:
[1] 11 13 14 15

[[7]]
+ 3/15 vertices, from 8c73875:
[1] 1 2 3

[[8]]
+ 2/15 vertices, from 8c73875:
[1] 4 6

[[9]]
+ 2/15 vertices, from 8c73875:
[1] 4 7

[[10]]
+ 2/15 vertices, from 8c73875:
[1] 4 5

[[11]]
+ 2/15 vertices, from 8c73875:
[1] 6 7

[[12]]
+ 2/15 vertices, from 8c73875:
[1]  4 11

[[13]]
+ 2/15 vertices, from 8c73875:
[1]  6 11

[[14]]
+ 2/15 vertices, from 8c73875:
[1]  7 10

[[15]]
+ 4/15 vertices, from 8c73875:
[1]  4 13 14 15

cutsets[which(unlist(lapply(cutsets, function(x) length(x))) == 2)]

# > cutsets[which(unlist(lapply(cutsets, function(x) length(x))) == 2)]
# [[1]]
# + 2/15 vertices, from 8c73875:
#   [1] 11 12
#
# [[2]]
# + 2/15 vertices, from 8c73875:
#   [1] 10 11
#
# [[3]]
# + 2/15 vertices, from 8c73875:
#   [1] 4 6
#
# [[4]]
# + 2/15 vertices, from 8c73875:
#   [1] 4 7
#
# [[5]]
# + 2/15 vertices, from 8c73875:
#   [1] 4 5
#
# [[6]]
# + 2/15 vertices, from 8c73875:
#   [1] 6 7
#
# [[7]]
# + 2/15 vertices, from 8c73875:
#   [1]  4 11
#
# [[8]]
# + 2/15 vertices, from 8c73875:
#   [1]  6 11
#
# [[9]]
# + 2/15 vertices, from 8c73875:
#   [1]  7 10
``````

But the very things that I want to get are the list of separators with k length (in this example, k = 2) as `cutsets[which(unlist(lapply(cutsets, function(x) length(x))) == 2)]` produces.

I am not quite sure why the above results between what networkx produces and what igraphR produces are slightly different, but again I would like to get minimal-k-separators with k value as an additional parameter. Thank you and please let me know if you have any further parts that I clarify more.

(I attached the example file below)
cornwell_burchard_2019.txt (121 Bytes)

First, I need to make a correction to what I said about the `min_separators()` and the `min_st_separators()` functions in R/igraph. The accurate description is that they return a vertex set whose removal disconnects some (s,t) vertex pair. This is subtly different from saying that it “disconnects the graph” when it comes to the interpretation of minimal sets.

Let me rehash what the difference between minimum and minimal sets are in this context. A separator is called minimum size (or simply minimum) if there is no smaller size separator. It is called minimal if excluding any vertex from it makes it no longer a separator.

Now, taking your graph as an example,

notice that the only minimum separator is \{10\}. Its size is 1, the smallest possible.

An example of a minimal separator is \{4, 11\}. Removing these vertices disconnects the graph. Removing only 4 or only 11 does not, which make \{4,11\} a minimal (though not minimum size) separator set.

A more subtle example is \{10, 11\}. Clearly, removing only \{10\} is sufficient for disconnecting the graph. Thus for simply disconnecting the graph, the set \{10,11\} is not minimal. However, there exists an (s,t) pair which can only be disconnected from each other if we remove both 10 and 11. An example is the pair (14,12). Removing 10 alone will not disconnect them. `min_st_separators()` returns separators which are minimal in this latter sense, i.e. for disconnecting some (s,t) pair.

Here’s the list of all minimal (s,t)-separators as returned by `min_st_separators`:

``````{{10},
{4, 5}, {4, 6}, {4, 7}, {4, 11}, {6, 7}, {6, 11}, {7, 10}, {10, 11}, {11, 12},
{1, 2, 3}, {8, 9, 10},
{4, 13, 14, 15}, {10, 13, 14, 15}, {11, 13, 14, 15}}
``````

The following sets are not minimal for disconnecting the graph, but they are minimal for disconnecting some (s,t) pair:

``````{{7, 10}, {10, 11},
{8, 9, 10},
{10, 13, 14, 15}}
``````

The first two are minimal for disconnecting e.g. 4 from 6. The third is needed to disconnect e.g. 1 from 2. And the last one for (6,7).

Still with me? Let me move on to responding to your last comment.

1 Like

I would not call this “very simple”. You are misusing the `all_node_cuts()` function. The networkx documentation is quite clear that the 2nd argument must be the vertex connectivity of the graph. You are passing in arbitrary values which are different from the actual vertex connectivity. Then all bets are off about what the function will return. In my view, this is basically a GIGO situation.

Can you explain what you are trying to do in plain but mathematically accurate language, without any reference to code?

Nevertheless, let us see what `all_node_cuts(G, 2)` returns for your graph, even knowing that its vertex connectivity is not 2. The result will be

``````[{6, 10},
{4, 6},
{4, 7},
{4, 11},
{11, 12},
{6, 11},
{4, 5},
{6, 7},
{10, 11},
{7, 10}]
``````

This is not a very consistent result. Notice the inclusion of `{6, 10}`, which is not a minimal separator in any sense (either for disconnecting the graph, or for disconnecting some (s,t) pair).

Do you perhaps want all separators of size 2, whether minimal or not? Then many others should be included as well, for example `{10, 3}`.

This is because you were misusing `all_node_cuts()`, passing in invalid input. Unsurprisingly, the output is invalid as well.

This can be obtained with `min_st_separators()`, and filtering the result, as you have done above.

At this moment, it is not clear to me if performance could be improved by restricting to size-k sets in the core implementation. Can you explain why you were seeking to change the implementation? Were you looking to improve performance?

1 Like

Thank you so much for making clear the issues that I raised. I could not understand 100% of your comments, but I think I could understand to some extent what your specifically means across two comments.

Why I am seeking to change the `min_separators()` by including an additional k value parameter is because I am now trying to write the `cohesive_blocks()` algorithm in bipartite networks (a related paper: https://www.tandfonline.com/doi/pdf/10.1080/0022250X.2019.1606806?casa_token=VjJlKb0-lOwAAAAA:J-b3pfkFxEhwE2cgIIr5AkN9B3Zo2fUPsz6NqbchugZo0YRAfKamtExCIC0Sk1gKM9BYdlU0wA).

In their paper, the authors suggest two ways to find k-component in bipartite networks (i.e. one-sided and two-sided), and stipulate how to enumerate all of the structurally cohesive groups in two-mode networks as follows (p.9 for two-sided):

1. Identify the one-sided structural cohesion, k, of the input graph.
2. Identify “all the k-cutsets” at the current level of connectivity.
3. Generate new graph component based on the removal of these cutsets.
4. If the graph is neither complete nor trivial, return to 1 else end.

To me, the above procedure is relatively straightforward and easy to implement except 2: based on what I have tried to implement the above algorithm (it was a long time ago so I might be wrong), sometimes I specifically need to know all the cutsets with specific k value rather than minimum size cutsets that `min_separators()` generates.

Do you have any good ideas on how to implement those two-mode cohesive block algorithms? If there are short and efficient alternative ways to write the codes for them, it would be better. Thanks!