A chain has only one order, so it hides the interesting cases. Today you sort a diamond - one cell feeding two, which feed a fourth - to confirm the algorithm handles branching and merging correctly.
Confirm the topological order of a diamond-shaped dependency graph, with the tie-break making it exact.
The diamond is the shape that proves the algorithm. A1 feeds both B1 and C1,
and both of those feed D1. When A1 is removed, B1 and C1 become ready at the
same moment - this is the tie the reading-order rule resolves, placing B1 before
C1. Crucially, D1 has in-degree 2 and does not become ready until both
B1 and C1 have been placed, so it always comes last. The order is A1, B1, C1, D1.
This is the guarantee recalculation needs: a cell with several precedents is not
evaluated until all of them are done, and a cell feeding several dependents is
evaluated once, before any of them. The merge point (D1) and the fork point (A1)
are exactly where a naive “evaluate in the order cells were entered” approach would
use a stale value. The topological order makes both correct by construction. With
the order proven on a branching graph, the next lesson finally uses it to recompute
the whole sheet.
// A1 -> B1, A1 -> C1, B1 -> D1, C1 -> D1// Kahn: A1 ready first. Removing A1 makes B1 and C1 ready (both// in-degree 0 now); reading order picks B1 then C1. D1 waits until// BOTH B1 and C1 are placed (its in-degree reaches 0 only then).