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 (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

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:

[dependencies]
tide-maxflow = "0.1"

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 (C++ push-relabel), and HPF (C, Hochbaum Pseudoflow -- the best serial max-flow on vision graphs per Jensen et al. 2022 TPAMI).

Full interactive benchmark report (HTML)

Tide vs HPF (Pseudoflow)

Tide wins 63 of 87 comparable graphs. Ratio = Tide / HPF (< 1 = Tide faster).

Tide vs OR-Tools (C++ Push-Relabel)

Tide wins 26 of 87 comparable graphs. Ratio = Tide / OR-Tools.

Selected results

Times in milliseconds (lower is better).

| Graph | |V| | |E| | Tide (ms) | OR-Tools (ms) | HPF (ms) | |:---|---:|---:|---:|---:|---:| | 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

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

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

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 for the full proof and empirical verification.

Rust ecosystem

Three other Rust crates provide max-flow solvers:

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 crate on thousands of random graphs with varying size, density, and capacity ranges:

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