Crate tide_maxflow 

Tide Flow

Implementation of the Tide max flow algorithm — a push-pull-relabel variant.

The algorithm performs global sweeps (BFS relabeling, then global pull, then global push) in each iteration (“tide”). It uses O(1) array-based data structures with i64 capacities for maximum performance.

Algorithm Overview

Each tide consists of three phases:

1. globalRelabel — BFS from source and sink on the residual graph to compute exact vertex heights.
2. globalPull — Right-fold over overflowing vertices (descending level), pulling flow on reverse edges.
3. globalPush — Left-fold over overflowing vertices (ascending level), pushing flow on forward edges.

Terminates when net flow and the overflowing set are unchanged between tides.

Optimizations

• Skips globalRelabel when no edge crossed a saturation boundary.
• Precomputed level buckets (levels are constant).
• Contiguous adjacency storage (CSR-like head/next arrays).
• Reused BFS buffers across tides.
• Allocation-free convergence check via excess hash.

Structs

MaxFlowResult

Result of the Tide max flow computation.

PhaseTiming

Per-phase timing breakdown (in microseconds) for profiling.

TimedMaxFlowResult

Result with timing breakdown.

Functions

max_flow

Compute the maximum flow in a network using the Tide algorithm.

max_flow_adaptive

Compute max flow using adaptive Tide.

max_flow_adaptive_timed

Compute max flow using adaptive Tide with per-phase timing.

max_flow_hybrid

Compute max flow using the hybrid Tide algorithm.

max_flow_hybrid_timed

Compute max flow using the hybrid Tide algorithm with timing.

max_flow_timed

Compute max flow with per-phase timing instrumentation.