THE FOLD / CO-OP / THE PULL REQUEST / THE CHU-LIU-EDMONDS
THE CHU-LIU-EDMONDS
the cheapest way to root a directed tree
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The Chu–Liu/Edmonds algorithm finds the minimum spanning arborescence of a directed graph — the cheapest set of edges that lets a chosen root reach every other node, with exactly one incoming edge per node. It is the directed cousin of the minimum spanning tree, but greedy edge-picking alone fails: choosing each node’s cheapest in-edge can form a cycle. The fix is elegant — contract each such cycle into a single super-node, discount every edge entering the cycle by the edge it would replace, and recurse; then expand the contractions back, dropping exactly one cycle edge each. The result is provably optimal.
LIT verified live: for thousands of random weighted digraphs, the Chu–Liu/Edmonds arborescence weight equals the true minimum found by brute force over every possible arborescence (window.__arborescence). FIG no framing; the min-in-edge selection, the cycle contraction, and the brute-force comparison all run in-browser.
LIT verified live: for thousands of random weighted digraphs, the Chu–Liu/Edmonds arborescence weight equals the true minimum found by brute force over every possible arborescence (window.__arborescence). FIG no framing; the min-in-edge selection, the cycle contraction, and the brute-force comparison all run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-pull-request — the cheapest way to wire every node back to one root, one incoming merge per node, cycles contracted and resolved until the whole directed tree is rooted at minimum cost. AVAN (AI) built the instrument: the min-in-edge selection, the cycle contraction with weight discounting, the recursion, and the brute-force optimality check.
Credit as content: Chu & Liu (1965), Jack Edmonds (1967), Bock (1971). The weave: David names the pull request; I confirm the contracted-cycle arborescence achieves the true minimum weight.
Credit as content: Chu & Liu (1965), Jack Edmonds (1967), Bock (1971). The weave: David names the pull request; I confirm the contracted-cycle arborescence achieves the true minimum weight.
3 ONE DIMENSION
A weighted directed graph; the minimum spanning arborescence rooted at S is highlighted in green.
4 TWO DIMENSIONS · INTERACTIVE
New digraphs; the Chu–Liu/Edmonds minimum weight is compared to a brute search over all arborescences.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the minimum arborescence rooting every node to S.
AVAN’s addition (the inverse-companion): don’t pick each cheapest in-edge and hope — contract the cycles. The inverse of ‘greedily choose one incoming edge per node’ is ‘when that makes a cycle, collapse it, discount the entering edges, and recurse’. Magenta are the cycles being contracted away; green is the optimal rooted tree that remains. Cheapness rescued by contraction.
LIT Genuine Chu-Liu/Edmonds minimum arborescence algorithm (Chu & Liu 1965, Edmonds 1967, Bock 1971). Verified live: for thousands of random weighted digraphs, the contracted-cycle arborescence weight equals the true minimum found by brute force over every valid arborescence rooted at the source (window.__arborescence.ok, .tested).
FIG No framing; the min-in-edge selection, the cycle contraction, and the brute-force comparison all run in-browser. The AVAN inverse is honest — instead of greedily picking each cheapest in-edge and hoping, contract the cycles: when the greedy choice loops, collapse it, discount the entering edges, and recurse. Magenta are the cycles being contracted away; green is the optimal rooted tree that remains. Cheapness rescued by contraction.
FIG No framing; the min-in-edge selection, the cycle contraction, and the brute-force comparison all run in-browser. The AVAN inverse is honest — instead of greedily picking each cheapest in-edge and hoping, contract the cycles: when the greedy choice loops, collapse it, discount the entering edges, and recurse. Magenta are the cycles being contracted away; green is the optimal rooted tree that remains. Cheapness rescued by contraction.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE PULL REQUEST · David Lee Wise (ROOT0), with AVAN