# tide-maxflow
A Rust implementation of the **Tide** max-flow algorithm — a push-pull-relabel
variant that uses global sweeps and O(1) array-based data structures.
> **Note:** This crate was AI-transpiled from the reference Haskell
> implementation in [algraph](https://github.com/tpapak/algraph)
> (`Data.Graph.AdjacencyList.PushRelabel.Pure`) and then manually reviewed,
> optimized, and validated against 12,000+ random graphs.
## Algorithm
Each iteration ("tide") consists of three phases:
1. **Global Relabel** — BFS from source and sink on the residual graph to compute
exact vertex heights.
2. **Global Pull** — Right-fold over vertices with excess (descending level),
pulling flow along reverse edges.
3. **Global Push** — Left-fold over vertices with excess (ascending level),
pushing flow along forward edges.
The algorithm terminates when net flow and the set of overflowing vertices are
unchanged between tides.
### Solver variants
| `max_flow` | Standard BFS-based tide solver |
| `max_flow_hybrid` | Full BFS on the first tide, then local relabeling until flow stalls |
| `max_flow_adaptive` | Starts with standard tides; switches to hybrid mode if not converged after 5 iterations |
Each variant has a `_timed` counterpart (e.g. `max_flow_timed`) that returns a
`TimedMaxFlowResult` with per-phase timing breakdowns.
### Optimizations
- Skips global relabel when no edge crossed a saturation boundary
- Precomputed level buckets
- Contiguous adjacency storage (CSR-like layout)
- Reused BFS buffers across tides
- Allocation-free convergence check via excess hash
## Usage
Add to your `Cargo.toml`:
```toml
[dependencies]
tide-maxflow = "0.1"
```
```rust
use tide_maxflow::max_flow;
let result = max_flow(4, 0, 3, &[
(0, 1, 10),
(0, 2, 10),
(1, 3, 10),
(2, 3, 10),
]);
assert_eq!(result.flow, 20);
```
The input is a list of `(from, to, capacity)` tuples with `i64` capacities.
Vertices are `0`-indexed. The result includes the max flow value, iteration
count, and per-edge flow decomposition.
## Benchmarks
97 DIMACS graphs across 11 families (layered, grid, chains, bipartite, random,
washington, vision2d, vision3d, rfim2d, rfim3d, Waterloo vision benchmarks).
Single-threaded, Apple Silicon, `--release`. All solver phases ran sequentially.
Compared against [Google OR-Tools](https://developers.google.com/optimization)
(C++ push-relabel), and [HPF](https://riot.ieor.berkeley.edu/Applications/Pseudoflow/maxflow.html)
(C, Hochbaum Pseudoflow -- the best serial max-flow on vision graphs per
[Jensen et al. 2022 TPAMI](https://doi.org/10.1109/TPAMI.2022.3174373)).
**[Full interactive benchmark report (HTML)](benchmark-report.html)**
### Tide vs HPF (Pseudoflow)
Tide wins **63 of 87** comparable graphs. Ratio = Tide / HPF (< 1 = Tide faster).
| layered (15) | **0.01x** | 15/15 | **Tide (100x faster)** |
| grid (11) | **0.07x** | 11/11 | **Tide (15x faster)** |
| chains (9) | **0.07x** | 9/9 | **Tide (14x faster)** |
| washington (4) | **0.24x** | 4/4 | **Tide (4x faster)** |
| random (15) | **0.13x** | 15/15 | **Tide (8x faster)** |
| bipartite (9) | **0.10x** | 7/9 | **Tide (10x faster)** |
| vision2d (4) | 1.4x | 1/3 | HPF |
| rfim2d (4) | 12.2x | 0/4 | HPF |
| waterloo (9) | 6.7x | 0/9 | HPF |
### Tide vs OR-Tools (C++ Push-Relabel)
Tide wins **26 of 87** comparable graphs. Ratio = Tide / OR-Tools.
| layered (15) | **0.92x** | 9/15 | **Tide (1.1x faster)** |
| grid (11) | 1.02x | 7/11 | Tied |
| chains (9) | **0.89x** | 5/9 | **Tide (1.1x faster)** |
| random (15) | 1.7x | 2/15 | OR-Tools |
| bipartite (9) | 2.1x | 2/9 | OR-Tools |
| vision2d (4) | 6.4x | 0/4 | OR-Tools |
| waterloo (9) | 6.7x | 0/9 | OR-Tools |
### Selected results
Times in milliseconds (lower is better).
| `layered_1000x1000` | 1.0M | 3.0M | **94** | 183 | 10,421 |
| `layered_5000x1000` | 5.0M | 15.0M | **358** | 560 | 227,647 |
| `layered_3000x3000` | 9.0M | 27.0M | **700** | 1,284 | 305,944 |
| `layered_70000x1000` | 70.0M | 210.0M | **6,836** | - | - |
| `grid_1000x1000` | 1.0M | 2.0M | **92** | 134 | 550 |
| `grid_4500x4500` | 20.3M | 40.5M | **3,359** | 2,332 | 13,709 |
| `chains_5000x1000` | 5.0M | 5.0M | **613** | 634 | 902 |
| `bipartite_1000x1000` | 2K | 1.0M | 555 | **21** | 97 |
| `random_10000_5pct` | 10K | 5.0M | 919 | **299** | 518 |
| `vision2d_1000x1000` | 1.0M | 6.0M | 1,006 | **227** | 920 |
| `rfim2d_1000` | 1.0M | 5.0M | 13,985 | **1,549** | **1,680** |
### Key findings
- **Tide dominates on structured graphs**: 10-100x faster than HPF, competitive
with OR-Tools on layered, grid, chains, and random families.
- **OR-Tools and HPF win on vision/RFIM graphs**: graphs with t-links at every
vertex or random capacities require many tides (20-400+), where the global
BFS sweep becomes the bottleneck.
- **Tide count predicts performance**: graphs converging in 2-5 tides are
Tide's sweet spot; graphs needing >30 tides favor local-operation solvers.
- **Scales to 210M edges**: `layered_70000x1000` solves in 6.8s (3 tides).
### Running benchmarks
```bash
cargo bench # Criterion benchmarks (Tide vs rs-graph)
cargo build --release
./target/release/solve_dimacs FILE.max # standard
./target/release/solve_dimacs --adaptive FILE.max # adaptive
```
## Complexity
### Per-tide cost
Each tide performs BFS + a full sweep over all edges:
```
O(V + E) per tide
```
### Number of tides
| Polynomial capacities | O(1) | O(V + E) |
| Sub-exponential (base < 2) | O(V) | O(VE) |
| Exponential (base >= 2) | O(V^2) | O(V^2 E) |
**Worst case**: O(V^2) tides, giving **O(V^2 E)** total.
Achieved only by a specific pathological family with exponentially-varying
capacities (base >= 2).
**Practical case**: O(V) tides on all tested graph families with
polynomially-bounded capacity ratios, giving **O(VE)** total — matching
Orlin's optimal strongly polynomial bound.
The O(V) tide bound for sub-exponential capacities is empirically robust
but remains an open conjecture. The gap between the proven O(V^2) worst case
and the empirical O(V) is entirely in the stalling tide analysis.
### Comparison with classical algorithms
| Edmonds-Karp | O(V E^2) |
| Dinic | O(V^2 E) |
| Push-relabel (highest-label) | O(V^2 sqrt(E)) |
| Orlin | O(V E) |
| **Tide (worst case)** | **O(V^2 E)** |
| **Tide (practical)** | **O(V E)** |
### Termination proof
The algorithm is proven to terminate for all networks with positive
capacities. The proof uses a potential function argument showing that
(1) net flow is non-decreasing, (2) no flow cycles are possible within
a stalling phase, and (3) the finite state space forces convergence.
See the [complexity report](https://github.com/tpapak/tide-maxflow/blob/main/docs/complexity-report.md)
for the full proof and empirical verification.
## Rust ecosystem
Three other Rust crates provide max-flow solvers:
| [petgraph](https://crates.io/crates/petgraph) | Dinic, Ford-Fulkerson (Edmonds-Karp) | O(V^2 E), O(V E^2) | Graph type + method |
| [rs-graph](https://crates.io/crates/rs-graph) | Edmonds-Karp, Dinic, push-relabel | O(V E^2), O(V^2 E), O(V^2 sqrt(E)) | Graph trait + function |
| [pathfinding](https://crates.io/crates/pathfinding) | Edmonds-Karp | O(V E^2) | Edge list + function |
| **tide-maxflow** | **Tide (push-pull-relabel)** | **O(V^2 E) worst, O(VE) practical** | **Edge list + function** |
`tide-maxflow` differs from these in several ways:
- **Performance**: Tide is significantly faster than all other Rust max-flow
implementations across tested graph families (layered, grid, bipartite,
random, chains). The CSR-based flat-array layout and global-sweep structure
give it a substantial constant-factor advantage over the linked-list and
adjacency-map representations used by other crates.
- **Algorithm**: The only push-relabel variant available as a standalone Rust
crate. `rs-graph` has a push-relabel implementation, but it is part of a
larger graph library.
- **No graph type required**: Takes a plain `&[(usize, usize, i64)]` edge list.
No need to construct a graph data structure first.
- **CSR-based internals**: Flat arrays with paired forward/reverse edges for
cache locality, rather than adjacency-list or linked-list representations.
- **Multiple solver strategies**: Standard, hybrid, and adaptive variants with
optional per-phase timing instrumentation.
## Testing
Correctness is validated by comparing all three solver variants (standard,
hybrid, adaptive) against the reference Dinic implementation from the
[rs-graph](https://crates.io/crates/rs-graph) crate on thousands of random
graphs with varying size, density, and capacity ranges:
```bash
cargo test
```
The test suite (`tests/random_comparison.rs`) generates 5,000 seeded random
graphs (4-30 vertices, sparse to dense, capacities 1-1000) and asserts that
every Tide variant produces the same max flow value as rs-graph's Dinic solver.
## Binaries
The crate includes two binaries:
- **`solve_dimacs`** -- Reads a DIMACS max-flow file and solves it. Supports
`--adaptive` and `--hybrid` flags.
- **`gen_graphs`** -- Generates random test graphs in DIMACS format.
## License
LGPL-3.0-or-later