A flow network: a directed graph with a source, sink, edge capacities, and edge flows.

Construct a Network with zero initial flows and pass it to pushRelabel to compute the maximum flow.

Edge capacity. Uses Rational for exact arithmetic, ensuring the Tide algorithm terminates correctly for arbitrary capacity values.

Map from edges to their capacities.

Edge flow. Same type as Capacity since flow values are rational.

The residual graph: the complete mutable state of the Tide algorithm.

Threaded through each tide iteration. Contains the underlying network, per-vertex and per-edge state, the neighbor map for O(log V) edge lookup, overflowing vertex sets, step counter, and the topology-change flag.

Per-vertex state in the residual graph.

ResidualVertex v l h x stores:

• v — vertex identifier
• l — level (BFS distance from source in original graph, constant)
• h — height (updated by globalRelabel each tide)
• x — excess flow (updated by push/pull operations)

Map from vertex id to its ResidualVertex state.

Per-edge state: original edge, capacity, and current flow (preflow).

ResidualEdge e c f: edge e with capacity c and flow f. A forward residual edge exists when f < c; a backward residual edge exists when f > 0.

Map from edge index to its ResidualEdge state.

For each vertex, maps forward neighbors and reverse neighbors to their edge indices in the graph's EdgeMap.

NeighborsMap ! v = (fwdMap, revMap) where:

• fwdMap ! w = index of edge (v, w) (forward neighbor)
• revMap ! u = index of edge (u, v) (reverse neighbor)

This provides O(log degree) edge-index lookup, replacing the original O(log E) lookup via Map Edge Int.

Overflowing vertices grouped by level. Keys are levels (BFS distance from source); values are sets of vertices at that level with positive excess.

This structure determines the iteration order for globalPush (ascending level = left fold) and globalPull (descending level = right fold).

Vertex height in the push-relabel framework. For source-side vertices: height = |V| + distance_from_source. For sink-side vertices: height = distance_from_sink.

Vertex excess: inflow - outflow. Positive excess means the vertex is overflowing and needs to push or pull flow.

Level: the shortest-path distance from the source in the original (not residual) graph. Constant throughout the algorithm. Determines the ordering of vertices in globalPush (left fold, ascending) and globalPull (right fold, descending).

Build the initial ResidualGraph from a Network.

Saturates all edges leaving the source (setting their flow equal to capacity), sets the source height to |V|, and initializes the overflowing set with all vertices that received flow from the source.

The topologyChanged flag is set to True so the first tide always runs globalRelabel.

Level of a vertex (shortest distance from source in original graph).

Excess of a vertex.

Height of a vertex.

Capacity of an edge.

Current flow on an edge.

O(log degree) edge index lookup via NeighborsMap.

Looks up the edge index of (u, v) by finding v in the forward neighbor map of u. Returns Nothing if the edge does not exist.

Net flow into the sink. This is the current flow value of the network. At termination, this equals the maximum flow.

Total flow into a vertex (sum of flows on incoming edges).

Total flow out of a vertex (sum of flows on outgoing edges).

Total capacity of all edges leaving the source. This is an upper bound on the maximum flow.

Push flow along a forward edge (u, v).

Preconditions (checked, returns Nothing if not met):

• height(u) = height(v) + 1 (flow goes downhill)
• Residual capacity c - f > 0 (edge is not saturated)
• excess(u) > 0 (source vertex has excess to push)

Pushes min(excess(u), c - f) units of flow. Updates the topologyChanged flag if the edge becomes saturated.

Pull flow along a reverse edge (u, v).

This is the dual of push: it decreases flow on edge (u, v) by moving excess from v back to u.

Preconditions (checked, returns Nothing if not met):

• height(v) = height(u) + 1 (pull goes uphill in the forward direction)
• flow(u, v) > 0 (there is flow to pull back)
• excess(v) > 0 (pulling vertex has excess)

Pulls min(excess(v), flow) units. Updates the topologyChanged flag if the edge becomes zero-flow.

Update the height of a vertex. Source and sink heights are never modified.

Update the excess of a vertex and maintain the overflowing index.

When excess transitions between zero and non-zero, the vertex is added to or removed from the Overflowing map at its level. Source and sink are excluded from the overflowing set.

Update the flow on an edge and track topology changes.

A topology change occurs when a forward residual edge appears or disappears (flow crosses the capacity boundary) or a backward residual edge appears or disappears (flow crosses zero). The topologyChanged flag is set to True (OR-ed) if such a change occurs.

Collect all vertices with positive excess.

Reconstruct the Network with final edge flows from the residual graph. Called when the algorithm terminates.

Compute distances from source and sink in the residual graph via BFS.

Returns (sourceDists, sinkDists) where:

• sourceDists: IntMap from vertex to BFS distance from source (traversing edges with residual capacity > 0 in reverse, and edges with flow > 0 forward)
• sinkDists: IntMap from vertex to BFS distance from sink (traversing edges with residual capacity > 0 forward, and edges with flow > 0 in reverse)

Used by globalRelabel to set vertex heights: source-side vertices get height = |V| + dist_from_source, sink-side vertices get height = dist_from_sink.

Compute the source-sink minimum cut from the residual graph.

Returns (S, T) where S is the set of vertices reachable from the source in the residual graph (excluding source and sink) and T is the complement. By the max-flow min-cut theorem, the total capacity of edges crossing from S to T equals the maximum flow.