Maximum Flow

By the end of this lesson you will be able to model a real problem as a flow network, build its residual network, and run fordFulkerson and edmondsKarp by hand; read the minimum cut straight off the final residual network (max-flow min-cut); turn bipartite matching into a flow problem; and trace the push-relabel family (push, relabel, genericPushRelabel, relabelToFront) using heights and excess. Every animation is computed by a real implementation running in your browser, and you can feed most of them your own network.

0. What is a flow?

Picture a city water system. A big pumping station (the source, called s) pushes water through a web of pipes to a town (the sink, called t). Each pipe can carry only so many litres per minute (its capacity). Junctions (the other vertices) have no tank: whatever water flows into a junction must flow out again. The question of this whole chapter is: what is the largest amount of water per minute you can send from s to t? That amount is the maximum flow. Swap water for trucks on roads, packets on network links, or current in wires and nothing changes.

Words you will meet: a graph is dots (vertices) joined by arrows (edges); a directed edge u→v only lets things travel from u to v. An algorithm is a fixed recipe of steps. This lesson uses only these ideas plus simple addition, so if you can add and take the minimum of a few numbers you can follow every step.

A first tiny example. Two pipes in a row: s→a holds at most 3 litres a minute and a→t holds at most 2. The junction a has no tank, so whatever enters must leave, and at most 2 litres per minute can travel from s to t. The narrow pipe is the bottleneck. Every algorithm in this chapter is a cleverer way of finding bottlenecks in bigger maps.

The maximum flow is not "the sum of all capacities" and not "the capacity of the biggest pipe". In the example above 3 + 2 = 5 and 3 are both wrong; the answer is 2, decided by the tightest place on the way.

Whole numbers versus fractions. The definitions allow any non-negative real capacities, but the running-time bounds and the integrality theorem in this lesson are stated for whole-number capacities. With irrational capacities and unlucky path choices Ford-Fulkerson is not guaranteed to converge, while Edmonds-Karp (section 3) still stops because its bound does not depend on the capacity values at all.

A flow network is a directed graph with a capacity on each edge, one source s and one sink t. A flow puts a number on each edge without exceeding the capacity and without creating or losing water at junctions. The maximum flow is the largest such total leaving s.

The maths as code. The tiny two-pipe example as code: on a chain of pipes the maximum flow is the smallest capacity.

1. Flow networks

A flow network is the pipe map: a directed graph where every edge (u,v) has a capacity c(u,v) ≥ 0 (its pipe size). A flow assigns every edge a number f(u,v), "how much water is really flowing", obeying two rules: capacity constraint 0 ≤ f(u,v) ≤ c(u,v) (a pipe cannot carry more than its size, nor negative water) and flow conservation (at every vertex except s and t, total flow in = total flow out). The value of a flow, written |f|, is the net amount leaving the source: total flow out of s minus total flow into s.

We label each edge f/c in the pictures. Our running example is a small pumping network: source s, sink t, four junctions a, b, c, d and nine pipes. Its maximum flow is 24, and you will reproduce that number in the first animation of every algorithm below.

Small example, checked by hand. Edges s→a 4/5, a→b 3/3, a→t 1/2, b→t 3/3 (each written f/c). Capacity constraint: every flow is at most its capacity. Conservation at a: 4 flows in and 3 + 1 = 4 flow out. At b: 3 in, 3 out. The value is |f| = 4 (out of s), and indeed 1 + 3 = 4 also arrives at t.

Two housekeeping rules

No antiparallel edges. This lesson does not allow both u→v and v→u, because the residual network (next section) would then be ambiguous. Fix: split one of them through a new helper vertex u': replace u→v by u→u' and u'→v, both with the old capacity. The maximum flow value does not change. The custom-input player in the Ford-Fulkerson section does this automatically, and tells you when it happens.
One source, one sink. Several sources or sinks are handled by adding a "super source" joined to every source by an edge of capacity ∞ (and symmetrically a super sink).

