A build graph contains these edges:
parse -> typecheck -> bundle -> parse
There is no valid first task. A topological sort should not return a partial list and quietly stop; it should explain why the graph cannot be ordered.
This project teaches two connected ideas:
- Kahn's algorithm produces an order for a directed acyclic graph (DAG).
- A separate depth-first search can turn “some cycle exists” into a concrete cycle a learner can inspect.
Prerequisites: Python 3.11+ and basic familiarity with dictionaries, sets, and queues. The code uses only the standard library.
Define the graph contract
We represent each task with the tasks it depends on:
graph = {
"bundle": {"typecheck"},
"typecheck": {"parse"},
"parse": set(),
}
An edge parse -> typecheck means parse must appear first. A dependency mentioned only inside a set is still a node, so normalization must add it.
Order the acyclic case
Kahn's algorithm tracks each node's in-degree: the number of prerequisites not yet removed.
from collections import deque
def normalize(graph):
nodes = set(graph)
for dependencies in graph.values():
nodes.update(dependencies)
return {node: set(graph.get(node, set())) for node in nodes}
def topological_order(graph):
dependencies = normalize(graph)
dependents = {node: set() for node in dependencies}
for node, prerequisites in dependencies.items():
for prerequisite in prerequisites:
dependents[prerequisite].add(node)
ready = deque(sorted(
node for node, prerequisites in dependencies.items()
if not prerequisites
))
order = []
while ready:
node = ready.popleft()
order.append(node)
for dependent in sorted(dependents[node]):
dependencies[dependent].remove(node)
if not dependencies[dependent]:
ready.append(dependent)
remaining = {node for node, deps in dependencies.items() if deps}
if remaining:
return None, remaining
return order, set()
Try it:
graph = {
"bundle": {"typecheck"},
"typecheck": {"parse"},
"parse": set(),
"test": {"typecheck"},
}
print(topological_order(graph))
Expected output (the exact order of equally ready tasks depends on queue policy):
(['parse', 'typecheck', 'bundle', 'test'], set())
Sorting ready names makes this example deterministic. Real schedulers may instead prioritize cost, critical path, or resource availability.
Why a partial result is not enough
Now introduce a cycle:
cyclic = {
"parse": {"bundle"},
"typecheck": {"parse"},
"bundle": {"typecheck"},
}
print(topological_order(cyclic))
Expected result:
(None, {'parse', 'typecheck', 'bundle'})
Kahn's algorithm proves ordering failed, but remaining can include nodes merely blocked by a cycle. It does not necessarily show cycle edges. We need a second pass.
Extract one concrete cycle
Depth-first search assigns three states:
unseen: not visited;
active: on the current recursion path;
done: fully explored.
An edge to an active node is a back edge and therefore closes a cycle.
def find_cycle(graph, candidates=None):
graph = normalize(graph)
allowed = set(graph) if candidates is None else set(candidates)
state = {node: "unseen" for node in graph}
stack = []
position = {}
def visit(node):
state[node] = "active"
position[node] = len(stack)
stack.append(node)
for dependency in sorted(graph[node]):
if dependency not in allowed:
continue
if state[dependency] == "unseen":
cycle = visit(dependency)
if cycle:
return cycle
elif state[dependency] == "active":
start = position[dependency]
return stack[start:] + [dependency]
stack.pop()
position.pop(node)
state[node] = "done"
return None
for node in sorted(allowed):
if state[node] == "unseen":
cycle = visit(node)
if cycle:
return cycle
return None
Combine both stages:
def schedule(graph):
order, remaining = topological_order(graph)
if order is not None:
return {"order": order, "cycle": None}
return {"order": None, "cycle": find_cycle(graph, remaining)}
print(schedule(cyclic))
Expected structure:
{'order': None, 'cycle': ['bundle', 'typecheck', 'parse', 'bundle']}
The start node may vary, but the last item must equal the first, and every adjacent pair must be a real dependency edge.
Tests that verify meaning
Avoid testing only one exact printed cycle because several rotations can be correct.
def assert_valid_order(graph, order):
index = {node: i for i, node in enumerate(order)}
normalized = normalize(graph)
assert set(order) == set(normalized)
for node, dependencies in normalized.items():
for dependency in dependencies:
assert index[dependency] < index[node]
def assert_valid_cycle(graph, cycle):
normalized = normalize(graph)
assert cycle[0] == cycle[-1]
for node, dependency in zip(cycle, cycle[1:]):
assert dependency in normalized[node]
order, remaining = topological_order(graph)
assert remaining == set()
assert_valid_order(graph, order)
result = schedule(cyclic)
assert result["order"] is None
assert_valid_cycle(cyclic, result["cycle"])
Add three error-shaped fixtures:
# Self-cycle
assert_valid_cycle({"a": {"a"}}, schedule({"a": {"a"}})["cycle"])
# A cycle plus a node blocked by it
blocked = {"a": {"b"}, "b": {"a"}, "deploy": {"a"}}
assert_valid_cycle(blocked, schedule(blocked)["cycle"])
# A disconnected valid component plus a cycle
mixed = {"lint": set(), "a": {"b"}, "b": {"a"}}
assert_valid_cycle(mixed, schedule(mixed)["cycle"])
Complexity and limitations
Both passes are O(V + E) apart from sorting, which adds deterministic output at a cost. Recursive DFS can hit Python's recursion limit on very deep graphs; an iterative stack is safer for untrusted or huge input.
This scheduler also assumes dependencies are static and tasks consume no limited resources. A production build system must consider caching, parallelism, task failures, and changing inputs. Topological order answers only one question: which precedence constraints are mathematically possible?
What you should understand
Kahn's algorithm and DFS do different jobs. Kahn's algorithm constructs an order and detects that some dependency cannot be removed. DFS explains a specific contradiction in the graph. Combining them produces both a useful success result and a useful failure result.
As an extension, change find_cycle() to return every strongly connected component with more than one node. That leads naturally to Tarjan's or Kosaraju's algorithm—and to better diagnostics for real build graphs.
SOCIAL SHARE CARD GENERATOR