Crate graph_flow 

graph-flow

Maximum flow and bipartite matching algorithms for graph-rs.

Flow algorithms require a residual graph — a mutable internal representation that tracks remaining capacity and sent flow on each edge. Because this requires mutable aliasing patterns that conflict with Rust’s borrow checker when using the generic Graph trait directly, this crate defines its own index-based FlowGraph structure for flow computation.

Algorithms

Module	Algorithm	Complexity
flow_graph	Residual graph representation	—
ford_fulkerson	Ford-Fulkerson (DFS augmentation)	O(E · max_flow)
edmonds_karp	Edmonds-Karp (BFS augmentation)	O(V · E²)
min_cut	Min-cut from a completed max-flow	O(V + E)
hopcroft_karp	Hopcroft-Karp bipartite matching	O(E · √V)

Design note: why a separate FlowGraph?

The residual graph needs to update both the forward edge and its corresponding reverse edge in a single pass. With Rust’s borrow checker, mutating two elements of the same Vec simultaneously requires either index-based access (what we use here) or unsafe. Using indices is the idiomatic safe solution: we store the index of each edge’s reverse in the adjacency list entry, giving O(1) residual updates with no aliasing.

Re-exports

pub use edmonds_karp::edmonds_karp;

pub use flow_graph::FlowGraph;

pub use ford_fulkerson::ford_fulkerson;

pub use hopcroft_karp::hopcroft_karp;

pub use min_cut::min_cut;

pub use min_cut::MinCut;

Modules

edmonds_karp

Edmonds-Karp maximum flow using BFS augmenting paths. Edmonds-Karp maximum flow via BFS augmenting paths.

flow_graph

Index-based flow graph (residual graph) used by all flow algorithms. Index-based residual graph for flow algorithms.

ford_fulkerson

Ford-Fulkerson maximum flow using DFS augmenting paths. Ford-Fulkerson maximum flow via DFS augmenting paths.

hopcroft_karp

Hopcroft-Karp maximum bipartite matching. Hopcroft-Karp maximum bipartite matching.

min_cut

Minimum s-t cut extracted from a completed max-flow computation. Minimum s-t cut from a completed max-flow computation.