Flow conservation does not apply at s and t: the source only sends out and the sink only receives. Also, f(u,v) is a number attached to an edge, not the capacity: an edge labelled 5/12 carries 5 units and could take 7 more.

Why the value can be measured at either end. Add up the conservation equations of all vertices except s and t: everything cancels except the net flow out of s and the net flow into t, so the two are equal. That is why |f| may be defined as the net flow leaving s and equally read off at t. The definition uses net flow so that an edge entering s (legal in general) is subtracted.

A flow is legal exactly when (1) 0 ≤ f(u,v) ≤ c(u,v) on every edge and (2) flow in = flow out at every vertex except s and t. Its value |f| is the net flow out of s, which equals the net flow into t.

The maths as code. The two rules of a legal flow and the value |f|, measured at the source and at the sink, as code (these use the FlowGraph class shown in the next section).

The housekeeping rule as code. A pair u→v and v→u is not allowed; this builder splits the later edge of each such pair through a helper vertex, so the maximum flow value is unchanged.

2. The Ford-Fulkerson method

Start with all pipes empty. Look for any route from s to t where every pipe still has room, and pour as much as the tightest pipe on that route allows. Repeat until no such route exists. The clever part: the "room" you look for is measured in the residual network, which also contains undo arrows. If a pipe already carries 5 units, the residual network gets a reverse arrow of capacity 5, meaning "you may take back up to 5 units from this pipe and send them another way". Without undo arrows you could paint yourself into a corner.

Residual network and augmenting paths

Residual capacity of an ordered pair: cf(u,v) = c(u,v) − f(u,v) if (u,v) is an edge (room left), plus f(v,u) if (v,u) is an edge (flow you can cancel). The residual network Gf keeps every pair with cf > 0.
An augmenting path is a simple path from s to t in Gf. Its bottleneck cf(p) is the smallest residual capacity along it. Pushing cf(p) units along p raises |f| by exactly that amount (call this Fact A).

In the animations below a dashed amber arrow is a residual back-edge: it appears on any edge that carries flow and shows how much of that flow could be undone. The method itself is only four lines; the concrete algorithm fills in how the path is found.

residualNetwork(G, f) — three examples

The residual network is usually given as a formula; here the formula is written as a loop so you can watch each edge of G turn into up to two residual edges. Example 1 (normal): a sample flow of value 17 on the running network, and its residual network.

Example 2 (edge case, zero flow): with no flow at all, nothing can be cancelled, so Gf is a copy of G.

Example 3 (custom input): type edges as u->v:capacity/flow. The page checks that your flow obeys the capacity constraint and conservation, and refuses antiparallel pairs (split them as described in section 1).

A back-edge in Gf is an accounting arrow, not a new pipe: pushing along it means "take back some of the water I already sent along the real edge". Forgetting that a full edge still leaves a back-edge (and an empty edge leaves no back-edge) is the most common mistake when drawing Gf by hand.

augmentOnce(G, f, s, t) — three examples

fordFulkerson hides one step inside line 3: finding a path in Gf and then pushing along it. This procedure does exactly one round with a breadth-first search, so you can study the search, the bottleneck and the augmentation without the outer loop. Example 1 (normal): the sample flow of value 17 is not maximum; watch the search find a path and add its bottleneck.

Example 2 (edge case, no augmenting path): start from a maximum flow (value 24). The search visits everything it can, never reaches t, and returns none; the visited set is the S side of a minimum cut.

Example 3 (custom input): same u->v:capacity/flow format as above. The default has a saturated edge, so the search must route around it.

Pushing cf(p) units along an augmenting path p always gives a legal flow of value |f| + cf(p) (Fact A). If the search returns none the flow is maximum (max-flow min-cut theorem, section 4). Cost of one call: O(V+E) for the search plus O(V) for the path.

