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
int 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
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #include <stdio.h> #define FAIL(msg, error) do { printf(msg "\n") ; return error; } while (0) int main() { igraph_t graph; igraph_vector_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_seq(1, 9), &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_seq(0, 9), &result); if (result) { FAIL("All vertices of star graph failed.", 6); } igraph_destroy(&graph); /* Karate club */ igraph_famous(&graph, "zachary"); igraph_vector_init(&sep, 0); igraph_vector_push_back(&sep, 32); igraph_vector_push_back(&sep, 33); igraph_is_separator(&graph, igraph_vss_vector(&sep), &result); if (!result) { FAIL("Karate network (32,33) failed", 3); } igraph_vector_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_destroy(&sep); return 0; }
int 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. |
|
Pointer to a vector of long integers, the candidate minimal separator. |
|
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
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #include <stdio.h> #define FAIL(msg, error) do { printf(msg "\n") ; return error; } while (0) int main() { igraph_t graph; igraph_vector_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_init(&sep, 0); igraph_vector_push_back(&sep, 32); igraph_vector_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_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_destroy(&sep); return 0; }
int igraph_all_minimal_st_separators(const igraph_t *graph,
igraph_vector_ptr_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_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
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #include <stdio.h> int main() { igraph_t graph; igraph_vector_ptr_t separators; long int i, n; igraph_famous(&graph, "zachary"); igraph_vector_ptr_init(&separators, 0); igraph_all_minimal_st_separators(&graph, &separators); n = igraph_vector_ptr_size(&separators); for (i = 0; i < n; i++) { igraph_bool_t res; igraph_vector_t *sep = VECTOR(separators)[i]; igraph_is_separator(&graph, igraph_vss_vector(sep), &res); if (!res) { printf("Vertex set %li is not a separator!\n", i); igraph_vector_print(sep); return 1; } } igraph_destroy(&graph); for (i = 0; i < n; i++) { igraph_vector_t *v = VECTOR(separators)[i]; igraph_vector_destroy(v); IGRAPH_FREE(v); } igraph_vector_ptr_destroy(&separators); return 0; }
int igraph_minimum_size_separators(const igraph_t *graph,
igraph_vector_ptr_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 pointer vector, the separators
are stored here. It is a list of pointers to igraph_vector_t
objects. Each vector will contain the ids of the vertices in
the separator.
To free all memory allocated for |
Returns:
Error code. |
Time complexity: TODO.
Example 23.4. File examples/simple/igraph_minimum_size_separators.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard st, Cambridge MA, 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> int print_and_destroy(igraph_vector_ptr_t *ptr) { long int i, n = igraph_vector_ptr_size(ptr); for (i = 0; i < n; i++) { igraph_vector_t *v = VECTOR(*ptr)[i]; igraph_vector_print(v); igraph_vector_destroy(v); igraph_free(v); } igraph_vector_ptr_destroy(ptr); return 0; } int main() { igraph_t g, g2; igraph_vector_ptr_t sep; igraph_vs_t vs; igraph_small(&g, 7, IGRAPH_UNDIRECTED, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, -1); igraph_vector_ptr_init(&sep, 0); igraph_minimum_size_separators(&g, &sep); print_and_destroy(&sep); igraph_destroy(&g); /* ----------------------------------------------------------- */ igraph_small(&g, 5, IGRAPH_UNDIRECTED, 0, 3, 1, 3, 2, 3, 0, 4, 1, 4, 2, 4, -1); igraph_vector_ptr_init(&sep, 0); igraph_minimum_size_separators(&g, &sep); print_and_destroy(&sep); igraph_destroy(&g); /* ----------------------------------------------------------- */ igraph_small(&g, 5, IGRAPH_UNDIRECTED, 2, 0, 3, 0, 4, 0, 2, 1, 3, 1, 4, 1, -1); igraph_vector_ptr_init(&sep, 0); igraph_minimum_size_separators(&g, &sep); print_and_destroy(&sep); igraph_destroy(&g); /* ----------------------------------------------------------- */ igraph_small(&g, 10, IGRAPH_UNDIRECTED, 0, 2, 0, 3, 1, 2, 1, 3, 5, 2, 5, 3, 6, 2, 6, 3, 7, 2, 7, 3, 8, 2, 8, 3, 9, 2, 9, 3, 2, 4, 4, 3, -1); igraph_vector_ptr_init(&sep, 0); igraph_minimum_size_separators(&g, &sep); print_and_destroy(&sep); igraph_destroy(&g); /* ----------------------------------------------------------- */ igraph_full(&g, 4, IGRAPH_UNDIRECTED, /*loops=*/ 0); igraph_vector_ptr_init(&sep, 0); igraph_minimum_size_separators(&g, &sep); print_and_destroy(&sep); igraph_destroy(&g); /* ----------------------------------------------------------- */ igraph_small(&g, 23, IGRAPH_UNDIRECTED, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 1, 2, 1, 3, 1, 4, 1, 6, 2, 3, 2, 5, 2, 6, 3, 4, 3, 5, 3, 6, 4, 5, 4, 6, 4, 20, 5, 6, 6, 7, 6, 10, 6, 13, 6, 18, 7, 8, 7, 10, 7, 13, 8, 9, 9, 11, 9, 12, 10, 11, 10, 13, 11, 15, 12, 15, 13, 14, 14, 15, 16, 17, 16, 18, 16, 19, 17, 19, 17, 20, 18, 19, 18, 21, 18, 22, 19, 20, 20, 21, 20, 22, 21, 22, -1); igraph_vector_ptr_init(&sep, 0); igraph_minimum_size_separators(&g, &sep); printf("Orig:\n"); print_and_destroy(&sep); igraph_vector_ptr_init(&sep, 0); igraph_vs_vector_small(&vs, 0, 1, 2, 3, 4, 5, 6, 16, 17, 18, 19, 20, 21, 22, -1); igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO); igraph_minimum_size_separators(&g2, &sep); printf("1-7,17-23:\n"); print_and_destroy(&sep); igraph_vs_destroy(&vs); igraph_destroy(&g2); igraph_vector_ptr_init(&sep, 0); igraph_vs_vector_small(&vs, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, -1); igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO); igraph_minimum_size_separators(&g2, &sep); printf("7-16:\n"); print_and_destroy(&sep); igraph_vs_destroy(&vs); igraph_destroy(&g2); igraph_vector_ptr_init(&sep, 0); igraph_vs_vector_small(&vs, 16, 17, 18, 19, 20, 21, 22, -1); igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO); igraph_minimum_size_separators(&g2, &sep); printf("17-23:\n"); print_and_destroy(&sep); igraph_vs_destroy(&vs); igraph_destroy(&g2); igraph_vector_ptr_init(&sep, 0); igraph_vs_vector_small(&vs, 6, 7, 10, 13, -1); igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO); igraph_minimum_size_separators(&g2, &sep); printf("7,8,11,14:\n"); print_and_destroy(&sep); igraph_vs_destroy(&vs); igraph_destroy(&g2); igraph_vector_ptr_init(&sep, 0); igraph_vs_vector_small(&vs, 0, 1, 2, 3, 4, 5, 6, -1); igraph_induced_subgraph(&g, &g2, vs, IGRAPH_SUBGRAPH_AUTO); igraph_minimum_size_separators(&g2, &sep); printf("1-7:\n"); print_and_destroy(&sep); igraph_vs_destroy(&vs); igraph_destroy(&g2); igraph_destroy(&g); return 0; }
int 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.
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 mean infinity). |
Returns:
Error code. |
Time complexity: O(|E|+|V|).
Example 23.5. File examples/simple/even_tarjan.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2010-2012 Gabor Csardi <csardi.gabor@gmail.com> 334 Harvard street, Cambridge, MA 02139 USA This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ #include <igraph.h> #include <limits.h> int main() { igraph_t g, gbar; igraph_integer_t k1, k2 = (igraph_integer_t) INT_MAX; igraph_real_t tmpk; long int 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 = %ld while k2 = %ld\n", (long int) k1, (long int) k2); return 1; } return 0; }
| ← Chapter 22. Maximum flows, minimum cuts and related measures | Chapter 24. Detecting community structure → |