Order from pairwise rules
A Socratic walk-through of order from pairwise rules — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #How do you put a thousand tasks in a workable order when all you know is which pairs must come first?
A build system is handed ten thousand source files and a pile of statements of the form "this one must be compiled before that one". Nobody wrote down a schedule. Nobody knows the whole picture. Yet a valid sequence has to come out the other end, and quickly.
The puzzle is that the constraints are radically incomplete. For most pairs of files, nothing at all is specified — neither must precede the other. So we are being asked to manufacture a total order out of information that describes only a scattering of pairs. When is that even possible?
Reasoning it through
REASONING #Begin with the incompleteness, because it is the point rather than an inconvenience. The constraints define a partial order: some pairs are related, most are not, and the relation is transitive — if A must precede B and B must precede C, then A must precede C, whether or not anyone said so. A schedule is a total order: every pair is decided. So the task is to extend a partial order to a total one that contradicts none of it. Mathematicians call the result a linear extension.
When can that be done? Try to break it. Suppose the constraints say A before B, B before C, and C before A. Follow the transitivity and A must precede itself, which no ordering can satisfy. That is a cycle, and it is fatal.
Now the more interesting direction: is a cycle the only thing that can go wrong? Suppose the constraint graph has no cycle at all. Must a valid order exist? Here is an argument. In a finite graph with no cycles there must be at least one node with nothing pointing into it — because if every node had a predecessor you could walk backwards forever, and in a finite graph walking forever means revisiting a node, which is a cycle. Take such a node, put it first, remove it, and observe that the rest is still acyclic. Repeat. The process cannot get stuck, since the same argument applies at every stage, and it terminates because the graph shrinks. So a valid order exists precisely when the graph is acyclic — not merely usually, but exactly.
That proof is also an algorithm, which is a pleasant thing when it happens. Kahn's method, published in 1962, maintains for each task a count of unsatisfied prerequisites — its in-degree. Every task with a count of zero goes into a ready set. Repeatedly remove one, emit it, and decrement the counts of everything it pointed at, adding to the ready set anything that drops to zero. Each node is emitted once and each edge is examined once, so the cost is proportional to the number of tasks plus the number of constraints.
And the cycle detection comes free. What happens if the ready set empties while tasks remain? Every remaining task has at least one unsatisfied prerequisite, which by the walking-backwards argument means the remaining subgraph contains a cycle. So the algorithm does not need a separate check; failing to finish is the check, and the tasks left behind are exactly the ones tangled in circular dependencies — which is why a build tool can name the offending files rather than merely reporting a failure.
A second method is what most recursive code does: depth-first search, emitting each node when its exploration finishes, then reversing the output. A node finishes only after everything it depends on has, so reverse finishing order respects every edge, and cycles show up as an edge back to a node still on the recursion stack.
One thing to be clear about: the answer is generally not unique. Whenever two tasks are unrelated, either may go first, and the number of valid orders can be astronomical — counting them exactly is #P-complete, a result of Brightwell and Winkler from 1991. This is a feature, not an ambiguity to be resolved. The freedom is the schedule's slack, and it is what lets you choose among valid orders on some other criterion: emit alphabetically for reproducible builds, or emit the task on the longest remaining chain first to shorten the critical path.
That freedom is also what makes downstream questions cheap. With unlimited parallel workers the job takes as long as the longest chain of genuine dependencies, and processing tasks in topological order computes that in a single sweep, because a task's predecessors are always already accounted for.
The analogy
THE ANALOGY #Think of a recipe written not as steps but as a heap of index cards, each saying only "do this card before that one" — brown the meat before adding the stock, chop the onions before browning. Nothing says whether to chop the onions before or after opening the wine, because it genuinely does not matter. To cook you need a sequence, so you repeatedly look for any card whose prerequisites are all done, do it, and cross it off. If a moment comes where every remaining card is waiting on another remaining card, someone wrote a circular instruction and no amount of care will save the dish.
the kitchen has real durations and one pair of hands, whereas the ordering knows nothing of time — it will happily place a two-hour braise last, and turning a valid order into a good schedule needs the durations the graph never recorded.
Clarifying the model
THE MODEL #Two refinements.
First, a common confusion: the constraints as written need not be transitively closed, and should not be. If A precedes B and B precedes C, the edge from A to C is implied and adding it changes nothing about which orders are valid — but it does inflate the edge count and therefore the running time. The relation being a partial order is a statement about the reachability the graph induces, not about the edges you were handed.
Second, this is not a sorting problem in disguise. A comparison sort may ask about any pair and always gets an answer, which is why it needs about n log n comparisons to pin down one of n! arrangements. Here the pairwise facts are given up front and most pairs have no answer at all, so there is nothing to search: the cost is linear, and the output is one of many acceptable orders rather than the unique correct one.
A picture of it
THE PICTURE #How to readarrows point from a prerequisite to what depends on it. Start with the nodes that have no incoming arrows — the parse and the schema — and emit anything whose incoming arrows have all been consumed; "compile module A" and "compile module B" are unordered relative to each other, which is exactly the slack a scheduler may spend. The diamond is the failure test: reaching it with tasks left over is what proves a cycle.
What became clearer
WHAT CLEARED #The constraints were never an incomplete description of a hidden true order — they are the whole specification, and they specify a set of acceptable orders rather than one. A valid order exists exactly when there is no cycle, the proof of that fact is itself the algorithm, and the freedom left over is not sloppiness but the room in which real scheduling decisions get made.
Where to go next
ONWARD #- Critical path analysis, which puts durations on the graph and asks how long the whole job takes with unlimited parallelism.
- Incremental and dynamic topological ordering, where edges arrive over time and the order must be repaired rather than recomputed.
Key terms
TERMS #| Term | What it means |
|---|---|
| Partial order | a relation deciding some pairs and leaving others incomparable, here induced by reachability in the constraint graph. |
| Linear extension | a total order consistent with every relation in a partial order; a topological sort produces one. |
| In-degree | the number of unsatisfied prerequisites a task still has; the counter Kahn's algorithm decrements. |
| Directed acyclic graph | a directed graph containing no cycle; exactly the condition under which a valid order exists. |
Every term the collection defines is gathered in the glossary.