The method leaves two things open: how to find the path, and whether the loop ever ends. Here is the concrete fordFulkerson, with the path found by a depth-first search (walk one branch as deep as possible before backing up). Watch each animation: the caption says which path is found, what the bottleneck is and why, and how each edge's flow changes.

fordFulkerson(G, s, t) — three examples

Example 1 (normal): the running network (6 vertices, 9 pipes, maximum flow 24).

Example 2 (edge case, no augmenting path at all): the sink cannot be reached from the source, so the loop body never runs and the answer is 0.

Example 3 (custom input, prefilled with antiparallel edges): the default text contains both a→b and b→a; the page splits the second one through a helper vertex, then runs fordFulkerson. Edit the edge list (format u->v:capacity, comma separated; the source must be called s and the sink t).

fordFulkerson is a method whose speed depends on how the path is chosen. "It always terminates" is only true for whole-number capacities, and "it is fast" is not true in general: its bound O(E·|f*|) grows with the capacity values, not just with the size of the graph, so a tiny network with huge capacities can be slow.

Why the running time can be bad. If augmenting paths are chosen unluckily, a network with one tiny "crossing" edge forces the algorithm to add just 1 unit per round, alternating across the crossing edge. The table below is computed by real code right now for the four-vertex network s→x:C, s→y:C, y→x:1, x→t:C, y→t:C: an adversarial path order versus BFS.

Loop-invariant idea for correctness: after every round f is still a legal flow (conservation and capacity hold, because we only push along residual capacity), and its value strictly increases. When the loop stops there is no augmenting path, which is exactly the condition of the max-flow min-cut theorem below.

fordFulkerson with integer capacities always terminates, and the loop runs at most |f*| times (each augmentation adds at least 1). Each round costs O(E) with an adjacency list, so the total is O(E·|f*|). Integrality theorem: with integer capacities the result uses only whole-number flows.

Dart implementation

The shared data structure. Every Dart panel below works on this small class: a FEdge holds one edge with its capacity and flow, and FlowGraph.cf(u, v) is the residual capacity.

The running example. The pumping network, built with that class (its maximum flow is 24).

residualNetwork and augmentOnce first (they are used by everything below). The Dart augmentOnce scans neighbours in the order the edges were added, so on a tie it may pick a different shortest path than the page's animation; the flow value it reaches is the same.

Input size → what is feasible: V ≤ 1000 and E ≤ 10⁴ → building Gf costs Θ(V+E) = about 10⁴ steps (instant); with a V × V matrix, V = 1000 means 10⁶ cells, still fine.

Input size → what is feasible: one search costs O(V+E); E = 10⁶ edges → about 10⁶ steps, instant.

The maths as code. Fact A as code: after augmenting along p the flow is still legal and |f| grew by exactly cf(p).

fordFulkerson. Indexing note: the pseudocode writes f(u, v) for the flow on an edge; the Dart port keeps a FEdge object per edge with a mutable flow field and looks residual capacity up through cf(u, v). Vertices are strings, so nothing here is array-indexed (the matrix-based solutions in the question bank are 0-indexed like every Dart list).

The method as code. fordFulkersonMethod with the path finder as a parameter (DFS gives fordFulkerson, BFS gives edmondsKarp).

The maths as code. The O(E·|f*|) bound made visible: on the trap network an unlucky path order needs 2C rounds, Edmonds-Karp needs 2.

Input size → what is feasible: E = 10⁴ and |f*| ≤ 10⁴ → E·|f*| = 10⁸ is fine; capacities up to 10⁶ (|f*| ≈ 10⁷) → 10¹¹ steps, too slow: use Edmonds-Karp or push-relabel.

3. Edmonds-Karp: choose the shortest augmenting path

fordFulkerson says "any route with room". edmondsKarp says "always take the route with the fewest pipes", found by breadth-first search (BFS: explore all vertices 1 step from s, then 2 steps, then 3 steps, like ripples spreading in a pond). That single change turns an algorithm whose speed depends on the capacity numbers into one whose speed depends only on the graph's size.

