graph_flow/lib.rs
1#![warn(missing_docs)]
2
3//! # graph-flow
4//!
5//! Maximum flow and bipartite matching algorithms for graph-rs.
6//!
7//! Flow algorithms require a **residual graph** — a mutable internal
8//! representation that tracks remaining capacity and sent flow on each edge.
9//! Because this requires mutable aliasing patterns that conflict with Rust's
10//! borrow checker when using the generic [`Graph`] trait directly, this crate
11//! defines its own index-based [`FlowGraph`] structure for flow computation.
12//!
13//! ## Algorithms
14//!
15//! | Module | Algorithm | Complexity |
16//! |---------------------|----------------------------------------|-----------------|
17//! | [`mod@flow_graph`] | Residual graph representation | — |
18//! | [`mod@ford_fulkerson`] | Ford-Fulkerson (DFS augmentation) | O(E · max_flow) |
19//! | [`mod@edmonds_karp`] | Edmonds-Karp (BFS augmentation) | O(V · E²) |
20//! | [`mod@min_cut`] | Min-cut from a completed max-flow | O(V + E) |
21//! | [`mod@hopcroft_karp`] | Hopcroft-Karp bipartite matching | O(E · √V) |
22//!
23//! ## Design note: why a separate `FlowGraph`?
24//!
25//! The residual graph needs to update both the forward edge **and** its
26//! corresponding reverse edge in a single pass. With Rust's borrow checker,
27//! mutating two elements of the same `Vec` simultaneously requires either
28//! index-based access (what we use here) or `unsafe`. Using indices is the
29//! idiomatic safe solution: we store the index of each edge's reverse in the
30//! adjacency list entry, giving O(1) residual updates with no aliasing.
31//!
32//! [`Graph`]: graph_core::Graph
33
34/// Edmonds-Karp maximum flow using BFS augmenting paths.
35pub mod edmonds_karp;
36/// Index-based flow graph (residual graph) used by all flow algorithms.
37pub mod flow_graph;
38/// Ford-Fulkerson maximum flow using DFS augmenting paths.
39pub mod ford_fulkerson;
40/// Hopcroft-Karp maximum bipartite matching.
41pub mod hopcroft_karp;
42/// Minimum s-t cut extracted from a completed max-flow computation.
43pub mod min_cut;
44
45pub use edmonds_karp::edmonds_karp;
46pub use flow_graph::FlowGraph;
47pub use ford_fulkerson::ford_fulkerson;
48pub use hopcroft_karp::hopcroft_karp;
49pub use min_cut::{min_cut, MinCut};