Topological sort

Deep dive

How it works

In: directed graph as adjacency lists (edge u → v: u must come first) · Out: an order in which every edge points forward, or the vertices on or behind a cycle · State: none between calls; per call an in-degree array and the output order · Cost: O(V + E) time and memory

1. Compute indeg[v] for all v.
2. Ready = all vertices with in-degree 0.
3. Pop u from ready and append it to the order. For each u → v, decrement indeg[v], and if it reaches 0, push v.
4. If the order has fewer than V vertices, those with indeg > 0 are on or behind a cycle. (This is Kahn's algorithm.)
5. Alternative: run DFS. When a vertex finishes (all its descendants are done), append it to the postorder, then reverse. A gray-to-gray edge (back edge) means a cycle.

a → b → d          indeg: a0 b1 c1 d2
a → c → d          Kahn: [a] → [b c] → [d]       waves: {a} {b,c} {d}

Code

/// Kahn's algorithm. Ok(order) or Err(vertices that are on or downstream of a cycle).
pub fn topo_sort(adj: &[Vec<u32>]) -> Result<Vec<u32>, Vec<u32>> {
    let n = adj.len();
    let mut indeg = vec![0u32; n];
    for vs in adj { for &v in vs { indeg[v as usize] += 1; } }
    let mut order: Vec<u32> = (0..n as u32).filter(|&v| indeg[v as usize] == 0).collect();
    let mut head = 0; // `order` doubles as the FIFO queue
    while head < order.len() {
        let u = order[head];
        head += 1;
        for &v in &adj[u as usize] {
            indeg[v as usize] -= 1;
            if indeg[v as usize] == 0 { order.push(v); }
        }
    }
    if order.len() == n {
        Ok(order)
    } else {
        Err((0..n as u32).filter(|&v| indeg[v as usize] > 0).collect())
    }
}

/// Wave per task (same wave = can run in parallel) and the critical-path length for given durations.
pub fn schedule(adj: &[Vec<u32>], dur: &[u64]) -> Option<(Vec<u32>, u64)> {
    let order = topo_sort(adj).ok()?;
    let mut wave = vec![0u32; adj.len()];
    let mut finish = vec![0u64; adj.len()]; // holds the latest predecessor finish until u is processed
    for &u in &order {
        let u = u as usize;
        finish[u] += dur[u];
        for &v in &adj[u] {
            let v = v as usize;
            wave[v] = wave[v].max(wave[u] + 1);
            finish[v] = finish[v].max(finish[u]);
        }
    }
    Some((wave, finish.into_iter().max().unwrap_or(0)))
}

/// Deterministic order: always take the smallest ready vertex.
pub fn topo_sort_lex(adj: &[Vec<u32>]) -> Option<Vec<u32>> {
    use std::{cmp::Reverse, collections::BinaryHeap};
    let mut indeg = vec![0u32; adj.len()];
    for vs in adj { for &v in vs { indeg[v as usize] += 1; } }
    let mut ready: BinaryHeap<Reverse<u32>> =
        (0..adj.len() as u32).filter(|&v| indeg[v as usize] == 0).map(Reverse).collect();
    let mut order = Vec::with_capacity(adj.len());
    while let Some(Reverse(u)) = ready.pop() {
        order.push(u);
        for &v in &adj[u as usize] {
            indeg[v as usize] -= 1;
            if indeg[v as usize] == 0 { ready.push(Reverse(v)); }
        }
    }
    (order.len() == adj.len()).then_some(order)
}

Complexity and constants

• Kahn: one pass to count in-degrees and one pass over the edges. 4 B per vertex for indeg, and the output doubles as the queue.
• On CSR graphs that fit in cache, order of 1-10 ns per edge. On larger graphs it is bound by random indeg[v] updates, about one cache miss per edge.
• Heap-based lexicographic order: O(log V) per vertex extra, fine up to about 10⁷ vertices.
• Critical-path scheduling with unlimited workers finishes in time = longest path. With p workers, list scheduling is within 2× of optimal (Graham).

Efficiency

• Cost: measured with the code above on an Apple M4 Pro, one thread, random DAG with 2^20 vertices and 8 · 2^20 edges as Vec<Vec<u32>>, best of 3: Kahn 122 ms (14.6 ns per edge); with waves and critical path (schedule) 234 ms; lexicographic order with a heap 135 ms. Memory: 4 B per vertex for indeg, the output doubles as the queue. Bound: random indeg[v] updates (cache misses).
• Levers:
  • plain Kahn instead of the heap for a deterministic order — 1.11× (135 vs 122 ms; measured) — only pay when stable output matters
  • CSR instead of Vec<Vec<u32>> — 1.56× for BFS at 2^20 vertices (measured on BFS/DFS, not on Kahn) — graphs that fit in cache
  • atomic in-degree counters and a work queue — no global sort, the order emerges while tasks run (Implementation notes) — parallel executors
  • critical-path-first among ready tasks — list scheduling stays within 2× of optimal (Graham 1969) — p workers, wide graphs
  • Pearce-Kelly order maintenance — reorders only the region between the endpoints (Pearce, Kelly 2006) — graphs that change by edge insertion
• Naive → standard → state of the art:
  • rescan all vertices for one with no unprocessed predecessor · O(V²) at least
  • Kahn with a queue (code above) · 122 ms, 14.6 ns per edge on the graph above
  • parallel executor with atomic counters, incremental order maintenance · work per edge stays O(1) (Implementation notes)

Implementation notes

• Parallel executor (make -j, Bazel, Cargo): keep atomic in-degree counters. Each worker finishes a task, decrements its successors, and pushes those that reach 0 onto a work queue (work-stealing deque). No global sort is needed, and the order emerges dynamically.
• Prioritize the critical path: among ready tasks, start the one with the longest remaining path to a sink first. This often cuts wall time on wide builds.
• Cycle reporting: Kahn tells you that there is a cycle. To show the user which one, run DFS on the leftover vertices and print the gray stack when a back edge appears.
• Stable output: iterate over sorted vertex IDs or use the heap version. HashMap iteration order makes builds and lockfiles nondeterministic.
• Duplicate edges are fine as long as counting and decrementing are consistent.
• Incremental: Pearce-Kelly maintains an order under edge insertions and only reorders the affected region between the two endpoints.

Pitfalls

• Ignoring the length check: Kahn silently returns a partial order on cyclic input.
• Recursive DFS on deep dependency chains overflows the stack. Use Kahn or an explicit stack.
• Recomputing the whole order on every small change in an interactive system (spreadsheets, reactive UIs). Use incremental or dirty-marking schemes.
• Assuming the order is unique and caching it as "the" order: any tie-break change gives a different valid order.
• Edge direction confusion ("depends on" vs "is needed by"). Reversing the edges reverses the order. Test with a 3-node chain.

Variants and alternatives

In production

Build and install: make, Ninja, Bazel, Cargo, npm/pip/apt dependency resolution (ordering step), systemd unit ordering. Data pipelines: Airflow and Dagster DAGs, Spark DAGScheduler stages (Zaharia et al. 2012). Machine learning: PyTorch autograd engine (dependency counts for the backward pass), TensorFlow graph execution. Spreadsheets: recalculation engines (Excel). Chip design: static timing analysis (Hitchcock et al. 1982).

Implementations

Sources

• A. B. Kahn, Topological Sorting of Large Networks, CACM, 1962. paper
• D. Knuth, The Art of Computer Programming, Vol. 1, §2.2.3, 1968 (3rd ed. 1997).
• R. Tarjan, Depth-First Search and Linear Graph Algorithms, SIAM Journal on Computing, 1972. paper
• D. Pearce, P. Kelly, A Dynamic Topological Sort Algorithm for Directed Acyclic Graphs, ACM Journal of Experimental Algorithmics, 2006. paper
• R. Graham, Bounds on Multiprocessing Timing Anomalies, SIAM Journal on Applied Mathematics, 1969. paper
• A. Mokhov, N. Mitchell, S. Peyton Jones, Build Systems à la Carte, ICFP 2018. paper
• R. Hitchcock, G. Smith, D. Cheng, Timing Analysis of Computer Hardware, IBM Journal of Research and Development 26(1), 1982. paper