For using the igraph C library
igraph_is_separator — Would removing this set of vertices disconnect the graph?igraph_is_minimal_separator — Decides whether a set of vertices is a minimal separator.igraph_all_minimal_st_separators — List all vertex sets that are minimal (s,t) separators for some s and t.igraph_minimum_size_separators — Find all minimum size separating vertex sets.igraph_even_tarjan_reduction — Even-Tarjan reduction of a graph.
igraph_error_t igraph_is_separator(const igraph_t *graph,
const igraph_vs_t candidate,
igraph_bool_t *res);
Arguments:
|
The input graph. It may be directed, but edge directions are ignored. |
|
The candidate separator. It must not contain all vertices. |
|
Pointer to a Boolean variable, the result is stored here. |
Returns:
Error code. |
Time complexity: O(|V|+|E|), linear in the number vertices and edges.
Example 23.1. File examples/simple/igraph_is_separator.c
#include <igraph.h> #include <stdio.h> #define FAIL(msg, error) do { printf(msg "\n") ; return error; } while (0) int main(void) { igraph_t graph; igraph_vector_int_t sep; igraph_bool_t result; /* Simple star graph, remove the center */ igraph_star(&graph, 10, IGRAPH_STAR_UNDIRECTED, 0); igraph_is_separator(&graph, igraph_vss_1(0), &result); if (!result) { FAIL("Center of star graph failed.", 1); } /* Same graph, but another vertex */ igraph_is_separator(&graph, igraph_vss_1(6), &result); if (result) { FAIL("Non-center of star graph failed.", 2); } /* Same graph, all vertices but the center */ igraph_is_separator(&graph, igraph_vss_range(1, 10), &result); if (result) { FAIL("All non-central vertices of star graph failed.", 5); } igraph_destroy(&graph); /* Same graph, all vertices */ igraph_is_separator(&graph, igraph_vss_range(0, 10), &result); if (result) { FAIL("All vertices of star graph failed.", 6); } igraph_destroy(&graph); /* Karate club */ igraph_famous(&graph, "zachary"); igraph_vector_int_init(&sep, 0); igraph_vector_int_push_back(&sep, 32); igraph_vector_int_push_back(&sep, 33); igraph_is_separator(&graph, igraph_vss_vector(&sep), &result); if (!result) { FAIL("Karate network (32,33) failed", 3); } igraph_vector_int_resize(&sep, 5); VECTOR(sep)[0] = 8; VECTOR(sep)[1] = 9; VECTOR(sep)[2] = 19; VECTOR(sep)[3] = 30; VECTOR(sep)[4] = 31; igraph_is_separator(&graph, igraph_vss_vector(&sep), &result); if (result) { FAIL("Karate network (8,9,19,30,31) failed", 4); } igraph_destroy(&graph); igraph_vector_int_destroy(&sep); return 0; }
igraph_error_t igraph_is_minimal_separator(const igraph_t *graph,
const igraph_vs_t candidate,
igraph_bool_t *res);
A set of vertices is a minimal separator, if the removal of the vertices disconnects the graph, and this is not true for any subset of the set.
This implementation first checks that the given
candidate is a separator, by calling igraph_is_separator(). If it is a separator, then it checks that
each subset of size n-1, where n is the size of the candidate, is
not a separator.
Arguments:
|
The input graph. It may be directed, but edge directions are ignored. |
|
The candidate minimal separators. |
|
Pointer to a boolean variable, the result is stored here. |
Returns:
Error code. |
Time complexity: O(n(|V|+|E|)), |V| is the number of vertices, |E| is the number of edges, n is the number vertices in the candidate separator.
Example 23.2. File examples/simple/igraph_is_minimal_separator.c
#include <igraph.h> #include <stdio.h> #define FAIL(msg, error) do { printf(msg "\n") ; return error; } while (0) int main(void) { igraph_t graph; igraph_vector_int_t sep; igraph_bool_t result; /* Simple star graph, remove the center */ igraph_star(&graph, 10, IGRAPH_STAR_UNDIRECTED, 0); igraph_is_minimal_separator(&graph, igraph_vss_1(0), &result); if (!result) { FAIL("Center of star graph failed.", 1); } /* Same graph, but another vertex */ igraph_is_minimal_separator(&graph, igraph_vss_1(6), &result); if (result) { FAIL("Non-center of star graph failed.", 2); } igraph_destroy(&graph); /* Karate club */ igraph_famous(&graph, "zachary"); igraph_vector_int_init(&sep, 0); igraph_vector_int_push_back(&sep, 32); igraph_vector_int_push_back(&sep, 33); igraph_is_minimal_separator(&graph, igraph_vss_vector(&sep), &result); if (!result) { FAIL("Karate network (32,33) failed", 3); } igraph_vector_int_resize(&sep, 5); VECTOR(sep)[0] = 8; VECTOR(sep)[1] = 9; VECTOR(sep)[2] = 19; VECTOR(sep)[3] = 30; VECTOR(sep)[4] = 31; igraph_is_minimal_separator(&graph, igraph_vss_vector(&sep), &result); if (result) { FAIL("Karate network (8,9,19,30,31) failed", 4); } igraph_destroy(&graph); igraph_vector_int_destroy(&sep); return 0; }
igraph_error_t igraph_all_minimal_st_separators(
const igraph_t *graph, igraph_vector_int_list_t *separators
);
This function lists all vertex sets that are minimal (s,t) separators for some (s,t) vertex pair.
Note that some vertex sets returned by this function may not be minimal
with respect to disconnecting the graph (or increasing the number of
connected components). Take for example the 5-vertex graph with edges
0-1-2-3-4-1. This function returns the vertex sets
{1}, {2,4} and {1,3}.
Notice that {1,3} is not minimal with respect to disconnecting
the graph, as {1} would be sufficient for that. However, it is
minimal with respect to separating vertices 2 and 4.
See more about the implemented algorithm in Anne Berry, Jean-Paul Bordat and Olivier Cogis: Generating All the Minimal Separators of a Graph, In: Peter Widmayer, Gabriele Neyer and Stephan Eidenbenz (editors): Graph-theoretic concepts in computer science, 1665, 167--172, 1999. Springer. https://doi.org/10.1007/3-540-46784-X_17
Arguments:
|
The input graph. It may be directed, but edge directions are ignored. |
|
An initialized pointer vector, the separators
are stored here. It is a list of pointers to igraph_vector_int_t
objects. Each vector will contain the ids of the vertices in
the separator.
To free all memory allocated for |
Returns:
Error code. |
See also:
Time complexity: O(n|V|^3), |V| is the number of vertices, n is the number of separators.
Example 23.3. File examples/simple/igraph_minimal_separators.c
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t graph; igraph_vector_int_list_t separators; igraph_integer_t i, n; igraph_famous(&graph, "zachary"); igraph_vector_int_list_init(&separators, 0); igraph_all_minimal_st_separators(&graph, &separators); n = igraph_vector_int_list_size(&separators); for (i = 0; i < n; i++) { igraph_bool_t res; igraph_vector_int_t *sep = igraph_vector_int_list_get_ptr(&separators, i); igraph_is_separator(&graph, igraph_vss_vector(sep), &res); if (!res) { printf("Vertex set %" IGRAPH_PRId " is not a separator!\n", i); igraph_vector_int_print(sep); return 1; } } igraph_destroy(&graph); igraph_vector_int_list_destroy(&separators); return 0; }
igraph_error_t igraph_minimum_size_separators(
const igraph_t *graph, igraph_vector_int_list_t *separators
);
This function lists all separator vertex sets of minimum size. A vertex set is a separator if its removal disconnects the graph.
The implementation is based on the following paper: Arkady Kanevsky: Finding all minimum-size separating vertex sets in a graph, Networks 23, 533--541, 1993.
Arguments:
|
The input graph, which must be undirected. |
|
An initialized list of integer vectors, the separators are stored here. It is a list of pointers to igraph_vector_int_t objects. Each vector will contain the IDs of the vertices in the separator. The separators are returned in an arbitrary order. |
Returns:
Error code. |
Time complexity: TODO.
Example 23.4. File examples/simple/igraph_minimum_size_separators.c
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_list_t sep; igraph_small(&g, 7, IGRAPH_UNDIRECTED, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, -1); igraph_vector_int_list_init(&sep, 0); igraph_minimum_size_separators(&g, &sep); for (igraph_integer_t i = 0; i < igraph_vector_int_list_size(&sep); i++) { igraph_vector_int_t* v = igraph_vector_int_list_get_ptr(&sep, i); igraph_vector_int_print(v); } igraph_vector_int_list_destroy(&sep); igraph_destroy(&g); return 0; }
igraph_error_t igraph_even_tarjan_reduction(const igraph_t *graph, igraph_t *graphbar,
igraph_vector_t *capacity);
A digraph is created with twice as many vertices and edges. For each
original vertex i, two vertices i' = i and
i'' = i' + n are created,
with a directed edge from i' to i''.
For each original directed edge from i to j, two new edges are created,
from i' to j'' and from i''
to j'.
This reduction is used in the paper (observation 2): Arkady Kanevsky: Finding all minimum-size separating vertex sets in a graph, Networks 23, 533--541, 1993.
The original paper where this reduction was conceived is Shimon Even and R. Endre Tarjan: Network Flow and Testing Graph Connectivity, SIAM J. Comput., 4(4), 507–518. https://doi.org/10.1137/0204043
Arguments:
|
A graph. Although directness is not checked, this function is commonly used only on directed graphs. |
|
Pointer to a new directed graph that will contain the reduction, with twice as many vertices and edges. |
|
Pointer to an initialized vector or a null pointer. If not a null pointer, then it will be filled the capacity from the reduction: the first |E| elements are 1, the remaining |E| are equal to |V| (which is used to indicate infinity). |
Returns:
Error code. |
Time complexity: O(|E|+|V|).
Example 23.5. File examples/simple/even_tarjan.c
#include <igraph.h> #include <limits.h> int main(void) { igraph_t g, gbar; igraph_integer_t k1, k2 = INT_MAX; igraph_real_t tmpk; igraph_integer_t i, j, n; igraph_maxflow_stats_t stats; /* --------------------------------------------------- */ igraph_famous(&g, "meredith"); igraph_even_tarjan_reduction(&g, &gbar, /*capacity=*/ 0); igraph_vertex_connectivity(&g, &k1, /* checks= */ 0); n = igraph_vcount(&g); for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { igraph_bool_t conn; igraph_are_connected(&g, i, j, &conn); if (conn) { continue; } igraph_maxflow_value(&gbar, &tmpk, /* source= */ i + n, /* target= */ j, /* capacity= */ 0, &stats); if (tmpk < k2) { k2 = tmpk; } } } igraph_destroy(&gbar); igraph_destroy(&g); if (k1 != k2) { printf("k1 = %" IGRAPH_PRId " while k2 = %" IGRAPH_PRId "\n", k1, k2); return 1; } return 0; }
| ← Chapter 22. Maximum flows, minimum cuts and related measures | Chapter 24. Detecting community structure → |