Topological Sort in Python With Kahn's Algorithm

The real problem: apply order

A deploy tool that applies Kubernetes manifests in file order can apply a Deployment before the ConfigMap it uses. The pod then fails with configmap "web-config" not found. The fix is to sort the manifests so dependencies come first:

web-config (ConfigMap)  ->  web-pod (Pod)
web-secret (Secret)     ->  web-pod (Pod)

This is a directed acyclic graph (DAG), and a dependency-first order of a DAG is a topological order. Build systems, package managers, task schedulers like Airflow, and spreadsheet recalculation use the same idea.

Kahn's algorithm, step by step

1. For every node, count how many dependencies it is still waiting for. This is its in-degree.
2. Put every node with in-degree 0 into a "ready" queue.
3. Take a node from the queue and add it to the output.
4. For every node that depends on it, lower its in-degree by 1. If it reaches 0, add it to the queue.
5. Repeat until the queue is empty.
6. If the output has fewer nodes than the input, the remaining nodes are in a cycle - no valid order exists.

Python implementation

import heapq
from dataclasses import dataclass


@dataclass
class Manifest:
    name: str
    kind: str
    depends_on: list[str]


def order_apply(manifests: list[Manifest]) -> list[Manifest]:
    by_name = {m.name: m for m in manifests}
    in_degree = {m.name: 0 for m in manifests}
    dependents = {m.name: [] for m in manifests}

    for m in manifests:
        for dep in m.depends_on:
            if dep in by_name:            # ignore names not in the input
                dependents[dep].append(m.name)
                in_degree[m.name] += 1

    # A min-heap gives a stable order: smallest name first when several are ready
    ready = [name for name, d in in_degree.items() if d == 0]
    heapq.heapify(ready)

    out = []
    while ready:
        name = heapq.heappop(ready)
        out.append(by_name[name])
        for nxt in dependents[name]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(ready, nxt)

    if len(out) != len(manifests):
        raise ValueError('cycle detected')
    return out

Each node is pushed and popped once, and each edge is processed once, so the work is O(V + E) plus the heap cost. A plain collections.deque is enough if you do not need a fixed order between ready nodes.

Test the important cases

M = Manifest
# Diamond: d needs b and c, both need a
out = order_apply([M('d','Pod',['b','c']), M('b','X',['a']),
                   M('c','X',['a']), M('a','X',[])])
assert [m.name for m in out] == ['a', 'b', 'c', 'd']

# Cycle: a -> b -> c -> a
try:
    order_apply([M('a','X',['c']), M('b','X',['a']), M('c','X',['b'])])
    assert False, 'expected ValueError'
except ValueError:
    pass

# Empty input
assert order_apply([]) == []

Also test a long chain (for example 1,000 nodes in shuffled input order). A correct O(V + E) implementation handles it instantly. A version that scans all nodes again on every step is O(V^2) and gets slow as the input grows.

Common mistakes

• Edges in the wrong direction. Store "who depends on me" (dependents), not only "what I depend on", so step 4 is a direct lookup.
• Forgetting cycle detection. Without the final length check, a cycle silently drops nodes from the output.
• Non-deterministic order. Iterating a set can change the order between runs. Use a heap or sort the ready list when stable output matters.
• Recursion limits. A DFS-based topological sort can hit Python's recursion limit on long chains. Kahn's algorithm is iterative and avoids it.

Standard library option

Since Python 3.9, graphlib.TopologicalSorter does this for you:

from graphlib import TopologicalSorter, CycleError

graph = {'web-pod': {'web-config', 'web-secret'}, 'web-config': set(), 'web-secret': set()}
print(list(TopologicalSorter(graph).static_order()))

It raises CycleError on a cycle. Knowing how to write Kahn's algorithm yourself is still useful: it is a common interview question, and real tools often need custom tie-breaking or partial ordering.