Note: edmondsKarp is fordFulkerson with the path found by BFS; the panel below shows the same eight lines with line 3 changed.

edmondsKarp(G, s, t) — three examples

Example 1 (normal): the running network again. Compare the paths chosen here with the DFS paths of the previous section: both reach 24.

Example 2 (edge case, unit capacities): every edge has capacity 1, so every augmentation adds exactly 1 unit and every used edge becomes full.

Example 3 (custom input, prefilled with the trap network): the network that costs an unlucky Ford-Fulkerson 2C rounds finishes in two BFS rounds.

BFS finds paths shortest by number of edges, not by total capacity. A short path with a tiny bottleneck is still chosen before a long fat one.

Why shortest paths give a bound (sketch of the distance fact). Let δf(s,v) be the fewest edges from s to v in Gf. Augmenting along a shortest path only adds back-edges that point from a farther vertex to a nearer one, so no vertex ever gets closer to s. The bottleneck edge of an augmentation (the critical edge) disappears; for that same edge to be critical again its far end must first have moved at least 2 steps further away. Distances are at most V, so each of the E edges is critical at most about V/2 times, giving O(VE) augmentations.

Edmonds-Karp bound. Edmonds-Karp performs O(V·E) augmentations, so it runs in O(V·E²) time. Key facts: shortest-path distances δf(s,v) in the residual network never decrease; each augmentation makes at least one critical edge (the bottleneck edge) vanish; and one edge can be critical at most V/2 times because its distance from s must grow by at least 2 between two turns as critical.

Dart implementation

The Dart port literally reuses fordFulkerson and only swaps the path finder.

The maths as code. The distance fact (distances δ_f(s, v) never decrease) and the augmentation bound (at most E·(V−2)) checked while the algorithm runs.

Input size → what is feasible: V = 100, E = 10³ → V·E² = 10⁸ worst case, fine; V = 1000, E = 10⁴ → 10¹¹ worst case: use push-relabel (V²E = 10¹⁰ worst case, usually far less) or Dinic.

4. Cuts and the max-flow min-cut theorem

Imagine drawing a fence across the pipe map that separates the pumping station from the town. Only pipes crossing the fence from the station side to the town side matter, and their total capacity is a hard ceiling on how much water can get across. Every possible fence gives a ceiling; the lowest ceiling is the minimum cut. The stunning theorem: the maximum flow equals the lowest ceiling.

Formally a cut (S,T) splits the vertices into two groups with s ∈ S and t ∈ T; its capacity c(S,T) adds up c(u,v) for edges going from S to T only (edges from T back to S do not count). Cut-flow fact: for any flow, the net flow across any cut equals |f|. Therefore Weak duality: |f| ≤ c(S,T) for every flow and cut.

The max-flow min-cut theorem. These are equivalent: (1) f is a maximum flow; (2) Gf has no augmenting path; (3) |f| = c(S,T) for some cut. The proof that (2) implies (3) is constructive and it is exactly the procedure below: let S be everything still reachable from s in Gf and T the rest. Every edge from S to T must be full and every edge from T to S empty (otherwise Gf would have another arrow leaving S), so c(S,T) = |f|.

The proof only hints at this search; here it is spelled out as its own procedure so you can watch it. The animation runs a breadth-first reachability search in the final residual network (a maximum flow is computed first by Edmonds-Karp).

minCutFromFlow(Gf, s) — three examples

Example 1 (normal): the running network; the cut capacity comes out at 24.

Example 2 (edge case, zero flow): nothing can reach t, so S is everything s can reach and the min cut has capacity 0.

Example 3 (custom input, prefilled with a network that has two different minimum cuts): the search reports only one of them (the one closest to s); the other has the same capacity.

enumerateCuts(G, f) — the theorem cut by cut

