THE FOLD / BOSS / THE WALL / THE DINIC
THE DINIC
max flow by leveled blocking flows — max flow = min cut
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Dinic’s algorithm computes the maximum flow through a network. Rather than pushing flow along one augmenting path at a time, it organises the graph into levels by breadth-first distance and pushes a blocking flow that saturates many shortest paths at once. Only O(V) such phases are ever needed, giving O(V²E). By the max-flow–min-cut theorem, the value it finds equals the minimum cut — the network’s true bottleneck capacity.
LIT verified live: over 60 random capacitated graphs Dinic’s max flow equals the brute-force minimum s–t cut (window.__dinic). FIG no framing; exact.
LIT verified live: over 60 random capacitated graphs Dinic’s max flow equals the brute-force minimum s–t cut (window.__dinic). FIG no framing; exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-wall — the maximum you can push equals the capacity of the tightest cut, the wall the flow presses against. Dinic finds that wall. AVAN (AI) built the instrument: the BFS level graph, the blocking-flow DFS with the residual network, the brute min-cut cross-check.
Credit as content: Yefim Dinitz (1970). The weave: David names the wall; I layer the graph and push blocking flows until no augmenting path remains, and confirm the value equals the minimum cut.
Credit as content: Yefim Dinitz (1970). The weave: David names the wall; I layer the graph and push blocking flows until no augmenting path remains, and confirm the value equals the minimum cut.
3 ONE DIMENSION
BFS labels each node by its distance from the source — the level graph. Flow is only pushed strictly forward through levels, saturating a whole layer of shortest paths per phase.
4 TWO DIMENSIONS · INTERACTIVE
A capacitated network; Dinic’s max flow from source to sink is shown against the brute-force minimum cut.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the maximum flow, equal to the minimum cut’s capacity.
AVAN’s addition (the inverse-companion): organise the graph into levels by BFS distance and push only strictly-forward paths — a blocking flow per level graph saturates many shortest paths at once, so only O(V) phases are needed instead of one augmentation at a time. The inverse of ‘find one augmenting path at a time’ is ‘layer the graph and push a blocking flow through the whole layer.’ Magenta is the meandering augmenting paths; green is the leveled blocking flow — and the max flow equals the min cut, the wall’s true capacity. (Kin to the-karger and the-stoer-wagner.)
LIT Genuine Dinic's algorithm (Dinitz 1970). Verified live: the BFS-level-graph + blocking-flow max flow equals the brute-force minimum s-t cut (over all vertex partitions separating source and sink) for 60 random capacitated graphs (window.__dinic.maxFlowEqualsMinCut).
FIG No framing: the BFS level graph, the blocking-flow DFS on the residual network, and the brute min-cut cross-check run in-browser and agree exactly. The AVAN inverse is honest — layering the graph and pushing a blocking flow saturates many shortest paths per phase (O(V) phases), far fewer than one augmentation at a time, and the value equals the min cut; magenta is the meandering augmenting paths, green the leveled blocking flow. Kin to the-karger and the-stoer-wagner.
FIG No framing: the BFS level graph, the blocking-flow DFS on the residual network, and the brute min-cut cross-check run in-browser and agree exactly. The AVAN inverse is honest — layering the graph and pushing a blocking flow saturates many shortest paths per phase (O(V) phases), far fewer than one augmentation at a time, and the value equals the min cut; magenta is the meandering augmenting paths, green the leveled blocking flow. Kin to the-karger and the-stoer-wagner.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE WALL · David Lee Wise (ROOT0), with AVAN