Topological Sort

Some things simply have to happen before others. You cannot compile a module before the modules it imports, take the advanced course before its prerequisite, or pour concrete before you have dug the foundation. When you have a whole pile of such constraints tangled together, "what order do I do these in" stops being obvious. Topological sort is the answer: given a set of items and a list of "this must come before that" rules, it produces a single linear order that never violates a rule, or tells you honestly that no such order exists.

The structure underneath is a directed acyclic graph, a DAG, where an edge from A to B means "A must come before B." The word acyclic is doing real work: if the constraints loop back on themselves (A before B, B before C, C before A), no valid order can exist, and a good topological sort detects exactly that. The most intuitive way to compute it is Kahn's algorithm, and it mirrors how you would actually untangle the pile by hand: repeatedly grab anything that has nothing left blocking it, do it, cross it off everyone's list, and repeat.

Kahn's algorithm: peel off whatever is unblocked

The bookkeeping is the in-degree of each node, the count of unmet prerequisites still pointing at it. Anything at in-degree zero is ready to go right now. Emit it, decrement its neighbors, and whatever drops to zero joins the ready set.

from collections import deque, defaultdict

def topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1                     # count prerequisites pointing at v

    ready = deque([u for u in graph if in_degree[u] == 0])
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)                        # nothing blocks it, so it goes next
        for v in graph[node]:
            in_degree[v] -= 1                     # one prerequisite satisfied
            if in_degree[v] == 0:
                ready.append(v)                   # now unblocked

    if len(order) != len(graph):
        raise ValueError("cycle detected: no valid order exists")
    return order

graph = {'A': ['C'], 'B': ['C', 'D'], 'C': ['E'], 'D': ['F'], 'E': ['F'], 'F': []}
print(topological_sort(graph))                    # ['A', 'B', 'C', 'D', 'E', 'F']

Trace the in-degrees: A and B start at zero (nothing depends on being before them), so they go first; emitting them frees C and D; and so on down to F, which waits until both D and E have cleared. The final safety check is the elegant part: if the order came up short, some nodes never reached in-degree zero, which can only mean they are trapped in a cycle. Cycle detection is not a separate algorithm here, it is a free byproduct.

A dependency graph with edges A to C, B to C, B to D, C to E, D to F and E to F; nodes with no unmet prerequisites, A and B, are peeled first, freeing the rest in turn, producing the linear order A B C D E F where every arrow points forward.

In the wild: the build system deciding what to compile first

Every build tool you have used (make, webpack, a compiler's module linker, a CI pipeline) is running a topological sort under the hood. Your source files declare dependencies through their imports, which forms a DAG, and the tool must compile or bundle them in an order where every file's dependencies are ready before it is processed. That order is exactly topological_sort of the import graph. Task runners do the same for job dependencies, and a spreadsheet does it every time you edit a cell, recomputing dependent cells in dependency order.

And here is where the free cycle detection becomes a feature you have definitely seen. When you accidentally make module A import B while B imports A, the build fails with "circular dependency detected." That message is the len(order) != len(graph) check firing: the bundler tried to topologically sort your imports, got stuck with files no ordering could satisfy, and reported the cycle rather than looping forever or producing garbage. Same algorithm as the toy, scaled to thousands of files, and the error you curse at is the safety net working as designed.

The trigger

You have items with "must come before" constraints and need a valid linear order, or you need to know a valid order is even possible. Prerequisites, dependencies, build order, install order, task scheduling with precedence: all of these are topological sort. If you catch yourself trying to sort things where the comparison is not "smaller or larger" but "depends on," this is the pattern.

Where it shows up

  • Build and dependency resolution: compilation order, module bundling, package install order, linker ordering.
  • Scheduling with precedence: task pipelines, course prerequisites, assembly steps that gate each other.
  • DAG preprocessing: producing the order in which to run dynamic programming or longest-path computations over a dependency graph.

Where it bites

The first trap is assuming your graph is actually acyclic; real dependency graphs grow cycles, so always keep the completeness check rather than blindly trusting the output. The second is expecting a unique answer: when several items are simultaneously unblocked, any of them can go next, so multiple valid orders exist, and if you need a specific tie-break (alphabetical, by priority) you must impose it yourself, for instance by using a heap instead of a plain queue for the ready set. Forgetting to seed the ready set with every zero in-degree node, or mutating the original in-degree map when you meant to copy, are the usual off-by-one style bugs.

When it is the wrong tool

If there are no ordering constraints at all, this is overkill and a plain sort or no sort will do. If the graph has cycles by design, for example mutually recursive modules that are legitimately allowed, topological sort cannot order them, and you need to first collapse each strongly connected component into a single super-node (Tarjan's or Kosaraju's algorithm) and topologically sort those. And if you need the shortest or longest path through the DAG rather than just a valid order, the topological order is only step one; the actual answer comes from a dynamic programming pass over that order.

Its neighbors

Topological sort is built directly on Graph Traversals: Kahn's algorithm is BFS-flavored, and the alternative formulation is a DFS post-order reversed. Its cycle detection overlaps with the cycle-finding uses of DFS. And it is the standard front end for Dynamic Programming on a DAG, because processing nodes in dependency order is precisely what guarantees a subproblem is solved before anything that needs it.

References