The graphlib module provides TopologicalSorter, a class for ordering tasks that have dependencies. A topological order arranges nodes in a directed acyclic graph so every prerequisite appears before the item that depends on it. This pattern appears in build systems, data pipelines, migrations, package installation, report generation, and job orchestration.
The module is not a general graph library. It does not calculate shortest paths, centrality, components, or flows. Its focus is dependency ordering and an incremental API that allows several ready nodes to run in parallel.
The dependency model
TopologicalSorter accepts a mapping where each key is a node and the value is an iterable containing that node’s predecessors.
from graphlib import TopologicalSorter
graph = {
"test": {"install"},
"package": {"test"},
"publish": {"package"},
"install": set(),
}
order = tuple(TopologicalSorter(graph).static_order())
print(order)
The relationship means “this task depends on these predecessors.” Reversing that interpretation is a common source of incorrect schedules.
Nodes must be hashable
Nodes are stored in dictionaries and sets, so they must be hashable. Strings, numbers, enums, and immutable tuples are natural choices.
Do not use mutable objects with unstable hashes. Keep a compact immutable task ID in the graph and store detailed metadata in a separate mapping.
Implicit predecessor nodes
A predecessor mentioned in a value does not have to appear as an explicit key. The sorter adds it as a node with no known predecessors.
graph = {
"deploy": {"build"},
}
Here build becomes part of the graph. The convenience is useful, but declaring every node explicitly improves validation and documentation.
static_order
static_order() is the simplest way to produce a complete valid order.
sorter = TopologicalSorter(graph)
for task in sorter.static_order():
run(task)
The result is an iterator. Consume it once or convert it to a tuple when the sequence must be reused.
Several orders may be valid
When two tasks are independent, either relative order can satisfy the graph. Tests should not demand one exact total sequence unless the application adds another deterministic rule.
Validate precedence instead: every predecessor must appear before its dependent. Sort ready nodes by a stable key when deterministic presentation is required.
Cycle detection
A topological order exists only for an acyclic graph. A dependency cycle raises CycleError.
from graphlib import CycleError, TopologicalSorter
try:
order = tuple(TopologicalSorter({
"a": {"b"},
"b": {"a"},
}).static_order())
except CycleError as error:
print("cycle detected", error)
A cycle means none of its tasks can begin because each waits for another member of the same group.
Reporting cycles
The exception contains information that helps identify a cycle, but it should not be treated as a complete user-facing reporting API. Convert task IDs into readable names and display a clear chain.
A graph may contain several cycles. Fixing the first one can reveal another, so validate again after every correction.
Add nodes incrementally
add(node, *predecessors) adds or extends dependencies before preparation.
sorter = TopologicalSorter()
sorter.add("compile", "generate_code")
sorter.add("test", "compile")
sorter.add("publish", "test")
Repeated calls for one node merge predecessor sets. This is useful when plugins contribute dependency edges.
prepare
The incremental execution API begins with prepare(). It validates the graph and enables get_ready() and done().
sorter.prepare()
Do not add new dependencies after the graph has been prepared. Construct and validate the entire configuration first.
get_ready
get_ready() returns nodes whose predecessors have already been marked complete.
ready = sorter.get_ready()
for task in ready:
start(task)
Returned nodes become “in progress.” They are not returned again, so the coordinator must call done() when they finish.
done
done(*nodes) marks previously ready nodes as complete.
sorter.done("generate_code")
new_ready = sorter.get_ready()
Do not mark a node that was never returned by get_ready(). Invalid state transitions raise errors.
is_active
is_active() reports whether progress remains possible: either ready nodes have not been retrieved or in-progress nodes may still complete.
while sorter.is_active():
for task in sorter.get_ready():
run(task)
sorter.done(task)
In parallel execution, completed tasks normally arrive through a result queue or future set.
Parallel execution
The incremental API can submit every ready node to workers, wait for completions, and release dependent nodes.
from concurrent.futures import ThreadPoolExecutor, wait, FIRST_COMPLETED
sorter.prepare()
active = {}
with ThreadPoolExecutor(max_workers=4) as executor:
while sorter.is_active():
for task in sorter.get_ready():
active[executor.submit(run, task)] = task
completed, _ = wait(active, return_when=FIRST_COMPLETED)
for future in completed:
task = active.pop(future)
future.result()
sorter.done(task)
A production version also needs failure, cancellation, and shutdown policies.
Task failures
A failed task should not automatically be marked complete when its dependents require a valid result. The coordinator must choose whether to stop the pipeline, mark descendants blocked, or use a documented fallback.
Keep distinct states such as succeeded, failed, cancelled, skipped, and blocked.
Cancellation
During cancellation, stop submitting new nodes, request cooperative worker cancellation, and wait for a deadline. Do not call done() on incomplete tasks merely to empty the sorter.
Optional paths should be modeled explicitly outside the mandatory dependency graph.
Optional dependencies
TopologicalSorter represents required precedence. Feature flags, environment conditions, and optional plugins need a graph-building phase that creates the effective graph before prepare().
Remove disabled nodes and rewrite their edges before execution begins.
Validate references
Because missing predecessor keys become implicit nodes, a typo can silently create a phantom task.
declared = set(configuration)
referenced = set().union(*configuration.values())
unknown = referenced - declared
Decide whether implicit nodes are allowed. User-configured pipelines often benefit from rejecting unknown names.
Separate identity from execution
Keep task IDs in the graph and functions in another mapping.
tasks = {
"extract": lambda: extract(data),
"transform": transform,
"load": load,
}
This keeps the graph serializable, improves logs, and prevents validation from executing code.
Side effects and idempotency
A valid order does not protect against partial writes. Tasks that update files, databases, or APIs need idempotency keys, transactions, and rollback plans.
When resuming a pipeline, do not assume that a logged start means successful completion. Persist checkpoints only after a verifiable result.
Priorities
The module does not prioritize simultaneously ready nodes. The coordinator may sort the tuple returned by get_ready().
for task in sorted(sorter.get_ready(), key=priority):
start(task)
Priority can choose among released nodes but cannot violate dependencies.
Concurrency limits
Not every ready task should start immediately. Respect worker counts, database pool capacity, memory, network bandwidth, and rate limits.
Maintain a local ready queue or submit only up to available capacity. See Python concurrent.futures for backpressure and executor design.
Resource classes
Some tasks consume CPU, others use databases or networks. One global worker limit may be inappropriate. Use separate executors or semaphores by resource type.
The graph describes precedence; the scheduler describes capacity.
Persistent workflow state
TopologicalSorter is not a durable workflow engine. A process restart loses in-memory progress.
Critical pipelines should persist the graph, attempts, outputs, timestamps, and status in transactional storage. Rebuild a sorter only to determine which tasks may proceed.
Large graphs
Topological sorting normally scales with the number of nodes and edges, but representation and memory still matter. Avoid unnecessary duplicate structures.
Use compact IDs and enforce limits before accepting external configurations.
Untrusted graph input
A user can submit a graph with huge identifiers, millions of edges, or extreme fan-in and consume CPU and memory.
Limit node count, edge count, identifier length, and preparation time. Never map task names directly to imports or shell commands without an allowlist.
Visualization
The module does not generate diagrams. Export edges to DOT, JSON, or a table for debugging. Highlight cycles, blocked tasks, and leaf nodes.
Visualization becomes especially valuable when plugins add dependencies automatically.
Testing
Test an empty graph, one node, a linear chain, independent branches, convergence, multiple valid orders, cycles, unknown references, task failure, cancellation, and parallel completion.
When order is not unique, assert precedence constraints rather than an exact list.
Common mistakes
Common failures include reversing the dependency direction, requiring one exact order, forgetting done(), marking failed tasks complete, adding nodes after preparation, accepting typos as implicit tasks, launching unlimited work, and treating the sorter as a persistent workflow system.
Conclusion
graphlib.TopologicalSorter provides a direct solution for dependency ordering and an incremental interface suitable for parallel schedulers. Model predecessors correctly, validate cycles and names, cap concurrency, and keep execution state separate from graph structure.
Consult the official graphlib documentation and Python multiprocessing when workers require separate processes.
