Module flow 

Maximum flows, minimum cuts and graph connectivity (igraph_flow.h).

A flow network is a graph whose edges carry a non-negative capacity (a &[f64] indexed by edge id; when omitted every edge has capacity 1). A flow from a source to a target assigns to every edge an amount not exceeding its capacity such that, at every other vertex, what comes in goes out. The celebrated max-flow min-cut theorem (Ford and Fulkerson, 1956) states that the largest possible flow value equals the smallest total capacity of a set of edges whose removal disconnects the target from the source. Almost everything in this module is built on that identity: edge and vertex connectivities, disjoint paths, cohesion measures and the Gomory–Hu tree are all max-flow computations in disguise.

All the functions are methods of Graph, with named result structs whenever the C function has several outputs.

Example: max-flow = min-cut

use igraph::prelude::*;

// A small directed pipeline network: 0 is the source, 3 the sink.
let g = Graph::from_edges(&[(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)], 4, true)?;
let capacity = [3.0, 2.0, 1.0, 2.0, 3.0];

let mf = g.maxflow(0, 3, Some(&capacity))?;
assert_eq!(mf.value, 5.0);

// The edges of the minimum cut have a total capacity equal to the flow.
let cut_capacity: f64 = mf.cut.iter().map(|&e| capacity[e as usize]).sum();
assert_eq!(cut_capacity, mf.value);
assert_eq!(g.st_mincut_value(0, 3, Some(&capacity))?, 5.0);

// The flow never exceeds the capacities.
assert!(mf.flow.iter().zip(&capacity).all(|(f, c)| *f <= *c));

Provided functionality

Method	C function	Computes
Graph::maxflow	igraph_maxflow	value, per-edge flow, minimum cut and both sides (MaxFlow)
Graph::maxflow_value	igraph_maxflow_value	only the value of the maximum flow
Graph::maxflow_value_with_stats	igraph_maxflow_value	value plus push-relabel statistics (MaxflowStats)
Graph::st_mincut	igraph_st_mincut	minimum s-t cut (Cut)
Graph::st_mincut_value	igraph_st_mincut_value	value of the minimum s-t cut
Graph::mincut	igraph_mincut	minimum cut of the whole graph (Cut)
Graph::mincut_value	igraph_mincut_value	value of the minimum cut of the whole graph
Graph::st_vertex_connectivity	igraph_st_vertex_connectivity	vertex connectivity of a pair
Graph::vertex_connectivity	igraph_vertex_connectivity	vertex connectivity of the graph
Graph::st_edge_connectivity	igraph_st_edge_connectivity	edge connectivity of a pair
Graph::edge_connectivity	igraph_edge_connectivity	edge connectivity of the graph
Graph::edge_disjoint_paths	igraph_edge_disjoint_paths	number of edge-disjoint paths
Graph::vertex_disjoint_paths	igraph_vertex_disjoint_paths	number of vertex-disjoint paths
Graph::adhesion	igraph_adhesion	White–Harary adhesion (edge connectivity)
Graph::cohesion	igraph_cohesion	White–Harary cohesion (vertex connectivity)
Graph::even_tarjan_reduction	igraph_even_tarjan_reduction	vertex-splitting reduction (EvenTarjanReduction)
Graph::residual_graph	igraph_residual_graph	residual network of a flow (ResidualGraph)
Graph::reverse_residual_graph	igraph_reverse_residual_graph	reverse residual network of a flow
Graph::dominator_tree	igraph_dominator_tree	Lengauer–Tarjan dominator tree (DominatorTree)
Graph::all_st_cuts	igraph_all_st_cuts	every s-t edge cut (StCuts)
Graph::all_st_mincuts	igraph_all_st_mincuts	every minimum s-t edge cut (StMinCuts)
Graph::gomory_hu_tree	igraph_gomory_hu_tree	Gomory–Hu tree of all pairwise flows (GomoryHuTree)

Capacities must be finite and non-negative and, when given, have exactly one entry per edge. igraph itself does not validate the sign of the capacities (negative or NaN entries silently produce meaningless flows, and infinite ones produce NaN flows), so a wrong length or an invalid entry is reported as ErrorKind::InvalidValue before calling into C.

The C reference for everything here is the Flows chapter of the igraph manual.

Example: how robust is the karate club?

use igraph::prelude::*;

let karate = Graph::famous("Zachary")?;
// Vertex 11 has a single friend, so one edge (or one vertex) isolates it.
assert_eq!(karate.edge_connectivity(true)?, 1);
assert_eq!(karate.vertex_connectivity(true)?, 1);
// The two leaders, 0 and 33, are far better connected: by Menger's
// theorem their local edge connectivity is the number of edge-disjoint
// paths, which is also the unit-capacity maximum flow.
let k = karate.st_edge_connectivity(0, 33)?;
assert_eq!(k, 10);
assert_eq!(karate.edge_disjoint_paths(0, 33)?, k);
assert_eq!(karate.maxflow_value(0, 33, None)?, k as f64);
// A Gomory–Hu tree stores all 561 pairwise flows in 33 numbers.
let gh = karate.gomory_hu_tree(None)?;
assert_eq!(gh.flow_between(0, 33), Some(k as f64));

See also

• Graph::is_connected, Graph::articulation_points and Graph::bridges answer the “connectivity at least 1 / 2” questions in linear time, without any flow computation.
• Graph::minimum_size_separators, Graph::all_minimal_st_separators, Graph::is_separator and Graph::cohesive_blocks list the vertex sets behind Graph::vertex_connectivity.
• Graph::maximum_bipartite_matching solves the classic flow application of matching the two sides of a bipartite graph.
• Graph::read_graph_dimacs_flow and Graph::write_graph_dimacs_flow read and write maximum flow instances in the DIMACS format.

Structs

Cut

An edge cut splitting the vertices into two sides, as returned by Graph::st_mincut and Graph::mincut.

DominatorTree

A dominator tree of a flowgraph, see Graph::dominator_tree.

EvenTarjanReduction

The Even–Tarjan reduction of a graph, see Graph::even_tarjan_reduction.

GomoryHuTree

A Gomory–Hu tree, see Graph::gomory_hu_tree.

MaxFlow

A maximum flow between two vertices, as computed by Graph::maxflow.

MaxflowStats

Statistics collected by igraph’s push-relabel maximum flow solver (igraph_maxflow_stats_t).

ResidualGraph

The residual network of a flow, see Graph::residual_graph.

StCuts

All minimal s-t edge cuts of a directed graph, see Graph::all_st_cuts.

StMinCuts

All minimum s-t edge cuts of a directed graph, see Graph::all_st_mincuts.