Topological sorting in Python: turn dependencies into a build order

Some jobs cannot start until other jobs finish. A build might need to fetch files before parsing them, compile before testing, and test before packaging. A scheduler faces the same problem with a different set of nouns.

A topological order turns those constraints into a sequence. For a directed edge from u to v, u must appear first. The order only exists when the graph has no directed cycle, and several valid orders may exist for the same graph.[1]

Diagram comparing repeated dependency scans with Kahn's topological sort and its ready queue — The scan keeps circling back. The queue waits for the next task to become ready.

The problem is a partial order

Consider this small dependency graph:

fetch -> parse -> compile -> test -> package

lint -> test

fetch and lint can begin immediately. test must wait for both of them, while package must wait for test. A valid result might start with either ready task. The exact order is less important than respecting every arrow.

The awkward case is a cycle. If test needs package and package already needs test, neither task can be placed first. A useful implementation should report that rather than returning a plausible-looking but invalid sequence. NetworkX’s topological_sort follows the same rule: it only works for directed acyclic graphs and raises an exception when no topological order exists.[1]

A baseline that keeps looking

The simplest approach is easy to write. Keep the unfinished nodes in a set, scan the original node list, and remove the first node whose prerequisites have all gone. Then start the scan again.

That repeated scan is the hidden cost. On a long chain, the next ready node sits just after the part of the list already processed, so the algorithm revisits a growing prefix on every pass. For this implementation the worst-case time is O(V² + E), where V is the number of nodes and E is the number of dependency edges. The set makes membership checks cheap, but it cannot stop the outer scan from walking over old positions.

This version is perfectly reasonable for a tiny graph or a one-off script. It is less attractive when a dependency graph is large, regenerated often, or sitting on a hot path.

Kahn’s algorithm remembers what changed

Kahn’s algorithm keeps an in-degree for every node, meaning the number of prerequisites still attached to it. Nodes with in-degree zero go into a queue. Each time the algorithm removes a node, it decreases the in-degree of that node’s successors. A successor enters the queue exactly when its last prerequisite disappears.

Python’s collections.deque is a good fit because the standard library documents fast appends and pops at either end.[2] The queue avoids restarting a scan. With adjacency lists, the algorithm initialises each node, visits each edge while building counts, and visits each edge again as its source is processed. That gives O(V + E) time and O(V + E) auxiliary storage for the graph representation and bookkeeping.

The cycle check is small but important: if fewer than V nodes leave the queue, some nodes still have prerequisites. Those remaining prerequisites form, or depend on, a cycle.

A complete comparison

The program below runs both versions on the same input, checks both answers, exercises the cycle failure, and measures a chain at four sizes. It uses timeit.repeat, which is designed for repeated small measurements and uses perf_counter() as its default timer.[3] The helper counters are not timings. They show how many candidate positions the baseline inspects and how many edge endpoints Kahn’s version touches across its count-building and removal passes.

from collections import deque
from statistics import median
from timeit import repeat
def baseline_topological_sort(graph):
    """Repeatedly scan the remaining nodes for one that is ready."""
    nodes = list(graph)
    incoming = {node: [] for node in nodes}
    for node, successors in graph.items():
        for successor in successors:
            if successor not in incoming:
                raise ValueError(f"unknown node: {successor}")
            incoming[successor].append(node)
    remaining = set(nodes)
    order = []
    while remaining:
        progress = False
        for node in nodes:
            if node not in remaining:
                continue
            if all(parent not in remaining for parent in incoming[node]):
                remaining.remove(node)
                order.append(node)
                progress = True
                break
        if not progress:
            raise ValueError("graph contains a cycle")
    return order
def kahn_topological_sort(graph):
    """Process each node when its final prerequisite is removed."""
    indegree = {node: 0 for node in graph}
    for node, successors in graph.items():
        for successor in successors:
            if successor not in indegree:
                raise ValueError(f"unknown node: {successor}")
            indegree[successor] += 1
    ready = deque(node for node, degree in indegree.items() if degree == 0)
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for successor in graph[node]:
            indegree[successor] -= 1
            if indegree[successor] == 0:
                ready.append(successor)
    if len(order) != len(graph):
        raise ValueError("graph contains a cycle")
    return order
def counted_baseline(graph):
    nodes = list(graph)
    incoming = {node: [] for node in nodes}
    for node, successors in graph.items():
        for successor in successors:
            incoming[successor].append(node)
    remaining = set(nodes)
    order = []
    candidate_scans = 0
    dependency_checks = 0
    while remaining:
        progress = False
        for node in nodes:
            candidate_scans += 1
            if node not in remaining:
                continue
            ready = True
            for parent in incoming[node]:
                dependency_checks += 1
                if parent in remaining:
                    ready = False
                    break
            if ready:
                remaining.remove(node)
                order.append(node)
                progress = True
                break
        if not progress:
            raise ValueError("graph contains a cycle")
    return order, candidate_scans, dependency_checks
