Topological sort: Kahn's algorithm in Python

In this illustrative build, packaging needs both compiled code and collected assets. A useful order must respect those dependencies; sorting the task names alphabetically does not check them. Each directed edge points from a prerequisite to a task that needs it. A graph with no directed cycles is called a directed acyclic graph, or DAG.

A worked example of Kahn’s algorithm#

Start with A → B, A → C, B → D, C → D and D → E. A has no prerequisites. B and C each wait for one task, D waits for two, and E waits for one. The number of incoming edges is a node’s in-degree; during the algorithm, the remaining count tells us how many prerequisites are still unmet.

Emit A, then subtract one from B’s and C’s counts. Both become ready. Choosing B first lowers D’s count from two to one, so D still cannot run. Only after C is emitted does D reach zero. D then releases E. This counting procedure is Kahn’s algorithm.

The order A, B, C, D, E is valid, and so is A, C, B, D, E. The dependency graph does not choose between B and C. Add C → B in the experiment: C must now precede B. Add D → B instead: B and D wait on each other. The ready set eventually empties before all tasks are emitted.

Python implementation and complexity#

The complete example below returns an emitted order and a map of blocked nodes with their remaining counts. An empty blocked map means the order is complete. A non-empty map means the graph has a directed cycle; the partial order must not be presented as a complete solution.

from collections import deque

def topological_sort(graph):
    # graph[u] lists tasks that must come AFTER u.
    # Copy the lists so even one-shot iterables can be read twice.
    successors = {node: list(after) for node, after in graph.items()}
    in_degree = {node: 0 for node in successors}
    for after in successors.values():
        for dependent in after:
            in_degree.setdefault(dependent, 0)  # include target-only nodes
            in_degree[dependent] += 1

    ready = deque(node for node, count in in_degree.items() if count == 0)
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for dependent in successors.get(node, ()):
            in_degree[dependent] -= 1
            if in_degree[dependent] == 0:
                ready.append(dependent)

    blocked = {node: count for node, count in in_degree.items() if count > 0}
    return order, blocked

graph = {
    "A": ["B", "C"],  # prepare -> compile, assets
    "B": ["D"],       # compile -> package
    "C": ["D"],       # assets -> package
    "D": ["E"],       # package -> deploy
    "E": [],
}
print(topological_sort(graph))
# (['A', 'B', 'C', 'D', 'E'], {})

cyclic = {**graph, "D": ["E", "B"]}  # add package -> compile
print(topological_sort(cyclic))
# (['A', 'C'], {'B': 1, 'D': 1, 'E': 1})

This example accepts a finite dictionary of hashable nodes and finite iterables of dependents. A node mentioned only as a dependent is included as a leaf. Include an isolated node as a key with an empty list. Duplicate edges are counted and removed the same number of times. The input is not mutated, and the graph must stay fixed for this sort.

With adjacency lists, the work is O(V + E): initialise V counts, inspect E edges to build them, then emit each node at most once and inspect its outgoing edges again. Two passes over the edges are still linear. Python’s deque provides approximately constant-time operations at either end; a list’s pop(0) would shift waiting entries.

The counts, ready queue and output use O(V) storage. This implementation also copies E adjacency entries, so its total extra storage is O(V + E). A repeatable adjacency representation could avoid that copy. These operation counts assume constant-time hashing and comparison of node identifiers; they are not measured runtimes.

Cycle detection and blocked nodes#

In the cyclic example, A and C can still be emitted. B waits for D, D waits for B, and E waits for D. The blocked set is B, D and E. E is downstream of the cycle without being a cycle member itself. Printing all three as an exact cycle would be wrong.

Why does an unfinished run prove a cycle? Every remaining node has an incoming edge from another remaining node. Follow those prerequisites backwards. In a finite graph, that walk must revisit a node, closing a directed loop. Conversely, no member of a directed cycle can become ready first, because it still waits for another cycle member. Princeton’s directed-graph material states the same existence condition: a topological order exists exactly when the graph is a DAG.

The remainder can include the entire graph; it is not guaranteed to be a smaller diagnostic set. To recover an actual loop, use a DFS that tracks the active branch, or a library that returns a cycle witness. Nodes outside the blocked set have a usable dependency order, but executing that partial work is a separate application decision.

Kahn’s algorithm versus DFS#

DFS explores a branch before returning to alternatives. For topological sorting, mark each node as unseen, active or finished. An edge to an active node proves a directed cycle. If the graph is acyclic, record a node after its dependents finish, then reverse the finished-node list. That reverse finish order places every prerequisite before its dependents. A plain visit-order list does not do this; BFS versus DFS explains the traversal that this method extends.

Our FIFO queue chooses by arrival in the ready set. It does not guarantee the alphabetically smallest valid order. If that matters, choose the smallest currently ready node with a binary-heap priority queue; sorting the finished output could violate dependencies. Heap queue operations change the time bound to O(E + V log V), assuming constant-cost key comparisons.

Python graphlib uses the opposite mapping#

Python 3.9 and later include graphlib.TopologicalSorter. Its dictionary values are prerequisites. Our function’s values are dependents. For A → B, write {“A”: [“B”]} for our function and {“B”: [“A”]} for graphlib. Reusing the same dictionary unchanged reverses the intended dependency.

from graphlib import CycleError, TopologicalSorter

# Here each value lists prerequisites, NOT dependents.
prerequisites = {
    "A": [],
    "B": ["A"],
    "C": ["A"],
    "D": ["B", "C"],
    "E": ["D"],
}
print(tuple(TopologicalSorter(prerequisites).static_order()))
# ('A', 'B', 'C', 'D', 'E') for this input order

try:
    cyclic = {**prerequisites, "B": ["A", "D"]}
    tuple(TopologicalSorter(cyclic).static_order())
except CycleError as error:
    print("One detected cycle:", error.args[1])
    # A closed path such as B -> D -> B; the chosen cycle can vary.

static_order() returns an iterator and raises CycleError for a cycle. The exception’s second argument contains one closed cycle path; which cycle is chosen is unspecified. For a scheduler that needs ready batches, graphlib also provides prepare(), get_ready() and done(). Mark a task done after it actually finishes, then ask for newly ready work. Being emitted by a sorting demonstration does not mean real work has completed.

What a dependency order cannot guarantee#

The sort respects only declared edges. If B and C both write the same file, the graph may allow either order even though the application needs one writer to run first. Add the required dependency if serial order is the intended solution; shared-resource access may instead need a separate synchronisation rule. An undeclared dependency can cause failure without producing a graph cycle.

A topological order also does not minimise elapsed time, account for worker capacity or recover from task failures. Ready tasks may be eligible to run together, but real concurrency needs those additional rules. Use the graph to state what must precede what, then decide how the work will execute.