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);
A vertex setS is a separator if there are verticesu andvin the graph such that all paths betweenu andv pass throughsome vertices inS.
Arguments:
| The input graph. It may be directed, but edge directions are ignored. |
| The candidate separator. |
| 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. Fileexamples/simple/igraph_is_separator.c
#include <igraph.h>#include <stdio.h>#defineFAIL(msg, error)do {printf(msg "\n") ;return error; }while (0)intmain(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); }/* 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 vertex separatorS is minimal is no proper subset ofSis also 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(|V|+|E|), linear in the number vertices and edges.
Example 23.2. Fileexamples/simple/igraph_is_minimal_separator.c
#include <igraph.h>#include <stdio.h>#defineFAIL(msg, error)do {printf(msg "\n") ;return error; }while (0)intmain(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 minimalwith respect to disconnecting the graph (or increasing the number ofconnected components). Take for example the 5-vertex graph with edges0-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 disconnectingthe graph, as{1} would be sufficient for that. However, it isminimal with respect to separating vertices2 and4.
See more about the implemented algorithm inAnne Berry, Jean-Paul Bordat and Olivier Cogis: Generating All theMinimal Separators of a Graph, In: Peter Widmayer, Gabriele Neyerand Stephan Eidenbenz (editors): Graph-theoretic concepts incomputer 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. |
| Pointer to a list of integer vectors, the separators will be stored here. |
Returns:
Error code. |
See also:
Time complexity: O(n|V|^3), |V| is the number of vertices, n is thenumber of separators.
Example 23.3. Fileexamples/simple/igraph_minimal_separators.c
#include <igraph.h>#include <stdio.h>intmain(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 ina graph, Networks 23, 533--541, 1993.https://doi.org/10.1002/net.3230230604
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. Fileexamples/simple/igraph_minimum_size_separators.c
#include <igraph.h>intmain(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 eachoriginal vertexi, two verticesi' = i andi'' = i' + n are created,with a directed edge fromi' toi''.For each original directed edge fromi toj, two new edges are created,fromi' toj'' and fromi''toj'.
This reduction is used in the paper (observation 2):Arkady Kanevsky: Finding all minimum-size separating vertex sets ina graph, Networks 23, 533--541, 1993.
The original paper where this reduction was conceived isShimon Even and R. Endre Tarjan: Network Flow and Testing GraphConnectivity, 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. Fileexamples/simple/even_tarjan.c
#include <igraph.h>#include <limits.h>intmain(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=*/ NULL);igraph_vertex_connectivity(&g, &k1,/* checks= */ false); n =igraph_vcount(&g);for (i = 0; i < n; i++) {for (j = i + 1; j < n; j++) { igraph_bool_t conn;igraph_are_adjacent(&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 → |