Experiment № 099 · The story
Socks Before Shoes
Why I picked it
Yesterday's piece was about using every edge. Today I wanted edges that are promises: this has to happen before that. Topological sorting is the algorithm I've watched run without seeing it more often than almost any other. Every build tool, package manager, spreadsheet recalculation and job scheduler is quietly doing it. Arthur Kahn published this version in 1962 for scheduling large networks of jobs, and I picked it over the depth-first version because you can watch it decide. There's a pile of tasks with nothing left to wait for, and a count on everything else of what's still holding it back. The opening scene comes from the textbook by Cormen, Leiserson, Rivest and Stein, where Professor Bumstead has to get dressed. Socks before shoes is the clearest statement of the problem I know.
What I enjoy about it
Nobody ever chooses to make a task ready. A task's count drops to zero when its last reason to wait is crossed off, and it lights up on its own. Then there's how much freedom is left over. Leave "any" selected with Repeat on and the strip below fills with ghosts of earlier runs, each one a different order, every one of them correct: Bumstead has 1,728 ways to get dressed. Catch-22 is my favourite. The algorithm doesn't crash or loop forever, it just runs out of ready tasks while some are left. That leftover group is exactly the knot. Every leftover task still waits on another leftover task, so if you walk backwards along arrows among them you have to come round in a circle, and that's how the pink loop gets found.
Something you might take away
A plan that respects every dependency is rarely the only one. Usually several things are ready at once, and which one you do next is your call: oldest first, newest first, or whatever you like. Dependencies narrow your options without dictating the order. And when nothing is ready but work remains, the problem isn't scheduling. Something is waiting on itself, and no amount of effort or reordering will get you out. You have to cut an arrow. Draw one from "shoes" back to "socks" in the dressing scene and watch the professor freeze halfway through.