For using the igraph C library
igraph_maxflow — Maximum network flow between a pair of vertices.igraph_maxflow_value — Maximum flow in a network with the push/relabel algorithm.igraph_dominator_tree — Calculates the dominator tree of a flowgraph.igraph_maxflow_stats_t — Data structure holding statistics from the push-relabel maximum flow solver.
igraph_error_t igraph_maxflow(const igraph_t *graph, igraph_real_t *value,
igraph_vector_t *flow, igraph_vector_int_t *cut,
igraph_vector_int_t *partition, igraph_vector_int_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 https://doi.org/10.1145/48014.61051.
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
#include <igraph.h> int main(void) { 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_flow( &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_flow(&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_flow(&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_flow(&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_flow(&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
#include <igraph.h> int main(void) { igraph_t g; igraph_real_t flow_value; igraph_vector_int_t cut; igraph_vector_t capacity; igraph_vector_int_t partition, partition2; igraph_vector_t flow; igraph_integer_t i; igraph_maxflow_stats_t stats; 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_int_init(&cut, 0); igraph_vector_int_init(&partition, 0); igraph_vector_int_init(&partition2, 0); igraph_vector_init(&flow, 0); igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2, /*source=*/ 0, /*target=*/ 2, &capacity, &stats); igraph_integer_t nc = igraph_vector_int_size(&cut); printf("flow value: %g\n", (double) flow_value); printf("flow: "); igraph_vector_print(&flow); printf("first partition: "); igraph_vector_int_print(&partition); printf("second partition: "); igraph_vector_int_print(&partition2); printf("edges in the cut: "); for (i = 0; i < nc; i++) { igraph_integer_t edge = VECTOR(cut)[i]; igraph_integer_t from = IGRAPH_FROM(&g, edge); igraph_integer_t to = IGRAPH_TO(&g, edge); printf("%" IGRAPH_PRId "-%" IGRAPH_PRId " (%g), ", from, to, VECTOR(capacity)[edge]); } printf("\n"); igraph_vector_int_destroy(&cut); igraph_vector_int_destroy(&partition2); igraph_vector_int_destroy(&partition); igraph_vector_destroy(&capacity); igraph_vector_destroy(&flow); igraph_destroy(&g); return 0; }
igraph_error_t 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 https://doi.org/10.1145/48014.61051.
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:
|
igraph_error_t igraph_dominator_tree(const igraph_t *graph,
igraph_integer_t root,
igraph_vector_int_t *dom,
igraph_t *domtree,
igraph_vector_int_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. https://doi.org/10.1145/357062.357071
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, |
|
Pointer to an uninitialized igraph_t,
or |
|
Pointer to an initialized vector object, or |
|
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
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t g, domtree; igraph_vector_int_t dom; igraph_vector_int_t leftout; igraph_vector_int_init(&dom, 0); igraph_vector_int_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_int_print(&dom); igraph_vector_int_print(&leftout); igraph_write_graph_edgelist(&domtree, stdout); igraph_vector_int_destroy(&dom); igraph_vector_int_destroy(&leftout); igraph_destroy(&domtree); igraph_destroy(&g); return 0; }
typedef struct {
igraph_integer_t nopush, norelabel, nogap, nogapnodes, nobfs;
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 vertex.igraph_st_mincut_value — The minimum s-t cut in a graph.igraph_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 graph.igraph_mincut — Calculates the minimum cut in a graph.igraph_mincut_value — The minimum edge cut in a graph.igraph_gomory_hu_tree — Gomory-Hu tree of a graph.
igraph_error_t igraph_st_mincut(const igraph_t *graph, igraph_real_t *value,
igraph_vector_int_t *cut, igraph_vector_int_t *partition,
igraph_vector_int_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 an initialized 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 an initialized 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 an initialized 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().
igraph_error_t 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.
igraph_error_t igraph_all_st_cuts(const igraph_t *graph,
igraph_vector_int_list_t *cuts,
igraph_vector_int_list_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 list of integer vectors, the cuts are stored here. Each vector will contain the IDs of the edges in the cut. This argument is ignored if it is a null pointer. |
|
An initialized list of integer vectors, 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. |
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.
igraph_error_t igraph_all_st_mincuts(const igraph_t *graph, igraph_real_t *value,
igraph_vector_int_list_t *cuts,
igraph_vector_int_list_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 or |
|
Pointer to initialized list of integer vectors or |
|
Pointer to an initialized list of integer vectors or |
|
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
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_list_t partitions; igraph_vector_int_list_t cuts; igraph_real_t value; igraph_small(&g, 5, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 3, 4, -1); igraph_vector_int_list_init(&partitions, 0); igraph_vector_int_list_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 0, /*target=*/ 4, /*capacity=*/ 0); igraph_integer_t i, e, m, n = igraph_vector_int_list_size(&partitions); printf("Found %" IGRAPH_PRId " cuts, value: %g\n", n, value); for (i = 0; i < n; i++) { igraph_vector_int_t *vec = igraph_vector_int_list_get_ptr(&partitions, i); igraph_vector_int_t *vec2 = igraph_vector_int_list_get_ptr(&cuts, i); printf("Partition %" IGRAPH_PRId ": ", i); igraph_vector_int_print(vec); if (vec2) { printf("Cut %" IGRAPH_PRId ":\n", i); m = igraph_vector_int_size(vec2); for (e = 0; e < m; e++) { igraph_integer_t from = IGRAPH_FROM(&g, VECTOR(*vec2)[e]), to = IGRAPH_TO(&g, VECTOR(*vec2)[e]); printf(" %" IGRAPH_PRId " -> %" IGRAPH_PRId "\n", from, to); } } } igraph_vector_int_list_destroy(&partitions); igraph_vector_int_list_destroy(&cuts); printf("\n"); igraph_destroy(&g); return 0; }
igraph_error_t igraph_mincut(const igraph_t *graph,
igraph_real_t *value,
igraph_vector_int_t *partition,
igraph_vector_int_t *partition2,
igraph_vector_int_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
#include <igraph.h> int print_mincut(const igraph_t *graph, igraph_real_t value, const igraph_vector_int_t *partition, const igraph_vector_int_t *partition2, const igraph_vector_int_t *cut, const igraph_vector_t *capacity) { igraph_integer_t i, nc = igraph_vector_int_size(cut); igraph_bool_t directed = igraph_is_directed(graph); printf("mincut value: %g\n", (double) value); printf("first partition: "); igraph_vector_int_print(partition); printf("second partition: "); igraph_vector_int_print(partition2); printf("edges in the cut: "); for (i = 0; i < nc; i++) { igraph_integer_t edge = VECTOR(*cut)[i]; igraph_integer_t from = IGRAPH_FROM(graph, edge); igraph_integer_t to = IGRAPH_TO (graph, edge); if (!directed && from > to) { igraph_integer_t tmp = from; from = to; to = tmp; } printf("%" IGRAPH_PRId "-%" IGRAPH_PRId " (%g), ", from, to, VECTOR(*capacity)[edge]); } printf("\n"); return 0; } int main(void) { igraph_t g; igraph_vector_int_t partition, partition2, cut; igraph_vector_t weights; igraph_real_t value; igraph_vector_int_init(&partition, 0); igraph_vector_int_init(&partition2, 0); igraph_vector_int_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_int_destroy(&cut); igraph_vector_int_destroy(&partition2); igraph_vector_int_destroy(&partition); return 0; }
igraph_error_t 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().
igraph_error_t 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:
Reference:
Gusfield D: Very simple methods for all pairs network flow analysis. SIAM J Comput 19(1):143-155, 1990 https://doi.org/10.1137/0219009.
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 vertices.igraph_edge_connectivity — The minimum edge connectivity in a graph.igraph_st_vertex_connectivity — The vertex connectivity of a pair of vertices.igraph_vertex_connectivity — The vertex connectivity of a graph.
igraph_error_t 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) 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:
|
igraph_error_t 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 https://doi.org/10.1111/0081-1750.00098.
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:
igraph_error_t 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 must 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, assuming no direct edges between them.
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:
igraph_error_t 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 https://doi.org/10.1111/0081-1750.00098.
Arguments:
|
The input graph. |
|
Pointer to an integer, the result will be stored here. |
|
Logical constant. Whether to check if the graph is connected or complete 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 1 then the vertex connectivity is also 1. If the graph is complete, the connectivity is the vertex count minus 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:
igraph_error_t 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:
igraph_error_t 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, other than the endpoints. This function computes the largest number of such paths that can be constructed between a source and a target vertex. The calculation is performed by using maximum flow techniques.
When there are no edges from the source to the target, the number of vertex-disjoint paths is the same as the vertex connectivity of the two vertices. When some edges are present, each one of them contributes one extra path.
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:
igraph_error_t 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:
igraph_error_t 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:
igraph_error_t igraph_cohesive_blocks(const igraph_t *graph,
igraph_vector_int_list_t *blocks,
igraph_vector_int_t *cohesion,
igraph_vector_int_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, with the entire graph G at its root.
This function implements cohesive blocking and calculates the complete cohesive block hierarchy of a graph.
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. https://doi.org/10.2307/3088904
Arguments:
|
The input graph. It must be undirected and simple. See
|
|
If not a null pointer, then it must be an initialized
list of integers vectors; the cohesive blocks will be stored here.
Each block is encoded with a vector of type |
|
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
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_list_t blocks; igraph_vector_int_t cohesion; igraph_vector_int_t parent; igraph_t block_tree; igraph_integer_t i; igraph_famous(&g, "zachary"); igraph_vector_int_list_init(&blocks, 0); igraph_vector_int_init(&cohesion, 0); igraph_vector_int_init(&parent, 0); igraph_cohesive_blocks(&g, &blocks, &cohesion, &parent, &block_tree); printf("Blocks:\n"); for (i = 0; i < igraph_vector_int_list_size(&blocks); i++) { igraph_vector_int_t *sg = igraph_vector_int_list_get_ptr(&blocks, i); printf(" "); igraph_vector_int_print(sg); } printf("Cohesion:\n "); igraph_vector_int_print(&cohesion); printf("Parents:\n "); igraph_vector_int_print(&parent); printf("Block graph:\n"); igraph_write_graph_edgelist(&block_tree, stdout); igraph_vector_int_list_destroy(&blocks); igraph_vector_int_destroy(&cohesion); igraph_vector_int_destroy(&parent); igraph_destroy(&block_tree); igraph_destroy(&g); return 0; }
| ← Chapter 21. Reading and writing graphs from and to files | Chapter 23. Vertex separators → |