A large software project has 500 source files. Some files depend on others — file A includes file B, so B must be compiled before A. The build system must determine the correct compilation order.
A database has 30 migration files. Each migration assumes a specific schema state; migrations must be applied in the right order or the database ends up corrupted.
A CI/CD pipeline has 15 stages. Some stages can run in parallel; others must wait for specific stages to complete. The orchestrator must find the correct execution order and maximise parallelism.
All three are the same problem: given a set of tasks and dependencies between them, find an ordering where every dependency comes before the task that depends on it. This is topological sort on a directed acyclic graph (DAG).
What Topological Sort Actually Is
A DAG is a directed graph with no cycles. A topological ordering is a linear ordering of the nodes such that for every directed edge (u → v), u appears before v.
Topological orderings are not unique. A DAG with independent nodes may have many valid orderings. The key constraint is: no node appears before its predecessors.
A topological ordering exists if and only if the graph is a DAG. Any cycle makes ordering impossible — if A must precede B and B must precede A, no valid order exists. The detection of this case is a useful side effect of the algorithm.
There are two algorithms:
DFS-based. Run depth-first search; when a node finishes (all descendants processed), prepend it to the output. O(V+E).
Kahn's algorithm (BFS-based). Start with nodes that have no incoming edges (in-degree 0); process each, decrement the in-degree of its neighbours; add to queue any neighbour whose in-degree reaches 0. O(V+E).
Kahn's algorithm has one practical advantage that matters in production: it naturally detects cycles. If the output contains fewer than V nodes, a cycle prevented some nodes from ever reaching in-degree 0. That is also the entire cycle-detection logic — no separate pass needed for the existence check.
Kahn's Algorithm, Concretely
from collections import defaultdict, deque
def topological_sort_kahn(nodes, dependencies):
"""
dependencies[task] = list of tasks that must complete before task.
Returns tasks in valid execution order. Raises on cycle.
"""
in_degree = defaultdict(int)
graph = defaultdict(list) # prerequisite -> [tasks that need it]
for task in nodes:
in_degree[task] = in_degree.get(task, 0)
for task, prereqs in dependencies.items():
for prereq in prereqs:
graph[prereq].append(task)
in_degree[task] += 1
queue = deque([t for t in nodes if in_degree[t] == 0])
order = []
while queue:
task = queue.popleft()
order.append(task)
for dependent in graph[task]:
in_degree[dependent] -= 1
if in_degree[dependent] == 0:
queue.append(dependent)
if len(order) != len(nodes):
raise ValueError("Cycle detected — no valid topological order exists")
return order
Applied to a small build:
source_files = ['main.c', 'utils.c', 'utils.h', 'io.c', 'io.h']
compile_deps = {
'main.c': ['utils.h', 'io.h'],
'utils.c': ['utils.h'],
'io.c': ['io.h'],
'utils.h': [],
'io.h': [],
}
# build_order = ['utils.h', 'io.h', 'utils.c', 'io.c', 'main.c']
Parallelism Falls Out of It
A linear topological order is the worst-case serialisation. The true constraint is the partial order — a set of "must come before" relationships. Nodes with no path between them are independent and can run in parallel.
Grouping nodes into levels makes this concrete:
def build_levels(nodes, dependencies):
"""
Level 0: tasks with no prerequisites.
Level k: tasks whose prerequisites are all in levels < k.
"""
# ... same in_degree setup ...
levels, ready = [], deque([t for t in nodes if in_degree[t] == 0])
while ready:
level = list(ready)
levels.append(level)
ready = deque()
for task in level:
for dependent in graph[task]:
in_degree[dependent] -= 1
if in_degree[dependent] == 0:
ready.append(dependent)
return levels
Bazel's build parallelism is computed exactly this way: build all tasks at the same level in parallel, wait for all to complete, advance to the next level.
The number of levels is the critical path length — the longest chain of sequential dependencies. This is the minimum wall-clock time, regardless of how many parallel workers you have. Adding workers reduces the time below the critical path is not possible.
Database Migrations Use the Same Shape
A migration tool (Alembic, Flyway, Liquibase) applies schema changes in order. Each migration has an identifier and may declare which migrations it depends on. The dependency graph is a DAG; the application order is a topological sort.
The critical property: a migration that adds a foreign key referencing a table created in another migration must come after the migration that creates that table. Topological sort guarantees the correct order. Get the order wrong, and the migration fails with a database constraint error.
Alembic uses a DAG of migration scripts where each declares down_revision (the migration it depends on). The alembic upgrade head command runs a topological sort of all pending migrations and applies them in order.
CI/CD Pipelines: Event-Driven Kahn's
A CI/CD pipeline has stages (test, build, security-scan, deploy-staging, integration-test, deploy-prod). Each stage has dependencies. The orchestrator needs to:
- Determine which stages can start immediately (in-degree 0).
- Start all immediately-ready stages in parallel.
- When a stage completes, check if any dependent stages are now unblocked.
This is Kahn's algorithm run as an event-driven process: each stage completion triggers in-degree updates and potentially unblocks new stages. The batch version computes the order up front. The event-driven version reacts to completions. For long-running pipelines where stages take hours, the asynchronous model is essential — you do not wait for one stage to finish before deciding which stages become ready.
GitHub Actions implements this with the needs: syntax. Steps that declare needs: [test, build] are held until both test and build complete. The Actions runner computes which steps are ready at any moment using in-degree tracking.
The Tradeoffs
AT5 (Centralisation vs Distribution). A centralised build system runs the topological sort and distributes tasks to workers — it has a global view of the dependency graph and can optimise distribution. A distributed build system requires nodes to exchange state to discover when dependencies are satisfied. Centralised is simpler; distributed is more resilient to coordinator failure.
AT10 (Synchronous vs Asynchronous). Batch topological sort (compute full order, then execute) is synchronous and predictable. Event-driven (each completed stage triggers in-degree updates) is asynchronous and maximally parallel. For long-running pipelines, the asynchronous model wins. For short builds (< 1 minute total), batch simplicity wins.
Where It Fails
FM8 (Schema/Contract Violation). A cycle in the dependency graph means no valid order exists. Kahn's detects cycles cheaply (output length < node count) but does not tell you which edges form the cycle. Cycle-finding requires a separate DFS pass. The failure mode is almost always a newly added dependency that inadvertently creates a cycle between two existing nodes. The bug is in the dependency declaration, not the algorithm.
FM5 (Latency Amplification). The critical path length determines minimum pipeline duration. Adding a new dependency that lengthens the critical path — even if the new stage is fast — increases minimum build time. Teams that do not track the critical path add "quick" stages and are surprised when total duration increases. The stage itself takes 30 seconds; but it was added to the critical path, converting a previously parallel branch into a sequential dependency.
The Three Real Systems Engineers Already Use
Bazel (Google's open-source build system) models all build targets as nodes in a DAG. It computes build parallelism by finding independent subgraphs. Build tasks can be distributed across a remote cache and executor cluster, with the topological sort determining which tasks are eligible at each step.
Alembic (SQLAlchemy migrations) uses a DAG of migration scripts. Each script declares down_revision. The upgrade command runs a topological sort and applies pending migrations in order.
GitHub Actions pipelines use the needs: syntax to declare a DAG. The Actions runner computes which steps are ready at any moment using in-degree tracking — exactly Kahn's algorithm in event-driven form.
This article extracts the core of Book 2, Chapter 8 — Topological Sort in Engineering. The chapter includes the full DFS variant, the parallel-pipeline orchestrator code, the critical-path computation with the seven-stage CI walkthrough, and the data-platform design problem with 200 daily transformation jobs.