To see the theorem, this visual lists every cut of a small network (a teaching procedure) and, for each one, its capacity and the net flow crossing it. Two facts will hold on every line: the net flow across the cut is always the same number |f| (cut-flow fact), and no cut is cheaper than that (weak duality). The cheapest cut is exactly as cheap as the flow: max-flow equals min-cut. Example 1 (normal): the running network with its 16 cuts.

Example 2 (edge case, no flow at all): the sink cannot be reached, so the maximum flow is 0. Edges that come back from T to S are ignored in capacity, and the cut with c(S,T) = 0 exists.

Example 3 (custom input): at most 4 vertices besides s and t, so at most 16 cuts are listed.

Only edges that go from S to T add to the capacity of a cut. An edge that goes from T back to S counts for nothing, even if it is huge, but the flow on it is subtracted when you compute the net flow across the cut. Also, a network can have several minimum cuts: the search from s always finds the one with the smallest S.

Running time: one BFS/DFS, O(V+E), after the flow is known. Finding all minimum cuts is a different (harder to state) problem; the reachability cut is the one with the smallest possible S.

Max-flow min-cut in one line: the biggest flow you can push equals the cheapest cut you can draw. When no augmenting path is left, the vertices still reachable from s in Gf form the S side of a cut whose capacity equals |f|.

Dart implementation

enumerateCuts tries every subset of the junctions (a bit mask), so it takes Θ(2^(V−2)·E) time; it is a teaching device and a brute-force checker, not a practical algorithm. Vertices are strings, so there is no 1-based to 0-based shift; bit i of the mask says whether junction i joins S.

The maths as code. The cut-flow fact, weak duality (|f| ≤ c(S,T)) and the max-flow min-cut theorem checked on every cut of a small network.

Input size → what is feasible: minCutFromFlow is one search, O(V+E), after the flow is known; enumerateCuts only for V−2 ≤ 20 junctions (2²⁰ ≈ 10⁶ cuts, each scanning E edges).

5. Maximum bipartite matching

A bipartite graph has two groups of dots (say people on the left, jobs on the right) and lines only between the groups ("this person can do this job"). A matching hands out jobs so that nobody gets two jobs and no job gets two people. You want as many people employed as possible. Trick: add a super source that feeds one unit to every person and a super sink that collects one unit from every job. A flow of 1 through person→job is "assign this person to that job". The maximum flow is the maximum matching.

Construction: add s and t; edges s→u (capacity 1) for every left vertex, v→t (capacity 1) for every right vertex, and every original edge directed left to right with capacity 1. Matching = flow: the max matching size equals the max flow value (integrality theorem: with unit capacities every edge carries 0 or 1). Time O(V·E), since the flow is at most V and each augmentation costs O(E).

Small example. Ann can do jobs J1 and J2, Bob can only do J1. Network: s→Ann, s→Bob, Ann→J1, Ann→J2, Bob→J1, J1→t, J2→t, all capacity 1. The maximum flow is 2: Ann takes J2 and Bob takes J1. If the search first sent Ann to J1, the second augmenting path would use the dashed back-edge of Ann→J1 to move her to J2.

maximumBipartiteMatching(G) — three examples

Example 1 (normal): four people, four jobs, a perfect matching exists. Look for the round where the augmenting path uses a dashed back-edge: that person is re-assigned to make room.

