optional · interactive figures

Explore: network flows

The residual graph as augmenting paths use it, and push–relabel with every node drawn at its height, both replayed from the reference solution.

optional: nothing in the lab depends on itback to the slides

14 · explore

Augmenting paths, on the residual graph

Try: step through Edmonds–Karp, then switch the menu to depth-first Ford–Fulkerson and watch its third path run backwards along b → a. Static version: augmenting, on the example.

What it shows. The textbook network of the slides ($sa = 3$, $sb = 2$, $ab = 1$, $at = 3$, $bt = 2$) as its residual graph: every arc with remaining capacity, forward arcs solid and backward arcs dashed. Each augmenting path is shown before it is used (thick), then the graph after sending its bottleneck. At the end the nodes still reachable from $s$ are filled: the source side of a minimum cut.

Edmonds–Karp is a logged copy of the reference edmonds_karp: breadth-first, so it finds $s \to a \to t$ then $s \to b \to t$, the table on the slide. No backward arc is needed.
Ford–Fulkerson, depth first uses the same residual graph but picks paths by depth-first search in the same adjacency order. Its first path $s \to a \to b \to t$ wastes the arc $a \to b$; its third path $s \to b \to a \to t$ cancels that unit through the backward arc $b \to a$. Four paths instead of two, same value 5.

Both runs are recorded by slides/viz/traces/u14.py on the reference Residual class, and checked against the reference edmonds_karp before they are written.

14 · explore

Push–relabel, drawn at the heights

Try: step and watch nodes rise; flow only runs one level downhill. Step 9 sends a unit back up the arc it came down. Static version: the push–relabel table.