Topological Sort, in depth: Kahn and DFS, cycle reporting, deterministic orders, parallel levels and build systems

The problem, stated precisely

Model the dependencies as a directed graph. Each task is a node, and an edge from u to v means u must happen before v. A topological order is a list of all nodes such that for every edge u to v, u appears earlier than v. Two facts make the problem well defined.

First, an order exists if and only if the graph has no directed cycle; such a graph is called a DAG, a directed acyclic graph. If A needs B and B needs A, no list can put each before the other. Conversely, every DAG has at least one node with no incoming edges, so you can always output such a node, delete it, and repeat on a smaller DAG. That argument is the proof, and it is also Kahn's algorithm.

Second, the order is usually not unique. Any two tasks with no path between them can appear in either order. For some graphs the number of valid orders is enormous; counting them exactly is #P-complete, as Brightwell and Winkler showed in 1991. So never write code or tests that assume a specific order unless you forced one, which is a later section.

Kahn's algorithm: peel off what is ready

Kahn's algorithm tracks, for each node, its in-degree: how many prerequisites remain unfinished. Nodes with in-degree zero are ready. Repeatedly take a ready node, output it, and decrement the in-degree of each of its successors, adding any that reach zero to the ready set.

from collections import deque

def kahn(nodes, edges):
    """nodes: iterable of ids; edges: list of (u, v) meaning u must come before v."""
    succ = {n: [] for n in nodes}
    indeg = {n: 0 for n in nodes}
    for u, v in edges:
        succ[u].append(v)
        indeg[v] += 1                 # count every edge; decrement every edge
    ready = deque(n for n in nodes if indeg[n] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in succ[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                ready.append(v)
    if len(order) != len(indeg):
        blocked = [n for n in indeg if indeg[n] > 0]
        raise CycleError(blocked)     # on a cycle OR downstream of one
    return order

Each node enters the ready queue once and each edge is decremented once, so the running time is O(V + E) and the memory is O(V + E) for the adjacency lists. The ready set does not have to be a queue. Any container works, and the choice of container decides which of the valid orders you get; that freedom is what later sections exploit. Cycle detection is free: if the loop ends before every node is output, the remaining nodes could never reach in-degree zero, so there is a cycle.

One detail causes real bugs. If the input may contain the same edge twice, either deduplicate edges everywhere or count them everywhere. The code above counts every edge when building in-degrees and decrements once per edge in the adjacency list, so duplicates are harmless. Deduplicating in one place but not the other leaves a node stuck at in-degree one forever, which looks exactly like a cycle.

DFS postorder: finish times give the order

The second algorithm uses depth-first search. When DFS finishes a node, meaning it has fully explored everything reachable from it, every successor of that node has already finished. So listing nodes in the order they finish gives every node after all its successors, and reversing that list gives a topological order. Cycle detection uses three colours: white for unvisited, gray for on the current DFS path, black for finished. Meeting a gray node means you found an edge back to an ancestor on the current path, which is a cycle.

WHITE, GRAY, BLACK = 0, 1, 2

def dfs_topo(nodes, succ):
    color = {n: WHITE for n in nodes}
    post = []
    for root in nodes:
        if color[root] != WHITE:
            continue
        color[root] = GRAY
        stack = [(root, iter(succ[root]))]      # explicit stack: no recursion limit
        while stack:
            u, it = stack[-1]
            v = next(it, None)
            if v is None:                        # all successors done
                stack.pop()
                color[u] = BLACK
                post.append(u)
            elif color[v] == WHITE:
                color[v] = GRAY
                stack.append((v, iter(succ[v])))
            elif color[v] == GRAY:               # back edge: v is on the current path
                path = [x for x, _ in stack]
                raise CycleError(path[path.index(v):] + [v])
    post.reverse()
    return post

This version uses an explicit stack. The textbook recursive version is shorter, but a dependency chain ten thousand deep, which is ordinary in a large build graph or a long unrolled computation, overflows the default recursion limit in Python and the thread stack in many other languages. The running time is also O(V + E). Background on the traversal itself, including edge classification, is in BFS and DFS in depth.

Worked example: an ML pipeline

Take seven tasks: A fetch data, B build vocabulary, C tokenize, D train, E evaluate, F export, G report. The edges are A to B, A to C, B to C, C to D, D to E, D to F, E to G and F to G. Initial in-degrees are A 0, B 1, C 2, D 1, E 1, F 1, G 2.

Kahn with a FIFO queue: the queue starts as [A]. Output A; B drops to 0 and C to 1, so the queue is [B]. Output B; C drops to 0. Output C; D drops to 0. Output D; E and F both drop to 0, queue [E, F]. Output E; G drops to 1. Output F; G drops to 0. Output G. The order is A B C D E F G.

DFS from A, visiting successors in listed order: A, then B, then C, then D, then E, then G. G has no successors and finishes first, then E. Back at D, visit F; its successor G is already black, so F finishes, then D, C, B. Back at A, C is already black, so A finishes. The finish order is G E F D C B A, and reversed it is A B C D F E G. It differs from Kahn's in swapping E and F, and both are correct, since there is no path between E and F.

Now add an edge from G to C, as if the report fed back into tokenization. Kahn outputs A and B, and then the queue is empty: C still waits on G. The leftover set is {C, D, E, F, G}, but the cycle is C, D, E, G. F is only downstream of the cycle. Reporting the leftover set as the cycle sends an engineer hunting in the wrong place. Run the three-colour DFS on the leftover nodes instead: it walks C, D, E, G, finds the edge from G back to gray C, and reports the path C, D, E, G, C, which is the actual loop to break.

Making the order deterministic

If your ready set is a hash set, or your adjacency lists come from a hash map, the order can change between runs, machines and language versions. For a build system that means non-reproducible output; for tests it means flakes. Fix the order by construction. Either keep insertion order everywhere and feed nodes in a stable order, or replace the queue with a min-heap keyed on a stable name. The heap gives the lexicographically smallest topological order, at a cost of O((V + E) log V):

import heapq

def smallest_order(nodes, succ, indeg):
    """Lexicographically smallest topological order: Kahn with a min-heap."""
    heap = [n for n in nodes if indeg[n] == 0]
    heapq.heapify(heap)
    out = []
    while heap:
        u = heapq.heappop(heap)
        out.append(u)
        for v in succ[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                heapq.heappush(heap, v)
    return out

def levels(order, succ):
    """Earliest round each node can run in, given unlimited workers."""
    level = {n: 0 for n in order}
    for u in order:                  # any topological order works
        for v in succ[u]:
            level[v] = max(level[v], level[u] + 1)
    return level

def critical_path(order, succ, cost):
    finish = {}
    for u in order:
        finish[u] = finish.get(u, 0) + cost[u]
        for v in succ[u]:
            finish[v] = max(finish.get(v, 0), finish[u])
    return max(finish.values())      # minimum makespan with unlimited workers

The same code shows two scheduling tools. Levels give the earliest round in which each node can run with unlimited workers: in the example, six rounds numbered 0 to 5, with E and F together at level 4, the fifth round. Critical path adds task costs and gives the minimum possible makespan; if training takes four hours and everything else minutes, no amount of parallelism finishes the pipeline in under four hours. The critical path computation is dynamic programming over a topological order, the pattern in dynamic programming in depth: process nodes in order so every predecessor's answer is final before you use it. With a limited number of workers, optimal scheduling becomes NP-hard in general, and real schedulers use list scheduling, which means Kahn's algorithm with a priority queue ordered by remaining critical path.

Where it runs in production

Two operational patterns follow from the table. Schedulers run Kahn's algorithm incrementally: the in-degree map is live state, completing a task decrements its successors, and anything that hits zero is dispatched. That makes a crash-safe scheduler a matter of persisting completions and recomputing in-degrees on restart, not persisting the order. And in autograd the reverse order is why a tensor's gradient is only complete after every operation that consumed it has run its backward step, which is exactly the finish-time property DFS uses.

When a graph has cycles you must live with, such as mutually recursive modules, collapse each strongly connected component into one node and sort the resulting condensation, which is always a DAG. Tarjan's algorithm finds those components in linear time; the same lowlink machinery appears in bridges and articulation points.

Failure modes

• Reversed edges. The most common bug is building edges as depends-on instead of must-come-before, which yields a perfectly valid order that is exactly backwards. Pick one direction, name it in the type, and test with a two-node graph.
• Missing isolated nodes. Building the node set from edges alone drops tasks with no dependencies at all. Always pass the full node list.
• Reporting the leftover set as the cycle. As the worked example shows, it over-reports. Extract a real cycle with the three-colour DFS.
• Recursion depth. Deep chains overflow a recursive DFS. Use an explicit stack or Kahn's algorithm.
• Hidden nondeterminism. Hash iteration order leaks into the output. Use a heap or stable ordering if anyone will ever diff two outputs.
• Re-sorting on every change. Recomputing a full sort after each edge insertion in a huge interactive graph costs O(V + E) per edit. For editors and spreadsheets, maintain in-degrees incrementally, or recompute only the affected subgraph.

What to do next

1. Implement Kahn's algorithm from memory, then the iterative DFS version, and run both on the seven-node example.
2. Write a test that checks the property, every edge goes forward in the output, instead of comparing against one fixed order.
3. Add the G to C edge and make your code report the actual cycle path, not the leftover set.
4. Switch the ready queue to a min-heap and confirm two runs produce identical output.
5. Compute levels and the critical path for a real pipeline or build you own, and compare it with its wall-clock time.
6. Read how your build tool or scheduler reports cycles, and check whether it reports the loop or everything blocked by it.