Python graphlib: Topological Sorting for Tasks

graphlib.TopologicalSorter solves a recurring build, pipeline, and migration problem: ordering tasks while respecting dependencies. Its input maps each node to predecessors, not successors.

from graphlib import CycleError, TopologicalSorter

dependencias = {
    "testar": {"instalar"},
    "empacotar": {"testar"},
    "publicar": {"empacotar"},
    "instalar": set(),
}

try:
    ordem = tuple(TopologicalSorter(dependencias).static_order())
    print(ordem)
except CycleError as erro:
    print("Ciclo detectado:", erro.args[1])

Use static_order() when a single sequence is enough. A cycle raises CycleError. Do not treat the exact order among independent nodes as a contract because multiple sequences may be valid.

Practical guidance

For parallel execution, combine prepare(), get_ready(), and done() to release tasks as their predecessors finish. Keep nodes hashable and validate external configuration before building the graph. A cycle usually means invalid configuration and should stop execution.

For priority-based work, see Python heapq. When related tasks are coroutines, asyncio.TaskGroup provides structured failure and cancellation.

The official graphlib documentation, accessed July 22, 2026, documents the API and its guarantees.

Modeling dependencies

Each mapping key is a node and its values are predecessors that must finish first. To say compile depends on generate, write {"compile": {"generate"}}. This direction is easy to reverse because other graph formats list successors. A predecessor omitted as a key still becomes a node.

Use stable, hashable identifiers such as strings or enums and keep commands in another mapping. This separation permits validation and display without side effects.

from graphlib import TopologicalSorter

graph = {
    "fetch": set(),
    "validate": {"fetch"},
    "transform": {"validate"},
    "report": {"validate"},
    "publish": {"transform", "report"},
}
order = list(TopologicalSorter(graph).static_order())
position = {node: i for i, node in enumerate(order)}
assert position["validate"] < position["transform"]
assert position["report"] < position["publish"]

Test required relationships, not one full sequence. Independent nodes may exchange positions.

Cycles and failures

A cycle means no complete valid order exists. It can be a self-reference or a long chain returning to its start. CycleError carries details in args, but applications should translate them into a clear domain message.

After prepare() detects a cycle, unrelated nodes may remain available. That helps diagnostic tools, but builds and migrations usually should fail before effects occur. Running only the possible portion can leave a surprising partial state.

Parallel execution

Use prepare(), get_ready(), and done() to exploit independent work. Submit ready nodes and report completion only after success.

from concurrent.futures import FIRST_COMPLETED, ThreadPoolExecutor, wait
from graphlib import TopologicalSorter

sorter = TopologicalSorter(graph)
sorter.prepare()
futures = {}
with ThreadPoolExecutor(max_workers=4) as executor:
    while sorter.is_active():
        for name in sorter.get_ready():
            futures[executor.submit(run, name)] = name
        completed, _ = wait(futures, return_when=FIRST_COMPLETED)
        for future in completed:
            name = futures.pop(future)
            future.result()
            sorter.done(name)

Call done() once and only after success. If result() raises, dependents remain blocked. Production code should cancel pending work and record completed tasks. Marking a failure complete gives successors a false premise.

Lifecycle and validation

Add dependencies before ordering. After prepare(), treat the graph as closed and create another sorter when configuration changes. Normalize external input and avoid mutating predecessor sets while in use.

Duplicate edges do not matter, but a missing edge may release work too early. Validate references, blank names, disabled stages, and conditional dependencies. Limit node and edge counts for untrusted input.

Determinism

A DAG may allow several orders. Do not make observed ordering among independent nodes an accidental contract. For reproducible logs, normalize input and sort only each ready batch. Alphabetically sorting the final output can violate dependencies. Runtime completion can still vary under parallelism.

Scope and complexity

Sorting visits nodes and edges, so cost scales with graph size. Task execution is normally more expensive. graphlib is not a full scheduler: it has no persistence, retry, timeout, priority, resource lock, or distributed coordination. It identifies runnable work; the application executes and recovers.

Use cases include ETL, builds, service initialization, migrations, and prerequisites. Priority and preference are not necessarily dependencies and belong in separate policies.

Testing strategy

Cover an empty graph, isolated node, chain, branch, merge, and cycle. Verify every predecessor appears before its dependent and every node occurs once. In incremental mode, ensure done() releases exactly the expected successors. Simulate a task failure without done() and confirm dependents never start.

Record duration, status, and error by node. If tasks have effects, make them idempotent or define compensation because one may fail after others complete.

Checklist

Confirm edge direction, normalize identifiers, and reject cycles before irreversible effects. Never depend on ordering among unrelated nodes. Call done() only for real success. Define cancellation and partial-state handling. For workflows that survive restarts or coordinate machines, use TopologicalSorter for planning and add durable execution infrastructure.