igraph_maxflow — Maximum network flow between a pair of verticesigraph_maxflow_value — Maximum flow in a network with the push/relabel algorithmigraph_dominator_tree — Calculates the dominator tree of a flowgraphigraph_maxflow_stats_t — A simple data type to return some statistics from the
int igraph_maxflow(const igraph_t *graph, igraph_real_t *value,
igraph_vector_t *flow, igraph_vector_t *cut,
igraph_vector_t *partition, igraph_vector_t *partition2,
igraph_integer_t source, igraph_integer_t target,
const igraph_vector_t *capacity,
igraph_maxflow_stats_t *stats);
This function implements the Goldberg-Tarjan algorithm for calculating value of the maximum flow in a directed or undirected graph. The algorithm was given in Andrew V. Goldberg, Robert E. Tarjan: A New Approach to the Maximum-Flow Problem, Journal of the ACM, 35(4), 921-940, 1988.
The input of the function is a graph, a vector of real numbers giving the capacity of the edges and two vertices of the graph, the source and the target. A flow is a function assigning positive real numbers to the edges and satisfying two requirements: (1) the flow value is less than the capacity of the edge and (2) at each vertex except the source and the target, the incoming flow (i.e. the sum of the flow on the incoming edges) is the same as the outgoing flow (i.e. the sum of the flow on the outgoing edges). The value of the flow is the incoming flow at the target vertex. The maximum flow is the flow with the maximum value.
Arguments:
|
The input graph, either directed or undirected. |
|
Pointer to a real number, the value of the maximum will be placed here, unless it is a null pointer. |
|
If not a null pointer, then it must be a pointer to an
initialized vector. The vector will be resized, and the flow
on each edge will be placed in it, in the order of the edge
ids. For undirected graphs this argument is bit trickier,
since for these the flow direction is not predetermined by
the edge direction. For these graphs the elements of the
|
|
A null pointer or a pointer to an initialized vector. If not a null pointer, then the minimum cut corresponding to the maximum flow is stored here, i.e. all edge ids that are part of the minimum cut are stored in the vector. |
|
A null pointer or a pointer to an initialized vector. If not a null pointer, then the first partition of the minimum cut that corresponds to the maximum flow will be placed here. The first partition is always the one that contains the source vertex. |
|
A null pointer or a pointer to an initialized vector. If not a null pointer, then the second partition of the minimum cut that corresponds to the maximum flow will be placed here. The second partition is always the one that contains the target vertex. |
|
The id of the source vertex. |
|
The id of the target vertex. |
|
Vector containing the capacity of the edges. If NULL, then every edge is considered to have capacity 1.0. |
|
Counts of the number of different operations preformed by the algorithm are stored here. |
Returns:
Error code. |
Time complexity: O(|V|^3). In practice it is much faster, but i
cannot prove a better lower bound for the data structure i've
used. In fact, this implementation runs much faster than the
hi_pr implementation discussed in
B. V. Cherkassky and A. V. Goldberg: On implementing the
push-relabel method for the maximum flow problem, (Algorithmica,
19:390--410, 1997) on all the graph classes i've tried.
See also:
|
Example 22.1. File examples/simple/flow.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-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> int main() { igraph_t g; igraph_real_t flow; igraph_vector_t capacity; igraph_integer_t source, target; FILE *infile; igraph_maxflow_stats_t stats; igraph_vector_init(&capacity, 0); /***************/ infile = fopen("ak-4102.max", "r"); igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, IGRAPH_DIRECTED); fclose(infile); igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); if (flow != 8207) { return 1; } igraph_destroy(&g); /***************/ /* /\***************\/ */ /* infile=fopen("ak-8198.max", "r"); */ /* igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, */ /* IGRAPH_DIRECTED); */ /* fclose(infile); */ /* t=timer(); */ /* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */ /* t=timer()-t; */ /* printf("8198: %g (time %.10f)\n", flow, t); */ /* igraph_destroy(&g); */ /* /\***************\/ */ /* /\***************\/ */ /* infile=fopen("ak-16390.max", "r"); */ /* igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, */ /* IGRAPH_DIRECTED); */ /* fclose(infile); */ /* t=timer(); */ /* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */ /* t=timer()-t; */ /* printf("16390: %g (time %.10f)\n", flow, t); */ /* igraph_destroy(&g); */ /* /\***************\/ */ /* /\***************\/ */ /* infile=fopen("ak-32774.max", "r"); */ /* igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, */ /* IGRAPH_DIRECTED); */ /* fclose(infile); */ /* t=timer(); */ /* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */ /* t=timer()-t; */ /* printf("32774: %g (time %.10f)\n", flow, t); */ /* igraph_destroy(&g); */ /* /\***************\/ */ /* /\***************\/ */ /* infile=fopen("ak-65542.max", "r"); */ /* igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, */ /* IGRAPH_DIRECTED); */ /* fclose(infile); */ /* t=timer(); */ /* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */ /* t=timer()-t; */ /* printf("65542: %g (time %.10f)\n", flow, t); */ /* igraph_destroy(&g); */ /* /\***************\/ */ igraph_vector_destroy(&capacity); return 0; }
Example 22.2. File examples/simple/flow2.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2006-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> int check_flow(int errorinc, const igraph_t *graph, igraph_real_t flow_value, const igraph_vector_t *flow, const igraph_vector_t *cut, const igraph_vector_t *partition, const igraph_vector_t *partition2, long int source, long int target, const igraph_vector_t *capacity, igraph_bool_t print) { long int i, n = igraph_vcount(graph), m = igraph_ecount(graph); long int nc = igraph_vector_size(cut); igraph_vector_t inedges, outedges; igraph_bool_t directed = igraph_is_directed(graph); igraph_real_t cutsize; igraph_t graph_copy; igraph_matrix_t sp; if (print) { printf("flow value: %g\n", (double) flow_value); printf("flow: "); igraph_vector_print(flow); printf("first partition: "); igraph_vector_print(partition); printf("second partition: "); igraph_vector_print(partition2); printf("edges in the cut: "); for (i = 0; i < nc; i++) { long int edge = VECTOR(*cut)[i]; long int from = IGRAPH_FROM(graph, edge); long int to = IGRAPH_TO (graph, edge); if (!directed && from > to) { igraph_integer_t tmp = from; from = to; to = tmp; } printf("%li-%li (%g), ", from, to, VECTOR(*capacity)[edge]); } printf("\n"); } fflush(stdout); /* Always less than the capacity */ for (i = 0; i < m; i++) { if (VECTOR(*flow)[i] > VECTOR(*capacity)[i]) { return errorinc + 3; } } /* What comes in goes out, but only in directed graphs, there is no in and out in undirected ones... */ if (igraph_is_directed(graph)) { igraph_vector_init(&inedges, 0); igraph_vector_init(&outedges, 0); for (i = 0; i < n; i++) { long int n1, n2, j; igraph_real_t in_flow = 0.0, out_flow = 0.0; igraph_incident(graph, &inedges, i, IGRAPH_IN); igraph_incident(graph, &outedges, i, IGRAPH_OUT); n1 = igraph_vector_size(&inedges); n2 = igraph_vector_size(&outedges); for (j = 0; j < n1; j++) { long int e = VECTOR(inedges)[j]; in_flow += VECTOR(*flow)[e]; } for (j = 0; j < n2; j++) { long int e = VECTOR(outedges)[j]; out_flow += VECTOR(*flow)[e]; } if (i == source) { if (in_flow > 0) { return errorinc + 4; } if (out_flow != flow_value) { return errorinc + 5; } } else if (i == target) { if (out_flow > 0) { return errorinc + 6; } if (in_flow != flow_value) { return errorinc + 7; } } else { if (in_flow != out_flow) { return errorinc + 8; } } } igraph_vector_destroy(&inedges); igraph_vector_destroy(&outedges); } /* Check the minimum cut size*/ for (i = 0, cutsize = 0.0; i < nc; i++) { long int edge = VECTOR(*cut)[i]; cutsize += VECTOR(*capacity)[edge]; } if (fabs(cutsize - flow_value) > 1e-14) { return errorinc + 9; } /* Check that the cut indeed cuts */ igraph_copy(&graph_copy, graph); igraph_delete_edges(&graph_copy, igraph_ess_vector(cut)); igraph_matrix_init(&sp, 1, 1); igraph_shortest_paths(&graph_copy, &sp, /*from=*/ igraph_vss_1(source), /*to=*/ igraph_vss_1(target), IGRAPH_OUT); if (MATRIX(sp, 0, 0) != IGRAPH_INFINITY) { return errorinc + 10; } igraph_matrix_destroy(&sp); igraph_destroy(&graph_copy); return 0; } int main() { igraph_t g; igraph_real_t flow_value; igraph_vector_t cut; igraph_vector_t capacity; igraph_vector_t partition, partition2; igraph_vector_t flow; long int i, n; igraph_integer_t source, target; FILE *infile; igraph_real_t flow_value2 = 0.0; int check; igraph_maxflow_stats_t stats; igraph_vector_init(&capacity, 0); /***************/ infile = fopen("ak-4102.max", "r"); igraph_read_graph_dimacs(&g, infile, 0, 0, &source, &target, &capacity, IGRAPH_DIRECTED); fclose(infile); igraph_vector_init(&cut, 0); igraph_vector_init(&partition, 0); igraph_vector_init(&partition2, 0); igraph_vector_init(&flow, 0); igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2, source, target, &capacity, &stats); if (flow_value != 8207) { return 1; } n = igraph_vector_size(&cut); for (i = 0; i < n; i++) { long int e = VECTOR(cut)[i]; flow_value2 += VECTOR(capacity)[e]; } if (flow_value != flow_value2) { return 2; } /* Check the flow */ if ( (check = check_flow(0, &g, flow_value, &flow, &cut, &partition, &partition2, source, target, &capacity, /*print=*/ 0))) { return check; } igraph_destroy(&g); igraph_vector_destroy(&capacity); igraph_vector_destroy(&cut); igraph_vector_destroy(&partition); igraph_vector_destroy(&partition2); igraph_vector_destroy(&flow); /* ------------------------------------- */ igraph_small(&g, 4, IGRAPH_UNDIRECTED, 0, 1, 0, 2, 1, 2, 1, 3, 2, 3, -1); igraph_vector_init_int_end(&capacity, -1, 4, 2, 10, 2, 2, -1); igraph_vector_init(&cut, 0); igraph_vector_init(&partition, 0); igraph_vector_init(&partition2, 0); igraph_vector_init(&flow, 0); igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2, /*source=*/ 0, /*target=*/ 3, &capacity, &stats); if ( (check = check_flow(20, &g, flow_value, &flow, &cut, &partition, &partition2, 0, 3, &capacity, /*print=*/ 1))) { return check; } igraph_vector_destroy(&cut); igraph_vector_destroy(&partition2); igraph_vector_destroy(&partition); igraph_vector_destroy(&capacity); igraph_vector_destroy(&flow); igraph_destroy(&g); /* ------------------------------------- */ igraph_small(&g, 6, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 0, 5, 5, 4, 4, 3, 3, 0, -1); igraph_vector_init_int_end(&capacity, -1, 3, 1, 2, 10, 1, 3, 2, -1); igraph_vector_init(&cut, 0); igraph_vector_init(&partition, 0); igraph_vector_init(&partition2, 0); igraph_vector_init(&flow, 0); igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2, /*source=*/ 0, /*target=*/ 2, &capacity, &stats); if ( (check = check_flow(40, &g, flow_value, &flow, &cut, &partition, &partition2, 0, 2, &capacity, /*print=*/ 1))) { return check; } igraph_vector_destroy(&cut); igraph_vector_destroy(&partition2); igraph_vector_destroy(&partition); igraph_vector_destroy(&capacity); igraph_vector_destroy(&flow); igraph_destroy(&g); return 0; }
int igraph_maxflow_value(const igraph_t *graph, igraph_real_t *value,
igraph_integer_t source, igraph_integer_t target,
const igraph_vector_t *capacity,
igraph_maxflow_stats_t *stats);
This function implements the Goldberg-Tarjan algorithm for calculating value of the maximum flow in a directed or undirected graph. The algorithm was given in Andrew V. Goldberg, Robert E. Tarjan: A New Approach to the Maximum-Flow Problem, Journal of the ACM, 35(4), 921-940, 1988.
The input of the function is a graph, a vector of real numbers giving the capacity of the edges and two vertices of the graph, the source and the target. A flow is a function assigning positive real numbers to the edges and satisfying two requirements: (1) the flow value is less than the capacity of the edge and (2) at each vertex except the source and the target, the incoming flow (i.e. the sum of the flow on the incoming edges) is the same as the outgoing flow (i.e. the sum of the flow on the outgoing edges). The value of the flow is the incoming flow at the target vertex. The maximum flow is the flow with the maximum value.
According to a theorem by Ford and Fulkerson
(L. R. Ford Jr. and D. R. Fulkerson. Maximal flow through a
network. Canadian J. Math., 8:399-404, 1956.) the maximum flow
between two vertices is the same as the
minimum cut between them (also called the minimum s-t cut). So igraph_st_mincut_value() gives the same result in all cases as igraph_maxflow_value().
Note that the value of the maximum flow is the same as the minimum cut in the graph.
Arguments:
|
The input graph, either directed or undirected. |
|
Pointer to a real number, the result will be placed here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
|
Vector containing the capacity of the edges. If NULL, then every edge is considered to have capacity 1.0. |
|
Counts of the number of different operations preformed by the algorithm are stored here. |
Returns:
Error code. |
Time complexity: O(|V|^3).
See also:
|
int igraph_dominator_tree(const igraph_t *graph,
igraph_integer_t root,
igraph_vector_t *dom,
igraph_t *domtree,
igraph_vector_t *leftout,
igraph_neimode_t mode);
A flowgraph is a directed graph with a distinguished start (or root) vertex r, such that for any vertex v, there is a path from r to v. A vertex v dominates another vertex w (not equal to v), if every path from r to w contains v. Vertex v is the immediate dominator or w, v=idom(w), if v dominates w and every other dominator of w dominates v. The edges {(idom(w), w)| w is not r} form a directed tree, rooted at r, called the dominator tree of the graph. Vertex v dominates vertex w if and only if v is an ancestor of w in the dominator tree.
This function implements the Lengauer-Tarjan algorithm to construct the dominator tree of a directed graph. For details please see Thomas Lengauer, Robert Endre Tarjan: A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS) I/1, 121--141, 1979.
Arguments:
|
A directed graph. If it is not a flowgraph, and it
contains some vertices not reachable from the root vertex,
then these vertices will be collected in the |
|
The id of the root (or source) vertex, this will be the root of the tree. |
|
Pointer to an initialized vector or a null pointer. If not a null pointer, then the immediate dominator of each vertex will be stored here. For vertices that are not reachable from the root, NaN is stored here. For the root vertex itself, -1 is added. |
|
Pointer to an uninitialized igraph_t, or NULL. If not a null pointer, then the dominator tree is returned here. The graph contains the vertices that are unreachable from the root (if any), these will be isolates. |
|
Pointer to an initialized vector object, or NULL. If not NULL, then the ids of the vertices that are unreachable from the root vertex (and thus not part of the dominator tree) are stored here. |
|
Constant, must be |
Returns:
Error code. |
Time complexity: very close to O(|E|+|V|), linear in the number of edges and vertices. More precisely, it is O(|V|+|E|alpha(|E|,|V|)), where alpha(|E|,|V|) is a functional inverse of Ackermann's function.
Example 22.3. File examples/simple/dominator_tree.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 <stdio.h> int main() { igraph_t g, domtree; igraph_vector_t dom, leftout; igraph_vector_init(&dom, 0); igraph_small(&g, 13, IGRAPH_DIRECTED, 0, 1, 0, 7, 0, 10, 1, 2, 1, 5, 2, 3, 3, 4, 4, 3, 4, 0, 5, 3, 5, 6, 6, 3, 7, 8, 7, 10, 7, 11, 8, 9, 9, 4, 9, 8, 10, 11, 11, 12, 12, 9, -1); /* Check NULL vector arguments */ igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ 0, /*leftout=*/ 0, /*mode=*/ IGRAPH_OUT); /* Proper calculation */ igraph_dominator_tree(&g, /*root=*/ 0, &dom, /*domtree=*/ 0, /*leftout=*/ 0, /*mode=*/ IGRAPH_OUT); igraph_vector_print(&dom); /* Tree calculation */ igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ &domtree, /*leftout=*/ 0, /*mode=*/ IGRAPH_OUT); igraph_write_graph_edgelist(&domtree, stdout); igraph_vector_destroy(&dom); igraph_destroy(&domtree); igraph_destroy(&g); /* -------------------------------------------------------------------*/ igraph_vector_init(&dom, 0); igraph_small(&g, 13, IGRAPH_DIRECTED, 1, 0, 2, 0, 3, 0, 4, 1, 1, 2, 4, 2, 5, 2, 6, 3, 7, 3, 12, 4, 8, 5, 9, 6, 9, 7, 10, 7, 5, 8, 11, 8, 11, 9, 9, 10, 9, 11, 0, 11, 8, 12, -1); /* Check NULL vector arguments */ igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ 0, /*leftout=*/ 0, /*mode=*/ IGRAPH_IN); /* Proper calculation */ igraph_dominator_tree(&g, /*root=*/ 0, &dom, /*domtree=*/ 0, /*leftout=*/ 0, /*mode=*/ IGRAPH_IN); igraph_vector_print(&dom); /* Tree calculation */ igraph_dominator_tree(&g, /*root=*/ 0, /*dom=*/ 0, /*domtree=*/ &domtree, /*leftout=*/ 0, /*mode=*/ IGRAPH_IN); igraph_write_graph_edgelist(&domtree, stdout); igraph_vector_destroy(&dom); igraph_destroy(&domtree); igraph_destroy(&g); /* -------------------------------------------------------------------*/ igraph_vector_init(&dom, 0); igraph_vector_init(&leftout, 0); /* Check a graph with more components */ igraph_small(&g, 20, IGRAPH_DIRECTED, 0, 1, 0, 2, 0, 3, 1, 4, 2, 1, 2, 4, 2, 8, 3, 9, 3, 10, 4, 15, 8, 11, 9, 12, 10, 12, 10, 13, 11, 8, 11, 14, 12, 14, 13, 12, 14, 12, 14, 0, 15, 11, -1); igraph_dominator_tree(&g, /*root=*/ 0, &dom, &domtree, &leftout, /*mode=*/ IGRAPH_OUT); igraph_vector_print(&dom); igraph_vector_print(&leftout); igraph_write_graph_edgelist(&domtree, stdout); igraph_vector_destroy(&dom); igraph_vector_destroy(&leftout); igraph_destroy(&domtree); igraph_destroy(&g); /* -------------------------------------------------------------------*/ igraph_vector_init(&dom, 0); igraph_vector_init(&leftout, 0); igraph_small(&g, 10, IGRAPH_DIRECTED, 0, 9, 1, 0, 1, 2, 2, 3, 2, 7, 3, 1, 4, 1, 4, 3, 5, 2, 5, 3, 5, 4, 5, 8, 6, 5, 6, 9, 8, 7, -1); igraph_dominator_tree(&g, /*root=*/ 9, &dom, &domtree, &leftout, /*mode=*/ IGRAPH_IN); igraph_vector_print(&dom); igraph_vector_print(&leftout); igraph_write_graph_edgelist(&domtree, stdout); igraph_vector_destroy(&dom); igraph_vector_destroy(&leftout); igraph_destroy(&domtree); igraph_destroy(&g); return 0; }
typedef struct {
int nopush, norelabel, nogap, nogapnodes, nobfs;
push-relabel maximum flow solver.
Arguments:
|
The number of push operations performed. |
|
The number of relabel operarions performed. |
|
The number of times the gap heuristics was used. |
|
The total number of vertices that were omitted form further calculations because of the gap heuristics. |
|
The number of times the reverse BFS was run to assign good values to the height function. This includes an initial run before the whole algorithm, so it is always at least one. |
igraph_st_mincut — Minimum cut between a source and a target vertexigraph_st_mincut_value — The minimum s-t cut in a graphigraph_all_st_cuts — List all edge-cuts between two vertices in a directed graphigraph_all_st_mincuts — All minimum s-t cuts of a directed graphigraph_mincut — Calculates the minimum cut in a graph.igraph_mincut_value — The minimum edge cut in a graphigraph_gomory_hu_tree — Gomory-Hu tree of a graph.
int igraph_st_mincut(const igraph_t *graph, igraph_real_t *value,
igraph_vector_t *cut, igraph_vector_t *partition,
igraph_vector_t *partition2,
igraph_integer_t source, igraph_integer_t target,
const igraph_vector_t *capacity);
Finds the edge set that has the smallest total capacity among all edge sets that disconnect the source and target vertices.
The calculation is performed using maximum flow
techniques, by calling igraph_maxflow().
Arguments:
|
The input graph. |
|
Pointer to a real variable, the value of the cut is stored here. |
|
Pointer to a real vector, the edge ids that are included in the cut are stored here. This argument is ignored if it is a null pointer. |
|
Pointer to a real vector, the vertex ids of the vertices in the first partition of the cut are stored here. The first partition is always the one that contains the source vertex. This argument is ignored if it is a null pointer. |
|
Pointer to a real vector, the vertex ids of the vertices in the second partition of the cut are stored here. The second partition is always the one that contains the target vertex. This argument is ignored if it is a null pointer. |
|
Integer, the id of the source vertex. |
|
Integer, the id of the target vertex. |
|
Vector containing the capacity of the edges. If a null pointer, then every edge is considered to have capacity 1.0. |
Returns:
Error code. |
See also:
Time complexity: see igraph_maxflow().
int igraph_st_mincut_value(const igraph_t *graph, igraph_real_t *value,
igraph_integer_t source, igraph_integer_t target,
const igraph_vector_t *capacity);
The minimum s-t cut in a weighted (=valued) graph is the
total minimum edge weight needed to remove from the graph to
eliminate all paths from a given vertex (source) to
another vertex (target). Directed paths are considered in
directed graphs, and undirected paths in undirected graphs.
The minimum s-t cut between two vertices is known to be same
as the maximum flow between these two vertices. So this function
calls igraph_maxflow_value() to do the calculation.
Arguments:
|
The input graph. |
|
Pointer to a real variable, the result will be stored here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
|
Pointer to the capacity vector, it should contain non-negative numbers and its length should be the same the the number of edges in the graph. It can be a null pointer, then every edge has unit capacity. |
Returns:
Error code. |
Time complexity: O(|V|^3), see also the discussion for igraph_maxflow_value(), |V| is the number of vertices.
int igraph_all_st_cuts(const igraph_t *graph,
igraph_vector_ptr_t *cuts,
igraph_vector_ptr_t *partition1s,
igraph_integer_t source,
igraph_integer_t target);
This function lists all edge-cuts between a source and a target vertex. Every cut is listed exactly once. The implemented algorithm is described in JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351--372, 1996.
Arguments:
|
The input graph, is must be directed. |
|
An initialized pointer vector, the cuts are stored
here. It is a list of pointers to igraph_vector_t
objects. Each vector will contain the ids of the edges in
the cut. This argument is ignored if it is a null pointer.
To free all memory allocated for |
|
An initialized pointer vector, the list of
vertex sets, generating the actual edge cuts, are stored
here. Each vector contains a set of vertex ids. If X is such
a set, then all edges going from X to the complement of X
form an (s,t) edge-cut in the graph. This argument is
ignored if it is a null pointer.
To free all memory allocated for |
|
The id of the source vertex. |
|
The id of the target vertex. |
Returns:
Error code. |
Time complexity: O(n(|V|+|E|)), where |V| is the number of vertices, |E| is the number of edges, and n is the number of cuts.
int igraph_all_st_mincuts(const igraph_t *graph, igraph_real_t *value,
igraph_vector_ptr_t *cuts,
igraph_vector_ptr_t *partition1s,
igraph_integer_t source,
igraph_integer_t target,
const igraph_vector_t *capacity);
This function lists all edge cuts between two vertices, in a directed graph, with minimum total capacity. Possibly, multiple cuts may have the same total capacity, although there is often only one minimum cut in weighted graphs. It is recommended to supply integer-values capacities. Otherwise, not all minimum cuts may be detected because of numerical roundoff errors. The implemented algorithm is described in JS Provan and DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351--372, 1996.
Arguments:
|
The input graph, it must be directed. |
|
Pointer to a real number, the value of the minimum cut is stored here, unless it is a null pointer. |
|
An initialized pointer vector, the cuts are stored
here. It is a list of pointers to igraph_vector_t
objects. Each vector will contain the ids of the edges in
the cut. This argument is ignored if it is a null pointer.
To free all memory allocated for |
|
An initialized pointer vector, the list of vertex sets, generating the actual edge cuts, are stored here. Each vector contains a set of vertex ids. If X is such a set, then all edges going from X to the complement of X form an (s,t) edge-cut in the graph. This argument is ignored if it is a null pointer. |
|
The id of the source vertex. |
|
The id of the target vertex. |
|
Vector of edge capacities. All capacities must be strictly positive. If this is a null pointer, then all edges are assumed to have capacity one. |
Returns:
Error code. |
Time complexity: O(n(|V|+|E|))+O(F), where |V| is the number of
vertices, |E| is the number of edges, and n is the number of cuts;
O(F) is the time complexity of the maximum flow algorithm, see igraph_maxflow().
Example 22.4. File examples/simple/igraph_all_st_mincuts.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> int print_and_destroy(igraph_t *g, igraph_real_t value, igraph_vector_ptr_t *partitions, igraph_vector_ptr_t *cuts) { long int i, e, m, n = igraph_vector_ptr_size(partitions); printf("Found %li cuts, value: %g\n", n, value); for (i = 0; i < n; i++) { igraph_vector_t *vec = VECTOR(*partitions)[i]; igraph_vector_t *vec2 = cuts ? VECTOR(*cuts)[i] : 0; printf("Partition %li: ", i); igraph_vector_print(vec); if (vec2) { printf("Cut %li:\n", i); m = igraph_vector_size(vec2); for (e = 0; e < m; e++) { igraph_integer_t from, to; igraph_edge(g, VECTOR(*vec2)[e], &from, &to); if (igraph_is_directed(g)) { printf(" %" IGRAPH_PRId " -> %" IGRAPH_PRId "\n", from, to); } else { printf(" %" IGRAPH_PRId " -- %" IGRAPH_PRId "\n", from, to); } } } igraph_vector_destroy(vec); if (vec2) { igraph_vector_destroy(vec2); } igraph_free(vec); if (vec2) { igraph_free(vec2); } } igraph_vector_ptr_destroy(partitions); if (cuts) { igraph_vector_ptr_destroy(cuts); } printf("\n"); return 0; } int main() { igraph_t g; igraph_vector_ptr_t partitions; igraph_vector_ptr_t cuts; igraph_real_t value; igraph_small(&g, 5, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 3, 4, -1); igraph_vector_ptr_init(&partitions, 0); igraph_vector_ptr_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 0, /*target=*/ 4, /*capacity=*/ 0); print_and_destroy(&g, value, &partitions, &cuts); igraph_destroy(&g); /* ---------------------------------------------------------------- */ igraph_small(&g, 6, IGRAPH_DIRECTED, 0, 1, 1, 2, 1, 3, 2, 4, 3, 4, 4, 5, -1); igraph_vector_ptr_init(&partitions, 0); igraph_vector_ptr_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 0, /*target=*/ 5, /*capacity=*/ 0); print_and_destroy(&g, value, &partitions, &cuts); igraph_destroy(&g); /* ---------------------------------------------------------------- */ igraph_small(&g, 6, IGRAPH_DIRECTED, 0, 1, 1, 2, 1, 3, 2, 4, 3, 4, 4, 5, -1); igraph_vector_ptr_init(&partitions, 0); igraph_vector_ptr_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 0, /*target=*/ 4, /*capacity=*/ 0); print_and_destroy(&g, value, &partitions, &cuts); igraph_destroy(&g); /* ---------------------------------------------------------------- */ igraph_small(&g, 9, IGRAPH_DIRECTED, 0, 1, 0, 2, 1, 3, 2, 3, 1, 4, 4, 2, 1, 5, 5, 2, 1, 6, 6, 2, 1, 7, 7, 2, 1, 8, 8, 2, -1); igraph_vector_ptr_init(&partitions, 0); igraph_vector_ptr_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 0, /*target=*/ 3, /*capacity=*/ 0); print_and_destroy(&g, value, &partitions, &cuts); igraph_destroy(&g); /* ---------------------------------------------------------------- */ igraph_small(&g, 4, IGRAPH_DIRECTED, 1, 0, 2, 0, 2, 1, 3, 2, -1); igraph_vector_ptr_init(&partitions, 0); igraph_vector_ptr_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 2, /*target=*/ 0, /*capacity=*/ 0); print_and_destroy(&g, value, &partitions, &cuts); igraph_destroy(&g); /* ---------------------------------------------------------------- */ igraph_small(&g, 4, IGRAPH_DIRECTED, 1, 0, 2, 0, 2, 1, 2, 3, -1); igraph_vector_ptr_init(&partitions, 0); igraph_vector_ptr_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 2, /*target=*/ 0, /*capacity=*/ 0); print_and_destroy(&g, value, &partitions, &cuts); igraph_destroy(&g); /* ---------------------------------------------------------------- */ igraph_small(&g, 9, IGRAPH_DIRECTED, 0, 4, 0, 7, 1, 6, 2, 1, 3, 8, 4, 0, 4, 2, 4, 5, 5, 0, 5, 3, 6, 7, 7, 8, -1); igraph_vector_ptr_init(&partitions, 0); igraph_vector_ptr_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 0, /*target=*/ 8, /*capacity=*/ 0); print_and_destroy(&g, value, &partitions, &cuts); igraph_destroy(&g); return 0; }
int igraph_mincut(const igraph_t *graph,
igraph_real_t *value,
igraph_vector_t *partition,
igraph_vector_t *partition2,
igraph_vector_t *cut,
const igraph_vector_t *capacity);
This function calculates the minimum cut in a graph.
The minimum cut is the minimum set of edges which needs to be
removed to disconnect the graph. The minimum is calculated using
the weights (capacity) of the edges, so the cut with the minimum
total capacity is calculated.
For directed graphs an implementation based on calculating 2|V|-2 maximum flows is used. For undirected graphs we use the Stoer-Wagner algorithm, as described in M. Stoer and F. Wagner: A simple min-cut algorithm, Journal of the ACM, 44 585-591, 1997.
The first implementation of the actual cut calculation for undirected graphs was made by Gregory Benison, thanks Greg.
Arguments:
|
The input graph. |
|
Pointer to a float, the value of the cut will be stored here. |
|
Pointer to an initialized vector, the ids of the vertices in the first partition after separating the graph will be stored here. The vector will be resized as needed. This argument is ignored if it is a NULL pointer. |
|
Pointer to an initialized vector the ids of the vertices in the second partition will be stored here. The vector will be resized as needed. This argument is ignored if it is a NULL pointer. |
|
Pointer to an initialized vector, the ids of the edges in the cut will be stored here. This argument is ignored if it is a NULL pointer. |
|
A numeric vector giving the capacities of the edges. If a null pointer then all edges have unit capacity. |
Returns:
Error code. |
See also:
|
Time complexity: for directed graphs it is O(|V|^4), but see the
remarks at igraph_maxflow(). For undirected graphs it is
O(|V||E|+|V|^2 log|V|). |V| and |E| are the number of vertices and
edges respectively.
Example 22.5. File examples/simple/igraph_mincut.c
/* -*- mode: C -*- */ /* IGraph library. Copyright (C) 2007-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_mincut(const igraph_t *graph, igraph_real_t value, const igraph_vector_t *partition, const igraph_vector_t *partition2, const igraph_vector_t *cut, const igraph_vector_t *capacity) { long int i, nc = igraph_vector_size(cut); igraph_bool_t directed = igraph_is_directed(graph); printf("mincut value: %g\n", (double) value); printf("first partition: "); igraph_vector_print(partition); printf("second partition: "); igraph_vector_print(partition2); printf("edges in the cut: "); for (i = 0; i < nc; i++) { long int edge = VECTOR(*cut)[i]; long int from = IGRAPH_FROM(graph, edge); long int to = IGRAPH_TO (graph, edge); if (!directed && from > to) { igraph_integer_t tmp = from; from = to; to = tmp; } printf("%li-%li (%g), ", from, to, VECTOR(*capacity)[edge]); } printf("\n"); return 0; } int main() { igraph_t g; igraph_vector_t weights, partition, partition2, cut; igraph_real_t value; igraph_vector_init(&partition, 0); igraph_vector_init(&partition2, 0); igraph_vector_init(&cut, 0); /* -------------------------------------------- */ igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 1, 0, 4, 1, 2, 1, 4, 1, 5, 2, 3, 2, 6, 3, 6, 3, 7, 4, 5, 5, 6, 6, 7, -1); igraph_vector_init_int_end(&weights, -1, 2, 3, 3, 2, 2, 4, 2, 2, 2, 3, 1, 3, -1); igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights); print_mincut(&g, value, &partition, &partition2, &cut, &weights); igraph_vector_destroy(&weights); igraph_destroy(&g); /* -------------------------------------------- */ igraph_small(&g, 6, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 0, 5, 5, 4, 4, 3, 3, 0, -1); igraph_vector_init_int_end(&weights, -1, 3, 1, 2, 10, 1, 3, 2, -1); igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights); print_mincut(&g, value, &partition, &partition2, &cut, &weights); igraph_vector_destroy(&weights); igraph_destroy(&g); /* -------------------------------------------- */ igraph_small(&g, 5, IGRAPH_DIRECTED, 4, 3, 3, 2, 2, 1, 1, 0, -1); igraph_vector_init_int_end(&weights, -1, 1, 1, 1, 1, -1); igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights); print_mincut(&g, value, &partition, &partition2, &cut, &weights); igraph_vector_destroy(&weights); igraph_destroy(&g); /* -------------------------------------------- */ igraph_vector_destroy(&cut); igraph_vector_destroy(&partition2); igraph_vector_destroy(&partition); return 0; }
int igraph_mincut_value(const igraph_t *graph, igraph_real_t *res,
const igraph_vector_t *capacity);
The minimum edge cut in a graph is the total minimum weight of the edges needed to remove from the graph to make the graph not strongly connected. (If the original graph is not strongly connected then this is zero.) Note that in undirected graphs strong connectedness is the same as weak connectedness.
The minimum cut can be calculated with maximum flow techniques, although the current implementation does this only for directed graphs and a separate non-flow based implementation is used for undirected graphs. See Mechthild Stoer and Frank Wagner: A simple min-cut algorithm, Journal of the ACM 44 585--591, 1997. For directed graphs the maximum flow is calculated between a fixed vertex and all the other vertices in the graph and this is done in both directions. Then the minimum is taken to get the minimum cut.
Arguments:
|
The input graph. |
|
Pointer to a real variable, the result will be stored here. |
|
Pointer to the capacity vector, it should contain the same number of non-negative numbers as the number of edges in the graph. If a null pointer then all edges will have unit capacity. |
Returns:
Error code. |
See also:
Time complexity: O(log(|V|)*|V|^2) for undirected graphs and
O(|V|^4) for directed graphs, but see also the discussion at the
documentation of igraph_maxflow_value().
int igraph_gomory_hu_tree(const igraph_t *graph, igraph_t *tree,
igraph_vector_t *flows, const igraph_vector_t *capacity);
The Gomory-Hu tree is a concise representation of the value of all the maximum flows (or minimum cuts) in a graph. The vertices of the tree correspond exactly to the vertices of the original graph in the same order. Edges of the Gomory-Hu tree are annotated by flow values. The value of the maximum flow (or minimum cut) between an arbitrary (u,v) vertex pair in the original graph is then given by the minimum flow value (i.e. edge annotation) along the shortest path between u and v in the Gomory-Hu tree.
This implementation uses Gusfield's algorithm to construct the Gomory-Hu tree. See the following paper for more details:
Gusfield D: Very simple methods for all pairs network flow analysis. SIAM J Comput 19(1):143-155, 1990.
Arguments:
|
The input graph. |
|
Pointer to an uninitialized graph; the result will be stored here. |
|
Pointer to an uninitialized vector; the flow values corresponding to each edge in the Gomory-Hu tree will be returned here. You may pass a NULL pointer here if you are not interested in the flow values. |
|
Vector containing the capacity of the edges. If NULL, then every edge is considered to have capacity 1.0. |
Returns:
Error code. |
Time complexity: O(|V|^4) since it performs a max-flow calculation between vertex zero and every other vertex and max-flow is O(|V|^3).
See also:
igraph_st_edge_connectivity — Edge connectivity of a pair of verticesigraph_edge_connectivity — The minimum edge connectivity in a graph.igraph_st_vertex_connectivity — The vertex connectivity of a pair of verticesigraph_vertex_connectivity — The vertex connectivity of a graph
int igraph_st_edge_connectivity(const igraph_t *graph, igraph_integer_t *res,
igraph_integer_t source,
igraph_integer_t target);
The edge connectivity of two vertices (source and
target) in a graph is the minimum number of edges that
have to be deleted from the graph to eliminate all paths from source to target.
This function uses the maximum flow algorithm to calculate the edge connectivity.
Arguments:
|
The input graph, it has to be directed. |
|
Pointer to an integer, the result will be stored here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
Returns:
Error code. |
Time complexity: O(|V|^3).
See also:
|
int igraph_edge_connectivity(const igraph_t *graph, igraph_integer_t *res,
igraph_bool_t checks);
This is the minimum of the edge connectivity over all pairs of vertices in the graph.
The edge connectivity of a graph is the same as group adhesion as defined in Douglas R. White and Frank Harary: The cohesiveness of blocks in social networks: node connectivity and conditional density, Sociological Methodology 31:305--359, 2001.
Arguments:
|
The input graph. |
|
Pointer to an integer, the result will be stored here. |
|
Logical constant. Whether to check that the graph is connected and also the degree of the vertices. If the graph is not (strongly) connected then the connectivity is obviously zero. Otherwise if the minimum degree is one then the edge connectivity is also one. It is a good idea to perform these checks, as they can be done quickly compared to the connectivity calculation itself. They were suggested by Peter McMahan, thanks Peter. |
Returns:
Error code. |
Time complexity: O(log(|V|)*|V|^2) for undirected graphs and
O(|V|^4) for directed graphs, but see also the discussion at the
documentation of igraph_maxflow_value().
See also:
int igraph_st_vertex_connectivity(const igraph_t *graph,
igraph_integer_t *res,
igraph_integer_t source,
igraph_integer_t target,
igraph_vconn_nei_t neighbors);
The vertex connectivity of two vertices (source and
target) is the minimum number of vertices that have to be
deleted to eliminate all paths from source to target. Directed paths are considered in directed graphs.
The vertex connectivity of a pair is the same as the number of different (i.e. node-independent) paths from source to target.
The current implementation uses maximum flow calculations to obtain the result.
Arguments:
|
The input graph. |
|
Pointer to an integer, the result will be stored here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
|
A constant giving what to do if the two vertices
are connected. Possible values:
|
Returns:
Error code. |
Time complexity: O(|V|^3), but see the discussion at igraph_maxflow_value().
See also:
int igraph_vertex_connectivity(const igraph_t *graph, igraph_integer_t *res,
igraph_bool_t checks);
The vertex connectivity of a graph is the minimum vertex connectivity along each pairs of vertices in the graph.
The vertex connectivity of a graph is the same as group cohesion as defined in Douglas R. White and Frank Harary: The cohesiveness of blocks in social networks: node connectivity and conditional density, Sociological Methodology 31:305--359, 2001.
Arguments:
|
The input graph. |
|
Pointer to an integer, the result will be stored here. |
|
Logical constant. Whether to check that the graph is connected and also the degree of the vertices. If the graph is not (strongly) connected then the connectivity is obviously zero. Otherwise if the minimum degree is one then the vertex connectivity is also one. It is a good idea to perform these checks, as they can be done quickly compared to the connectivity calculation itself. They were suggested by Peter McMahan, thanks Peter. |
Returns:
Error code. |
Time complexity: O(|V|^5).
See also:
int igraph_edge_disjoint_paths(const igraph_t *graph, igraph_integer_t *res,
igraph_integer_t source,
igraph_integer_t target);
A set of paths between two vertices is called edge-disjoint if they do not share any edges. The maximum number of edge-disjoint paths are calculated by this function using maximum flow techniques. Directed paths are considered in directed graphs.
Note that the number of disjoint paths is the same as the edge connectivity of the two vertices using uniform edge weights.
Arguments:
|
The input graph, can be directed or undirected. |
|
Pointer to an integer variable, the result will be stored here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
Returns:
Error code. |
Time complexity: O(|V|^3), but see the discussion at igraph_maxflow_value().
See also:
int igraph_vertex_disjoint_paths(const igraph_t *graph, igraph_integer_t *res,
igraph_integer_t source,
igraph_integer_t target);
A set of paths between two vertices is called vertex-disjoint if they share no vertices. The calculation is performed by using maximum flow techniques.
Note that the number of vertex-disjoint paths is the same as the vertex connectivity of the two vertices in most cases (if the two vertices are not connected by an edge).
Arguments:
|
The input graph. |
|
Pointer to an integer variable, the result will be stored here. |
|
The id of the source vertex. |
|
The id of the target vertex. |
Returns:
Error code. |
Time complexity: O(|V|^3).
See also:
int igraph_adhesion(const igraph_t *graph, igraph_integer_t *res,
igraph_bool_t checks);
This quantity is defined by White and Harary in The cohesiveness of blocks in social networks: node connectivity and conditional density, (Sociological Methodology 31:305--359, 2001) and basically it is the edge connectivity of the graph with uniform edge weights.
Arguments:
|
The input graph, either directed or undirected. |
|
Pointer to an integer, the result will be stored here. |
|
Logical constant. Whether to check that the graph is connected and also the degree of the vertices. If the graph is not (strongly) connected then the adhesion is obviously zero. Otherwise if the minimum degree is one then the adhesion is also one. It is a good idea to perform these checks, as they can be done quickly compared to the edge connectivity calculation itself. They were suggested by Peter McMahan, thanks Peter. * |
Returns:
Error code. |
Time complexity: O(log(|V|)*|V|^2) for undirected graphs and
O(|V|^4) for directed graphs, but see also the discussion at the
documentation of igraph_maxflow_value().
See also:
int igraph_cohesion(const igraph_t *graph, igraph_integer_t *res,
igraph_bool_t checks);
This quantity was defined by White and Harary in “The cohesiveness of blocks in social networks: node connectivity and conditional density”, (Sociological Methodology 31:305--359, 2001) and it is the same as the vertex connectivity of a graph.
Arguments:
|
The input graph. |
|
Pointer to an integer variable, the result will be stored here. |
|
Logical constant. Whether to check that the graph is connected and also the degree of the vertices. If the graph is not (strongly) connected then the cohesion is obviously zero. Otherwise if the minimum degree is one then the cohesion is also one. It is a good idea to perform these checks, as they can be done quickly compared to the vertex connectivity calculation itself. They were suggested by Peter McMahan, thanks Peter. |
Returns:
Error code. |
Time complexity: O(|V|^4), |V| is the number of vertices. In
practice it is more like O(|V|^2), see igraph_maxflow_value().
See also:
int igraph_cohesive_blocks(const igraph_t *graph,
igraph_vector_ptr_t *blocks,
igraph_vector_t *cohesion,
igraph_vector_t *parent,
igraph_t *block_tree);
Cohesive blocking is a method of determining hierarchical subsets of graph vertices based on their structural cohesion (or vertex connectivity). For a given graph G, a subset of its vertices S is said to be maximally k-cohesive if there is no superset of S with vertex connectivity greater than or equal to k. Cohesive blocking is a process through which, given a k-cohesive set of vertices, maximally l-cohesive subsets are recursively identified with l>k. Thus a hiearchy of vertex subsets is found, whith the entire graph G at its root. See the following reference for details: J. Moody and D. R. White. Structural cohesion and embeddedness: A hierarchical concept of social groups. American Sociological Review, 68(1):103--127, Feb 2003.
This function implements cohesive blocking and calculates the complete cohesive block hierarchy of a graph.
Arguments:
|
The input graph. It must be undirected and simple. See
|
|
If not a null pointer, then it must be an initialized vector of pointers and the cohesive blocks are stored here. Each block is encoded with a numeric vector, that contains the vertex ids of the block. |
|
If not a null pointer, then it must be an initialized
vector and the cohesion of the blocks is stored here, in the same
order as the blocks in the |
|
If not a null pointer, then it must be an initialized
vector and the block hierarchy is stored here. For each block, the
id (i.e. the position in the |
|
If not a null pointer, then it must be a pointer
to an uninitialized graph, and the block hierarchy is stored
here as an igraph graph. The vertex ids correspond to the order
of the blocks in the |
Returns:
Error code. |
Time complexity: TODO.
Example 22.6. File examples/simple/cohesive_blocks.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> int doit(igraph_t *g) { igraph_vector_ptr_t blocks; igraph_vector_t cohesion; igraph_vector_t parent; igraph_t block_tree; long int i; igraph_vector_ptr_init(&blocks, 0); igraph_vector_init(&cohesion, 0); igraph_vector_init(&parent, 0); igraph_cohesive_blocks(g, &blocks, &cohesion, &parent, &block_tree); printf("Blocks:\n"); for (i = 0; i < igraph_vector_ptr_size(&blocks); i++) { igraph_vector_t *sg = VECTOR(blocks)[i]; printf(" "); igraph_vector_print(sg); igraph_vector_destroy(sg); igraph_free(sg); } printf("Cohesion:\n "); igraph_vector_print(&cohesion); printf("Parents:\n "); igraph_vector_print(&parent); printf("Block graph:\n"); igraph_write_graph_edgelist(&block_tree, stdout); igraph_vector_ptr_destroy(&blocks); igraph_vector_destroy(&cohesion); igraph_vector_destroy(&parent); igraph_destroy(&block_tree); return 0; } int main() { igraph_t g; int ret; /* --------------------------------------------------------*/ /* The graph from the Moody-White paper */ 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); if ( (ret = doit(&g)) ) { return ret; } igraph_destroy(&g); printf("--\n"); /* --------------------------------------------------------*/ /* A tricky graph, where the separators themselves */ /* form a block. But recently we don't include this */ /* block in the results. */ igraph_small(&g, 8, IGRAPH_UNDIRECTED, 0, 1, 0, 4, 0, 5, 1, 2, 1, 4, 1, 5, 1, 6, 2, 3, 2, 5, 2, 6, 2, 7, 3, 6, 3, 7, 4, 5, 5, 6, 6, 7, -1); if ( (ret = doit(&g)) ) { return ret; } igraph_destroy(&g); printf("--\n"); /* --------------------------------------------------------*/ /* The science camp graph from http://intersci.ss.uci.edu/ */ /* wiki/index.php/Cohesive_blocking */ igraph_small(&g, 18, IGRAPH_UNDIRECTED, 0, 1, 0, 2, 0, 3, 1, 2, 1, 3, 1, 16, 1, 17, 2, 3, 3, 17, 4, 5, 4, 6, 4, 7, 4, 8, 5, 6, 5, 7, 6, 7, 6, 8, 7, 8, 7, 16, 8, 9, 8, 10, 9, 11, 9, 12, 9, 13, 9, 14, 10, 11, 10, 12, 10, 13, 11, 14, 12, 13, 12, 14, 12, 15, 15, 16, 15, 17, 16, 17, -1); if ( (ret = doit(&g)) ) { return ret; } igraph_destroy(&g); printf("--\n"); /* --------------------------------------------------------*/ /* Zachary karate-club */ igraph_small(&g, 34, IGRAPH_UNDIRECTED, 0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, 0, 8, 0, 10, 0, 11, 0, 12, 0, 13, 0, 17, 0, 19, 0, 21, 0, 31, 1, 2, 1, 3, 1, 7, 1, 13, 1, 17, 1, 19, 1, 21, 1, 30, 2, 3, 2, 7, 2, 27, 2, 28, 2, 32, 2, 9, 2, 8, 2, 13, 3, 7, 3, 12, 3, 13, 4, 6, 4, 10, 5, 6, 5, 10, 5, 16, 6, 16, 8, 30, 8, 32, 8, 33, 9, 33, 13, 33, 14, 32, 14, 33, 15, 32, 15, 33, 18, 32, 18, 33, 19, 33, 20, 32, 20, 33, 22, 32, 22, 33, 23, 25, 23, 27, 23, 32, 23, 33, 23, 29, 24, 25, 24, 27, 24, 31, 25, 31, 26, 29, 26, 33, 27, 33, 28, 31, 28, 33, 29, 32, 29, 33, 30, 32, 30, 33, 31, 32, 31, 33, 32, 33, -1); if ( (ret = doit(&g)) ) { return ret; } igraph_destroy(&g); printf("--\n"); return 0; }
| ← Chapter 21. Reading and writing graphs from and to files | Chapter 23. Vertex separators → |