Example 2 (edge case, Hall's condition fails): two people can only do the same one job, so no perfect matching exists; the final cut names the guilty group.

Example 3 (custom input): type pairs like l1-r1, l1-r2, l2-r1 (left name, dash, right name; names must not be s or t).

Two easy slips. First, the edges of the flow network are directed left to right only, otherwise a flow could wander back through a person. Second, the capacity-1 edges at s and t are what stop one person taking two jobs or one job going to two people; without them you would be counting something else.

Why a whole-number flow is a matching, and how to be faster. By the integrality theorem an integer-capacity network has an integer maximum flow, so every edge carries 0 or 1. Conservation at a person with capacity-1 inflow forces at most one outgoing edge to be used, and the same holds for each job, so the used middle edges form a matching whose size is |f|. Hopcroft-Karp improves the bound to O(√V·E) by augmenting along a whole batch of shortest, vertex-disjoint paths per round.

Hall's theorem: the left side can be fully matched if and only if every subset A of left vertices has at least |A| neighbours. When the algorithm gets stuck, the left vertices reachable in the residual network are such a violating subset.

Dart implementation

The maths as code. Matching = flow and the integrality theorem as code: unit capacities give 0/1 flows, the used edges form a matching, and the number of rounds equals the matching size.

The maths as code. Hall's theorem as code (every subset A needs |N(A)| ≥ |A|), and the violating subset that the stuck flow names.

Input size → what is feasible: |L|, |R| ≤ 200 and pairs ≤ 4·10⁴ → V·E = 400·4·10⁴ = 1.6·10⁷ steps, fine; |L|, |R| ≥ 10⁵ → use Hopcroft-Karp, O(√V·E).

6. Push-relabel algorithms

Ford-Fulkerson looks at the whole network to find one full route. Push-relabel works locally like water finding its own level. Every vertex stands on a tower of some height. The source stands on the tallest tower (height |V|) and the sink on the ground (height 0). At the start the source floods every neighbour with as much water as the pipes allow. A vertex that holds more water than it has passed on is overflowing (its excess e is positive). An overflowing vertex may push water only downhill to a neighbour exactly one step lower. If every route out is level or uphill, the vertex relabels: it raises its own tower just enough to create a downhill step. Eventually all spare water either reaches the sink or is pushed back to the source.

A preflow obeys capacities but lets a vertex receive more than it sends. Its excess is e(u) = (flow in) − (flow out). A vertex other than s, t with e > 0 is overflowing.
A height function h has h(s) = |V|, h(t) = 0, and h(u) ≤ h(v) + 1 for every residual edge (u,v) (you can never drop more than one step along a residual edge). This is what guarantees there is no s–t path in Gf.

The two basic operations. push(u,v) is applicable when u is overflowing, cf(u,v) > 0, and height[u] = height[v] + 1; it moves d = min(excess[u], cf(u,v)). If d = cf(u,v) the push is saturating (the residual edge disappears); otherwise it is nonsaturating and afterwards u is no longer overflowing. relabel(u) is applicable when u is overflowing and height[u] ≤ height[v] for every residual edge (u,v); it sets height[u] = 1 + min{height[v]}.

Heights never decrease and stay a valid height function. Every overflowing vertex has either a push or a relabel available, so the loop below never gets stuck while something overflows.

initializePreflow(G, s) — three examples

This is the starting whistle: it puts every vertex at height 0 with no water, lifts the source to height |V|, and floods every pipe leaving the source. Example 1 (normal): the running network.

Example 2 (edge case, the source has no outgoing edge): lines 6-8 never run and the algorithm has no work at all.

Example 3 (custom input): the usual u->v:capacity format.

push(u, v) — three examples

The player below runs the generic algorithm and stops on the first few pushes. Each push is drawn in four steps: the amount d, the change to the edge (line 5 for a real edge, line 6 when cancelling flow along a back-edge; lines 1-2 of the listing are comments), then the two excess updates. Example 1 (normal): the running network, first five pushes.

Example 2 (edge case, water returned to the source): the sink can only take 4 of the 10 units, so after the useful push the rest must go back along a residual back-edge (the else branch, line 6).

Example 3 (custom input): first six pushes of your network.

A vertex may push water only exactly one step downhill. A neighbour that is level or uphill is never a legal target, even if the edge is empty and the vertex is overflowing; the vertex must be relabelled first.

relabel(u) — three examples

Now the other half: a stuck vertex lifts itself just above its lowest residual neighbour. The player does every push silently and stops on each relabel. Example 1 (normal): the running network, first six relabels.

Example 2 (edge case, a vertex climbs above the source): water that cannot reach t raises its vertex until the only downhill neighbour is s.

Example 3 (custom input): first six relabels of your network.

relabel is only allowed when the vertex is overflowing and stuck. Relabelling a vertex that could still push, or one with no excess, can break the height function and with it the whole correctness proof.

genericPushRelabel(G) — three examples

The generic algorithm may choose any applicable operation. Our implementation always takes the first overflowing vertex (in the order the vertices were created) and pushes if it can, otherwise relabels. In the pictures each vertex shows h (height) above and e (excess) below; a cyan ring marks an overflowing vertex.

Example 1 (normal): the running network.

Example 2 (edge case, sink unreachable): the water floods in and can never reach t; heights keep rising until the trapped excess climbs above the source's tower and drains back into s. The final flow is 0.

Example 3 (custom input): a network where the source can push more than the sink can absorb along some edges.

The excess of the source is negative and the excess of the sink is positive; neither counts as "overflowing". When the algorithm ends, the flow value is simply excess[t].

Why no height can pass 2|V|−1. A vertex is relabelled only while it still holds excess, and an overflowing vertex always has a simple path back to s in Gf. That path has at most |V|−1 edges and drops at most one step per edge, so height[u] ≤ height[s] + |V| − 1 = 2|V| − 1. This one bound is what limits the number of relabels, and through them the saturating and nonsaturating pushes.

Analysis: heights never exceed 2|V|−1, so there are fewer than 2|V|² relabels, fewer than 2|V||E| saturating pushes, and fewer than 4|V|²(|V|+|E|) nonsaturating pushes (potential function Φ = Σ h(v) over overflowing vertices). Total O(V²E). Correctness: when no operation applies nothing overflows, so the preflow is a legal flow; the height function forbids an s–t path in Gf, so by the max-flow min-cut theorem it is maximum.

Dart implementation (initializePreflow, push, relabel and genericPushRelabel)

The shared state. The state the push-relabel procedures share: a height and an excess for every vertex.

The maths as code. The O(V²E) analysis as code: count every operation, re-check the height function after each one, and compare with the bounds (relabels < 2V², saturating < 2VE, nonsaturating < 4V²(V+E), heights ≤ 2V−1).

Input size → what is feasible: V = 100, E = 10³ → V²E = 10⁷ steps, instant; V = 1000, E = 10⁴ → V²E = 10¹⁰ in the worst case (usually far less in practice).

7. The relabel-to-front algorithm

Generic push-relabel is a crowd of workers each grabbing whatever job they like. relabelToFront gives them a queue discipline: keep all vertices in a list L and walk down it. At each vertex do a full discharge: push and relabel that vertex until its excess is zero. If discharging had to raise the vertex's height, move it to the front of the list (it may now have a fresh downhill path into vertices that come earlier), and carry on scanning from there.

To avoid rescanning, every vertex keeps a fixed neighbour list u.N (all vertices adjacent to u in either direction) and a pointer current[u] into it. An edge (u,v) is admissible when cf(u,v) > 0 and height[u] = height[v] + 1. discharge walks current along N: admissible edge, push; otherwise advance the pointer; falling off the end means no admissible edge remains, so relabel and start again from the head.

discharge(u) — three examples

discharge is the engine of relabelToFront: it empties one vertex completely. The animation calls it on each junction in list order, one loop iteration per step. Example 1 (normal): the running network, the first two calls.

Example 2 (edge case, relabel, partial push, then return to the source): vertex a has 10 units but the sink takes only 4, so it relabels twice before it can send anything back.

Example 3 (custom input): the first three discharges of your network.

relabelToFront(G, s, t) — three examples

Beside the picture you see the list L (current vertex highlighted) with each vertex's height and excess.

Example 1 (normal): the running network.

Example 2 (edge case, excess must be returned to the source): more flows into a than can ever reach t, so part of it climbs back to s.

Example 3 (custom input).

The current pointer is not reset after a push, only after a relabel. Resetting it after every push would make discharge rescan neighbours that are already known to be non-admissible and break the O(V³) bound. Also remember that a neighbour list contains vertices joined by an edge in either direction, because a back-edge can carry pushes too.

Why moving to the front is enough. While no relabel happens, the admissible edges form an acyclic network and the list L is a topological order of it, so a vertex that has been discharged only receives water from vertices earlier in the list, which have already been emptied. A relabel is the only event that can create a new admissible edge pointing to an earlier vertex, and moving the relabelled vertex to the front restores the topological order.

Running time: relabelToFront runs in O(V³). A phase is the stretch between two relabels; there are O(V²) relabels overall, and during a phase each vertex is discharged at most once, giving O(V³) discharge calls. The loop invariant is that L is topologically sorted with respect to the admissible edges (the admissible network is a DAG) and no vertex before the current one has excess.

Dart implementation

The maths as code. The O(V³) analysis as code: phases end at height raises, each vertex is discharged at most once per phase, and the loop invariant is re-checked before every iteration.

Input size → what is feasible: V ≤ 200 → V³ = 8·10⁶ steps, instant; V = 1000 → 10⁹ steps (about 10 s in Dart).

Quiz

Interview questions

Cheat sheet

Procedure	Time (best / typical / worst)	Space	Idea / when to use
residualNetwork	Θ(V+E) with adjacency lists (Θ(V²) with a matrix), same in every case	Θ(V+E)	Turn each edge into a forward edge (c − f) and a back edge (f); the working graph of every augmenting algorithm
augmentOnce (one BFS + augment)	about deg(s) if t is found early / O(V+E) / O(V+E)	Θ(V)	One round of Ford-Fulkerson or Edmonds-Karp; none means the flow is maximum
fordFulkerson (any path)	O(E) (one path) / depends on paths / O(E·\|f*\|) for integer capacities	Θ(V+E)	Simple; fine when \|f*\| is small; can be very slow otherwise
edmondsKarp (BFS)	O(E) / usually far below the bound / O(V·E²), O(VE) augmentations	Θ(V+E)	Same loop, shortest path by edges; never depends on capacity values
minCutFromFlow (residual reachability)	Θ(V+E) after the flow is known	Θ(V)	S = vertices reachable from s in Gf; c(S,T) = \|f\|
enumerateCuts (visual only)	Θ(2^(V−2)·E) in every case	Θ(V)	Teaching and brute-force checking of max-flow = min-cut on tiny networks; never for real work
maximumBipartiteMatching via flow	O(E) / O(V·E) / O(V·E)	Θ(V+E)	Unit capacities; integrality gives 0/1 edges; Hall violators come from the final cut; Hopcroft-Karp reaches O(√V·E)
initializePreflow	Θ(V+E) in every case	Θ(V)	Heights 0, source at \|V\|, source edges saturated: the start of every push-relabel algorithm
push(u,v)	Θ(1)	Θ(1)	Move min(excess[u], cf) one step downhill; saturating or nonsaturating
relabel(u)	O(deg u) to scan the neighbours	Θ(1)	Lift a stuck overflowing vertex to 1 + its lowest residual neighbour
genericPushRelabel	O(V²E) worst case, any operation order	Θ(V+E)	Local heights and excess; the base of the fast practical max-flow codes
discharge(u)	O(deg u) per pointer sweep, amortised into the O(V³) total	Θ(1) extra per vertex (the current pointer)	Empty one vertex completely: push along admissible edges, relabel when the pointer falls off the list
relabelToFront	O(V³) worst case	Θ(V+E)	Discharge vertices in a list, move relabelled ones to the front; good for dense graphs

Space is Θ(V+E) for all of them (flows and residual capacities are stored per edge). None of these methods is stable or in-place in the sorting sense; that question does not apply.