def counted_kahn(graph):
    indegree = {node: 0 for node in graph}
    edge_visits = 0
    for node, successors in graph.items():
        for successor in successors:
            indegree[successor] += 1
            edge_visits += 1
    ready = deque(node for node, degree in indegree.items() if degree == 0)
    order = []
    while ready:
        node = ready.popleft()
        order.append(node)
        for successor in graph[node]:
            edge_visits += 1
            indegree[successor] -= 1
            if indegree[successor] == 0:
                ready.append(successor)
    if len(order) != len(graph):
        raise ValueError("graph contains a cycle")
    return order, edge_visits
def chain_graph(size):
    return {
        node: [node + 1] if node + 1 < size else []
        for node in range(size)
    }
def valid_order(graph, order):
    position = {node: index for index, node in enumerate(order)}
    return len(position) == len(graph) and all(
        position[node] < position[successor]
        for node, successors in graph.items()
        for successor in successors
    )
def main():
    example = {
        "fetch": ["parse"],
        "parse": ["compile"],
        "compile": ["test"],
        "lint": ["test"],
        "test": ["package"],
        "package": [],
    }
    baseline_order = baseline_topological_sort(example)
    kahn_order = kahn_topological_sort(example)
    print("Baseline order:", baseline_order)
    print("Kahn order:   ", kahn_order)
    print("Both valid:   ", valid_order(example, baseline_order) and valid_order(example, kahn_order))
    print("Cycle check:  ", end=" ")
    try:
        kahn_topological_sort({"a": ["b"], "b": ["a"]})
    except ValueError as error:
        print(error)
    print("\nChain benchmark (median of 5 repeats, one call per repeat)")
    print("nodes  baseline_ms  kahn_ms  ratio  baseline_node_scans  kahn_edge_touches")
    for size in (200, 500, 1000, 2000):
        graph = chain_graph(size)
        baseline_runs = repeat(lambda: baseline_topological_sort(graph), repeat=5, number=1)
        kahn_runs = repeat(lambda: kahn_topological_sort(graph), repeat=5, number=1)
        baseline_ms = median(baseline_runs) * 1000
        kahn_ms = median(kahn_runs) * 1000
        _, baseline_scans, _ = counted_baseline(graph)
        _, kahn_edge_touches = counted_kahn(graph)
        print(
            f"{size:5d}  {baseline_ms:11.3f}  {kahn_ms:7.3f}  "
            f"{baseline_ms / kahn_ms:5.1f}x  {baseline_scans:20,d}  {kahn_edge_touches:17,d}"
        )
if __name__ == "__main__":
    main()

The captured run produced this output:

Baseline order: ['fetch', 'parse', 'compile', 'lint', 'test', 'package']
Kahn order:    ['fetch', 'lint', 'parse', 'compile', 'test', 'package']
Both valid:    True
Cycle check:   graph contains a cycle
Chain benchmark (median of 5 repeats, one call per repeat)
nodes  baseline_ms  kahn_ms  ratio  baseline_node_scans  kahn_edge_touches
  200        3.426    0.243   14.1x                20,100                398
  500       17.787    0.719   24.7x               125,250                998
 1000       85.640    1.376   62.3x               500,500              1,998
 2000      264.811    2.917   90.8x             2,001,000              3,998

The results show the shape of the work more clearly than the milliseconds. At 2,000 nodes, the scan method inspects 2,001,000 candidate positions. Kahn’s version touches 3,998 edge endpoints in its two passes. The measured median ratio grows from 14.1x at 200 nodes to 90.8x at 2,000 nodes on this machine and this input.

The two valid orders differ because the graph does not require lint to come before fetch, or the other way round. If a project needs a reproducible preference, the ready queue can be replaced with a heap, at the cost of extra queue operations. That is a policy choice, not a correction to the topological sort itself.

What the benchmark does not prove

This is a deliberately simple chain. It exposes the repeated scan’s worst behaviour, so it is useful for showing the growth in work but not for predicting every production graph. A wide graph with many ready nodes can make the baseline look less embarrassing, especially when the graph is small.

The measurements came from CPython 3.13.5 on a Raspberry Pi running Linux 6.12.47, with five repeats and one call per repeat. Graph construction happens inside both timed functions, while the test graph itself is built before timing. The machine was otherwise uncontrolled, and the reported milliseconds will vary with processor load, Python build and operating system. The ratios are more portable than the absolute times, but they are still measurements of this workload, not a promise that Kahn’s algorithm is always faster.

The practical rule is simple: use the repeated scan when its small size and clarity matter more than its worst case. Use Kahn’s algorithm when the dependency graph is large enough that revisiting old nodes has become visible. Either way, keep the cycle check. A schedule that quietly ignores a loop is not a schedule; it is a future debugging session.