Tide Max Flow: Benchmark Report
Solvers: Tide Standard (Rust), Tide Adaptive (Rust), Google OR-Tools (C++ push-relabel), HPF (C, Hochbaum Pseudoflow).
Graph pool: 97 DIMACS graphs across 11 families: layered, grid, chains, bipartite, random, washington, vision2d, vision3d, rfim2d, rfim3d, and Waterloo vision benchmarks. Graphs range from 10 edges to 210M edges.
Hardware: Apple Silicon, single-threaded, --release builds. All phases ran sequentially (no CPU contention).
Timing: Tide: internal Instant (min of 3 runs for adaptive, 1 run for standard). OR-Tools/HPF: perf_counter (min of 3 runs).
Correctness: All max flow values match exactly across all solvers on all 97 graphs.
1. Summary
Tide is a push-relabel variant that operates in global tides: each tide performs
a full BFS to compute exact distance labels, then a forward push sweep followed by a backward pull sweep.
Structured graphs (layered, grid, chains) converge in 2–5 tides. Dense or vision-style graphs
require 20–400+ tides.
2. Standard vs Adaptive Tide
Adaptive mode runs 5 standard BFS tides, then switches to local relabeling (skipping full BFS)
until flow stalls. This helps on graphs that need many tides (bipartite, random, washington) but
hurts on vision/RFIM graphs where local relabeling generates extra steps without reducing BFS cost.
2.1 By Family
Adaptive is faster on combinatorial graphs: bipartite 2x, random 1.7x, washington 2.5x faster.
Standard is faster on vision/RFIM graphs: adaptive inflates step count 2–7x on
vision and RFIM families, making it 1.4–1.9x slower. For these graphs, use standard mode.
2.2 All Graphs: Adaptive vs Standard
3. Tide vs OR-Tools (C++ Push-Relabel)
OR-Tools uses a highest-label push-relabel implementation in C++ with pybind11 bindings.
We compare Tide Standard on all 97 graphs (including graphs >1 GB that exceed OR-Tools' file size limit).
3.1 By Family
3.2 Head-to-Head: All Graphs
3.3 Scaling: Large Graphs
4. Tide vs HPF (Pseudoflow)
HPF (Hochbaum Pseudoflow, lowest-label FIFO) is the best-performing serial max-flow algorithm on
vision graphs per Jensen et al. (2022 TPAMI). It solves the minimum cut via pseudoflows
without computing explicit flows. We compare Tide Standard against HPF.
4.1 By Family
4.2 Head-to-Head: All Graphs
5. Tide Count as Performance Predictor
Tide count predicts everything. Graphs that converge in ≤5 tides are Tide's sweet spot:
10–100x faster than HPF, competitive with OR-Tools. Graphs requiring >30 tides are where
OR-Tools and HPF win. The crossover is sharp and predictable from graph structure.
6. Full Results Table
7. Conclusions
1. Tide dominates on structured graphs.
- Layered graphs: Tide 1.1x faster than OR-Tools, 100x faster than HPF (geo mean over 15 comparable graphs).
- Grid graphs: tied with OR-Tools, 15x faster than HPF.
- Chains: tied with OR-Tools, 14x faster than HPF.
- The advantage comes from Tide's global BFS sweep converging in 2–5 tides on these structures,
yielding effectively O(V+E) total work.
2. OR-Tools and HPF win on vision and physics graphs.
- Vision grids (t-links at every vertex): OR-Tools 6–7x faster, HPF 1.4–2x faster.
- RFIM lattices (PBC + random capacities): OR-Tools 5–14x faster, HPF 5–20x faster.
- Waterloo real vision benchmarks: OR-Tools 7x faster, HPF 7x faster.
- Root cause: these graphs require 20–400+ tides, each doing a full O(V+E) BFS.
OR-Tools' local push-relabel with gap heuristics and HPF's pseudoflow method avoid this repeated global work.
3. Tide count is the universal predictor.
- ≤5 tides: Tide is 10–100x faster than HPF, competitive with OR-Tools.
- 5–30 tides: competitive range, depends on graph size and density.
- >30 tides: OR-Tools and HPF win, gap grows with tide count.
- Tide count depends on graph structure, not size: a 210M-edge layered graph needs 3 tides,
while a 50K-edge RFIM lattice needs 150+.
4. Adaptive mode is not universally better.
- Adaptive helps on bipartite (2x), random (1.7x), washington (2.5x) by skipping BFS via local relabeling.
- Adaptive hurts on vision (1.4x slower) and RFIM (0.7–1.9x slower) because local relabeling
inflates step count 2–7x without proportional BFS savings.
- Recommendation: use standard mode as default; switch to adaptive only for dense combinatorial graphs.
5. Tide is a strong general-purpose max-flow algorithm.
- Pure Rust, single-threaded, no unsafe code, no external dependencies.
- Wins 63 of 87 graphs against HPF (the SOTA vision solver) by geometric mean 5.4x overall.
- Wins 26 of 87 graphs against OR-Tools, losing primarily on vision/RFIM families.
- Scales to 210M edges (layered_70000x1000: 6.0s, layered_10000x7000: 6.9s).
- Best suited for network flow, combinatorial optimization, and any application where
graph structure yields low tide counts.
8. Methodology
- Tide Standard:
solve_dimacs --dir graph-pool/. Rust --release, internal Instant timing, 1 run on all 97 graphs.
- Tide Adaptive:
solve_dimacs --adaptive --dir graph-pool/. Min of 3 runs on all 97 graphs. Warmup: 5 standard BFS tides before switching to local relabeling. Stall detection: bail after 2 consecutive tides without flow increase.
- OR-Tools: Google OR-Tools 9.15,
SimpleMaxFlow (C++ push-relabel via pybind11). perf_counter around solve(). Min of 3 runs. Graphs >1 GB excluded (Python memory limits).
- HPF: Hochbaum Pseudoflow v3.23, lowest-label FIFO (
pseudo_fifo). C, reads DIMACS from stdin. perf_counter around subprocess call (includes ~2 ms startup overhead). Min of 3 runs. Graphs >1 GB excluded.
- Graph pool: 97 DIMACS files across 11 families. Synthetic: layered DAGs (up to 210M edges), open-boundary grids, chains, complete bipartite, Erdős–Rényi random, washington (stochastic). Vision: 2D/3D grids with bidirectional n-links + s/t t-links. Physics: 2D/3D RFIM lattices with periodic boundary conditions. Real: Waterloo vision benchmarks (liver, adhead, babyface, bone, LB07-bunny).
- Hardware: Apple M-series Silicon, single-threaded. All solver phases ran sequentially with no CPU contention.
- Correctness: All max flow values verified identical across all solvers on all graphs.