Dependency Graphs and Topological Sort

Every build, every install and every deployment answers one question before it does anything else: in what order? Draw each task as a node and "must finish before" as an edge, and every valid order is a topological sort of that graph. An order exists exactly when the graph has no cycle, finding one costs time proportional to the tasks plus the dependencies, and the longest chain of dependent tasks sets a minimum wall-clock time that no number of machines can beat.

That last fact is the one with a bill attached. A pipeline that takes 40 minutes on ten runners may take 40 minutes on a hundred, and the reason is visible in the graph before anyone buys a runner. This topic is about reading that graph: the order, the parallelism, the cycle that makes ordering impossible, and the chain that sets the floor.

The Graph of "Before"

The nodes are tasks: generate code, compile a module, install a package, run a pipeline stage. An edge from A to B means A must finish before B starts. Any order that keeps every edge's promise is correct, and nothing else about the order matters. Build systems, package managers, CI pipelines, spreadsheet recalculation and database migrations all sit on this one structure, whatever syntax they use to declare it.

The example here is a six-task build. A code generator runs first. Two compile steps, a and b, each need the generated code. A link step needs both compiled halves. Tests and packaging each need the linked result. That is six nodes and six edges, and the first row of the figure below draws it.

Kahn's Algorithm: Peel Off What Is Ready

The most direct way to order the graph counts, for each task, how many of its inputs are still unfinished. Every task at zero is ready. Run a ready task, cross out its outgoing edges, and any task whose count drops to zero becomes ready in turn. Repeat until nothing is left.

In the figure, the blue number beside each task is its count of unmet inputs. At step 1 only the generator is at zero. Running it drops both compile steps to zero, so step 2 has two ready tasks. Running both drops the link step from 2 to 0. At step 4 tests and packaging are ready together. The ready set at each step is the set of tasks that may run in parallel at that moment, which is how a parallel build or a pipeline scheduler decides what to start next.

from graphlib import TopologicalSorter

deps = {"compile a": {"generate"}, "compile b": {"generate"},
        "link": {"compile a", "compile b"},
        "test": {"link"}, "package": {"link"}}

ts = TopologicalSorter(deps)
ts.prepare()
while ts.is_active():
    ready = ts.get_ready()     # everything that may run now
    print(sorted(ready))
    ts.done(*ready)

# ['generate']
# ['compile a', 'compile b']
# ['link']
# ['package', 'test']

The snippet above feeds the same six-task build to the topological sorter in Python's standard library, declaring each task with the set of tasks it needs. The loop asks for everything ready, marks it done and asks again. Run on CPython 3.15 it prints four batches: the generator alone, then both compile steps, then the link step, then packaging and tests together, the same four steps as the figure.

The Depth-First Route

The second classic method runs the depth-first search from the previous topic and records each task at the moment it finishes, meaning after everything it leads to has been explored. Every task finishes after all the tasks that depend on it, so the finishing record read backwards is a valid order. The cost is the same O(tasks + dependencies), and the three-state mark from the previous topic catches a cycle during the same walk.

The two methods produce different valid orders and suit different jobs. Kahn's algorithm hands out work in waves and suits a scheduler. The depth-first route suits a tool that only needs one order and wants to report a cycle by naming the path that forms it.

Why a Cycle Is an Error

If A needs B and B needs A, no order keeps both promises: whichever runs first is missing its input. Kahn's algorithm reveals this by stopping early. The tasks inside the cycle never reach a count of zero, so they are never ready, and when the ready set runs dry with tasks left over, those tasks contain the cycle. Python's sorter raises CycleError and names the loop, a to b to a, when given that pair.

A Python circular import is the same failure surfacing at run time. When module orders in a package imports billing and billing imports a name back from orders, the second import finds orders only half executed. On CPython 3.15 the error says it cannot import the name from a partially initialized module, "most likely due to a circular import". The fix is always to break an edge, by splitting a module or inverting a dependency, and never to retry, because no retry changes the graph.

Many Valid Orders

Most graphs admit many topological orders. The six-task build has four: the two compile steps can go in either order, and so can tests and packaging. A tool may pick any of them, and a different version of the same tool, or the same tool with parallelism switched on, may pick another.

That freedom is a trap for undeclared dependencies. A build that works only because B happened to run before C, with no edge saying so, has a missing edge that the current order satisfies by luck. It breaks the day the order changes, typically when parallelism is switched on or a runner is added, and it breaks as a flaky failure that passes on retry.

What Order Costs: The Critical Path

With unlimited workers, a job still takes as long as its longest chain of dependent tasks, the critical path. Two hundred CI jobs whose longest chain is six 5-minute jobs cannot finish in under 30 minutes, on 10 runners or on 1,000. Extra runners help only while the graph is wide enough to use them.

The figure schedules a 12-job pipeline: build, lint, six test shards, then integration, package, deploy and smoke tests in a row. The jobs add up to 58 minutes of work. On six runners, all six test shards run side by side, and the pipeline still takes 30 minutes, because build, one test, integration, package, deploy and smoke form a chain of six 5-minute jobs. For the last 20 minutes five runners sit idle. On a thousand runners the answer is the same 30 minutes; on four it rises to 35, because six shards need two rounds.

The same graph prices incremental builds. After a change, only the tasks downstream of the changed one need to run again, and finding them is a reachability walk from the change. Choosing which version of each package to install is a different and much harder problem, and Chapter 9's topic on backtracking takes it up.