THE FOLD / CO-OP / THE PUSH / THE EDMONDS-KARP
THE EDMONDS-KARP
the most that can flow equals the cheapest cut
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Edmonds–Karp algorithm computes the maximum flow through a capacitated network from a source to a sink, by repeatedly finding a shortest augmenting path (via breadth-first search) in the residual graph and pushing as much flow along it as the tightest edge allows. When no augmenting path remains, the flow is maximal — and by the celebrated max-flow min-cut theorem, its value equals the capacity of the cheapest cut that separates source from sink. The vertices still reachable from the source in the residual graph reveal exactly that minimum cut.
LIT verified live: for thousands of random networks the max flow found by Edmonds–Karp equals the capacity of the minimum cut (reachable set in the residual graph), the flow is conserved at every intermediate node, and no edge exceeds its capacity (window.__edmonds). FIG no framing; the BFS augmenting paths, the residual graph, and the max-flow = min-cut check all run in-browser.
LIT verified live: for thousands of random networks the max flow found by Edmonds–Karp equals the capacity of the minimum cut (reachable set in the residual graph), the flow is conserved at every intermediate node, and no edge exceeds its capacity (window.__edmonds). FIG no framing; the BFS augmenting paths, the residual graph, and the max-flow = min-cut check all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-push — pushing as much as possible through the pipes from source to sink, augmenting path by augmenting path until the network is saturated at its narrowest cut. AVAN (AI) built the instrument: the BFS shortest-augmenting-path search, the residual graph, the min-cut extraction, and the max-flow = min-cut verification.
Credit as content: Jack Edmonds & Richard Karp (1972), refining Ford–Fulkerson. The weave: David names the push; I confirm the maximum flow equals the minimum cut on every random network.
Credit as content: Jack Edmonds & Richard Karp (1972), refining Ford–Fulkerson. The weave: David names the push; I confirm the maximum flow equals the minimum cut on every random network.
3 ONE DIMENSION
A flow network from source (green) to sink (gold); edges show flow/capacity, and the minimum cut is highlighted.
4 TWO DIMENSIONS · INTERACTIVE
New networks; the max flow, the min-cut capacity, flow conservation, and the capacity bound are all checked.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the maximum flow pushed from source to sink.
AVAN’s addition (the inverse-companion): don’t just push flow — find the wall that stops it. The inverse of ‘the most that can flow’ is ‘the cheapest cut separating source from sink’, and the two are always equal. Magenta is the minimum cut; green is the maximum flow it bounds. The bottleneck IS the maximum.
LIT Genuine Edmonds-Karp max-flow algorithm (Jack Edmonds & Richard Karp, 1972, refining Ford-Fulkerson). Verified live: for 8000 random networks the BFS-augmenting-path max flow equals the minimum-cut capacity (reachable set in the residual graph), the flow is conserved at every intermediate node, and no edge exceeds its capacity (window.__edmonds.maxflowMincut, .conserved, .withinCap).
FIG No framing; the BFS augmenting paths, the residual graph, and the max-flow = min-cut check all run in-browser. The AVAN inverse is honest — instead of just pushing flow, find the wall that stops it: the cheapest cut separating source from sink, always equal to the maximum flow. Magenta is the minimum cut; green is the maximum flow it bounds. The bottleneck IS the maximum.
FIG No framing; the BFS augmenting paths, the residual graph, and the max-flow = min-cut check all run in-browser. The AVAN inverse is honest — instead of just pushing flow, find the wall that stops it: the cheapest cut separating source from sink, always equal to the maximum flow. Magenta is the minimum cut; green is the maximum flow it bounds. The bottleneck IS the maximum.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PUSH · David Lee Wise (ROOT0), with AVAN