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_CHECK(igraph_add_edge(&graph_copy, (igraph_integer_t) ii,
(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!
