Module flow 

Network-flow algorithms (ALGO-FL-*).

First entry: max_flow_value (ALGO-FL-002) — scalar maximum-flow value via Dinic’s algorithm (BFS level graph + DFS blocking flow). Mirrors igraph C igraph_maxflow_value from references/igraph/src/flow/flow.c, which delegates to the Goldberg-Tarjan push-relabel igraph_maxflow. The scalar max-flow value is unique (max-flow / min-cut theorem) regardless of which algorithm produced it, so the two backends agree bit-for-bit on unit-capacity fixtures and within numerical tolerance on weighted ones.

Structs

DominatorTree

Result of dominator_tree.

GomoryHuTree

Output of gomory_hu_tree — a weighted undirected tree on the same vertex set as the input graph, plus one flow value per tree edge.

MaxFlow

Output of max_flow: scalar value, per-edge flow vector, cut edge ids, and source-side / sink-side vertex partitions.

StCuts

Result of all_st_cuts.

StMinCuts

Result of all_st_mincuts.

StMincut

Output of st_mincut: scalar value, cut edge ids, and the source-side / sink-side vertex partitions.

Enums

DominatorMode

Traversal direction for dominator_tree.

VconnNei

Behaviour when source and target are directly adjacent.

Functions

adhesion

Group adhesion — igraph C alias igraph_adhesion (flow.c:2433). Exact synonym for edge_connectivity; kept for naming parity with the upstream API and so users following the White-Harary (2001) sociological-network literature have a direct hit. Identical signature and behaviour.

all_st_cuts

List all (s,t) edge cuts of a directed graph (Provan-Shier).

all_st_mincuts

List all minimum (s,t) edge cuts of a directed graph (Provan-Shier).

cohesion

Group cohesion — igraph C alias igraph_cohesion (flow.c:2470). Exact synonym for vertex_connectivity; kept for naming parity with the upstream API and so users following the White-Harary (2001) sociological-network literature have a direct hit. Identical signature and behaviour.

dominator_tree

Compute the Lengauer-Tarjan dominator tree of a directed flowgraph.

edge_connectivity

Edge connectivity (adhesion) of a graph.

edge_disjoint_paths

Maximum number of pairwise edge-disjoint paths from source to target.

gomory_hu_tree

Gomory-Hu cut tree of an undirected graph (Gusfield 1990).

max_flow

Full maximum-flow computation: value, per-edge flow, cut edges, and source-side / sink-side vertex partitions.

max_flow_value

Scalar maximum-flow value from source to target.

mincut

Compute the global minimum cut of a (possibly weighted) graph.

mincut_value

Global minimum-cut value of a (possibly weighted) graph.

st_edge_connectivity

Edge connectivity between two vertices: the minimum number of edges whose removal disconnects source from target.

st_mincut

Full s-t minimum-cut: scalar value, the cut edge list, and the source-side / sink-side vertex partitions.

st_mincut_value

Scalar s-t minimum-cut value (capacity of the minimum edge set whose removal disconnects source from target).

st_vertex_connectivity

Vertex connectivity between two vertices.

vertex_connectivity

Vertex connectivity (cohesion) of a graph.

vertex_disjoint_paths

Maximum number of pairwise internally vertex-disjoint paths from source to target.

Type Aliases

Mincut

Result of the global minimum cut computation.