Topological sort

You have a set of things with dependencies between them — build targets that need other targets built first, migrations that must run in a particular order, package installs, import statements — and you need one order to do them in, or you need to know why no order exists at all. The textbook definition, a linear ordering of a directed graph such that every edge points forward, is correct and does not tell you how to produce one. The procedure that does is short: repeatedly do whatever has nothing left in front of it.

Counting what is in front of each node#

The whole algorithm is one idea: for each node, count how many things it is still waiting for — its unmet prerequisites, usually called its in-degree. Anything whose count has already reached zero can run now, because nothing stands in front of it. This is the formulation known as Kahn’s algorithm, and it needs nothing more exotic than that count and a place to hold whatever is currently ready.

When more than one node is ready at the same step, any order between them is valid, and that is worth stating plainly: a reader expecting the sort to hand back one right answer needs to know that most graphs admit several, and that this is a property of the problem, not a weakness of the algorithm. A related question is which order to visit nodes in once the structure is a tree rather than a general graph — tree traversal orders covers that.

Running a node down decrements the count on everything that depends on it, and whatever count reaches zero as a result joins the ready set. That is the entire loop: take something ready, emit it, decrement its dependents, repeat until nothing is left to take.

There is a second standard way to arrive at the same kind of order, built the opposite way round. Instead of counting prerequisites forward, a depth-first search walks the graph and records each node the moment it is finished with — after every path leading out of it has already been explored. Reversing that finish-order list turns it into a valid topological order, because a node cannot finish before anything it points to has already finished. Kahn’s algorithm and the depth-first formulation are both standard, and they answer the same question from opposite ends: one watches what has become free, the other watches what has become done.

def topological_sort(graph):
    in_degree = {node: 0 for node in graph}
    for node in graph:
        for dependent in graph[node]:
            in_degree[dependent] += 1

    ready = [node for node in graph if in_degree[node] == 0]
    order = []

    while ready:
        node = ready.pop()
        order.append(node)
        for dependent in graph[node]:
            in_degree[dependent] -= 1
            if in_degree[dependent] == 0:
                ready.append(dependent)

    if len(order) < len(graph):
        return None  # whatever is missing sits on or behind a cycle
    return order

Every node is counted once and every edge is followed once — once to build the initial counts, once to decrement them when the node in front is emitted — so the cost is linear in the number of nodes plus the number of edges, not in their product. There is no separate pass over the graph beyond that.

The leftovers are the answer#

The check most implementations write as an afterthought — comparing how many nodes came out to how many went in — is the most useful thing the algorithm produces. A topological order exists for a directed graph if and only if the graph is acyclic, so a run that emits fewer nodes than the graph holds is not a bug in the implementation. It is the algorithm telling you the graph had a cycle, and telling you exactly which nodes were touched by it.

That remainder is not an error condition to catch and discard; it is exactly the set of nodes on a cycle, or downstream of one, handed to you for free by the same pass that built the order. A build tool that catches this, prints “circular dependency detected” and stops has thrown that set away. One that prints the nodes still sitting in the count map has told the reader where to start looking.

The honest caveat: that leftover set localises the problem rather than pinpointing it. It contains every node downstream of a cycle as well as the cycle itself, because a node waiting on a cycle can never have its count reach zero either, cycle member or not. Knowing which of those nodes actually close the loop still takes tracing the edges between them by hand — the algorithm narrows the search, it does not finish it.

That narrowing is still worth having, because the alternative most people reach for first is worse: reading the dependency declarations back over by eye, looking for the loop directly in the source rather than in what the algorithm already computed. The count map already ran over every edge once; the nodes it never got to zero on are a strictly smaller place to look than the whole graph. The trees path is the roadmap nearest this material.

The edge nobody declared#

The order comes out, every dependency it knows about is respected, and the run still breaks. The graph was never the actual dependency structure — an edge is missing from it.

The classic shape: two tasks that both write the same file, both touch the same table, or both mutate a piece of shared state, with no edge declared between them because neither task calls the other or names it in any manifest. Nothing forces the sort to put them in a particular order, so it does not — it places them wherever the count map and the ready set happen to put them, which depends on iteration order, on insertion order, on a node added somewhere else in the graph. The run works for a long stretch, because that arrangement has been stable, and then something upstream changes the count map’s iteration order and the two tasks land in the other sequence.

The point worth stating plainly: a topological sort is only as correct as the edges it was given, and an undeclared dependency does not produce an error. It produces an intermittent one — correct on most runs, wrong on the runs where the ready set happens to break the tie the other way.

The practical fix is not to stare harder at the sort, which did exactly what it was given. It is to ask what two tasks both touch — the same file, the same table, the same row, the same in-memory structure — and declare that as the edge the graph was missing.

Once the missing edge is declared, the count map picks it up on the next run without anything else about the algorithm changing: the newly-dependent task’s count starts one higher, so it cannot be emitted until the task it actually depends on already has been. The fix lives in the graph, not in the sort — which is exactly why re-reading the sort never finds it.