Many automation tasks are not really lists. They are dependency graphs.

A deployment may need a database migration before the API starts, while static assets can build independently. A data pipeline may need two source extracts before a join can run. A build system may have several targets that become runnable as soon as their prerequisites finish.

If you encode this work as one hand-written sequence, you hide the real constraint: which tasks depend on which other tasks. That makes the sequence harder to change and can prevent independent work from running concurrently.

Python’s graphlib.TopologicalSorter models this problem directly. You describe each node together with its predecessors, then ask for either a valid topological order or the set of nodes whose prerequisites are complete.

A topological order is an ordering of a directed acyclic graph in which every predecessor appears before the node that depends on it. The graph must be acyclic because a cycle such as A -> B -> A has no valid starting point.

Model prerequisites, not a hand-written sequence

Suppose a release has four tasks:

  • build-assets has no prerequisite.
  • migrate-db has no prerequisite.
  • deploy-api requires migrate-db.
  • smoke-test requires both build-assets and deploy-api.

TopologicalSorter expects a mapping from each node to an iterable of its predecessors:

from graphlib import TopologicalSorter

dependencies = {
    "build-assets": set(),
    "migrate-db": set(),
    "deploy-api": {"migrate-db"},
    "smoke-test": {"build-assets", "deploy-api"},
}

sorter = TopologicalSorter(dependencies)
order = tuple(sorter.static_order())

print(order)

One valid result is:

('build-assets', 'migrate-db', 'deploy-api', 'smoke-test')

The important word is valid. build-assets and migrate-db are independent, so their relative order is not a dependency guarantee. The particular order among equally ready nodes can depend on insertion order.

Code should therefore rely on the precedence constraints, not on one exact sequence among unrelated nodes.

Understand the graph direction before adding dependencies

A common mistake is to reverse the relationship.

With TopologicalSorter, this call:

sorter.add("deploy-api", "migrate-db")

means:

deploy-api depends on migrate-db.

It does not mean that deploy-api should run before migrate-db.

The same rule applies to the constructor mapping:

{
    "deploy-api": {"migrate-db"}
}

The dictionary key is the node being described. Its values are the nodes that must precede it.

This predecessor-oriented representation is convenient for task scheduling because it matches the question a scheduler needs to answer: “What must already be complete before this task can start?”

Use static_order when you only need one valid sequence

For migrations, initialization steps, or other sequential workflows, static_order() is usually the simplest interface.

from graphlib import TopologicalSorter

dependencies = {
    "create-schema": set(),
    "load-reference-data": {"create-schema"},
    "create-indexes": {"create-schema"},
    "verify": {"load-reference-data", "create-indexes"},
}

for step in TopologicalSorter(dependencies).static_order():
    print(f"run: {step}")

This guarantees that every predecessor is yielded before the node that depends on it.

It does not guarantee a unique order. In this example, load-reference-data and create-indexes may appear in either order because neither depends on the other.

If your application needs a deterministic secondary order for independent nodes, that is an additional policy. Do not mistake it for part of topological sorting itself.

Add dependencies incrementally when configuration is assembled in pieces

You do not have to construct one dictionary first. add() can build the graph incrementally:

from graphlib import TopologicalSorter

sorter = TopologicalSorter()

sorter.add("compile")
sorter.add("unit-test", "compile")
sorter.add("package", "compile", "unit-test")

print(tuple(sorter.static_order()))

Calling add() several times for the same node accumulates predecessors rather than replacing the earlier ones.

A predecessor that has not been added explicitly is also added to the graph automatically as a node with no known predecessors.

That behavior is useful when separate modules contribute dependency information, but it can also hide spelling mistakes. If task names come from configuration, validate them against the set of known tasks before sorting.

Once sorting has been prepared, the graph is considered fixed and new dependencies cannot be added.

Detect cycles before trying to execute the whole graph

A cycle means the dependency rules contradict each other.

Consider:

from graphlib import CycleError, TopologicalSorter

dependencies = {
    "publish": {"approve"},
    "approve": {"review"},
    "review": {"publish"},
}

try:
    tuple(TopologicalSorter(dependencies).static_order())
except CycleError as error:
    cycle = error.args[1]
    print("cycle:", " -> ".join(cycle))

The three tasks form a loop. No task can be first because each waits for another task in the same cycle.

CycleError contains one detected cycle in error.args[1]. When several cycles exist, do not assume every cycle will be reported at once.

For configuration-driven systems, detecting this before starting side effects is usually preferable. It lets you reject an invalid dependency graph before only part of a deployment or pipeline has run.

Use get_ready and done when tasks may run independently

static_order() produces a sequential iterator. The lower-level interface exposes a more useful idea for schedulers: the set of tasks that are ready now.

The lifecycle is:

  1. Build the graph.
  2. Call prepare().
  3. Call get_ready() to receive nodes whose predecessors are complete.
  4. Start those nodes.
  5. Call done(node) only after a node actually finishes.
  6. Repeat while the sorter is active.

Here is a synchronous simulation:

from graphlib import TopologicalSorter

dependencies = {
    "fetch-users": set(),
    "fetch-orders": set(),
    "join-data": {"fetch-users", "fetch-orders"},
    "write-report": {"join-data"},
}

sorter = TopologicalSorter(dependencies)
sorter.prepare()

while sorter.is_active():
    ready = sorter.get_ready()

    for task in ready:
        print(f"run: {task}")
        sorter.done(task)

The first get_ready() returns both fetch tasks because neither has predecessors. join-data cannot become ready until both fetch tasks have been marked done.

That distinction matters in real concurrent code: ready means allowed to start; done means finished successfully enough to unblock dependents.

Do not call done() immediately after submitting work to a thread or process pool. Doing so would tell the sorter that dependent work is safe to start even though the prerequisite may still be running.

Separate dependency state from worker execution

A realistic scheduler often has two responsibilities:

  • TopologicalSorter tracks which tasks are eligible.
  • A worker system executes the tasks and reports completion.

A small thread-pool example makes that separation explicit:

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


def run_task(name):
    print(f"running {name}")
    return name


dependencies = {
    "fetch-users": set(),
    "fetch-orders": set(),
    "join-data": {"fetch-users", "fetch-orders"},
    "write-report": {"join-data"},
}

sorter = TopologicalSorter(dependencies)
sorter.prepare()

with ThreadPoolExecutor(max_workers=2) as executor:
    running = {}

    while sorter.is_active():
        for task in sorter.get_ready():
            future = executor.submit(run_task, task)
            running[future] = task

        completed, _ = wait(running, return_when=FIRST_COMPLETED)

        for future in completed:
            task = running.pop(future)
            future.result()
            sorter.done(task)

future.result() is deliberately called before sorter.done(task). If the worker raised an exception, result() re-raises it and the failed task is not marked complete.

This simple example stops on failure. Production schedulers may instead cancel downstream work, retry selected tasks, record failure states, or continue independent branches. Those policies sit above TopologicalSorter; the sorter only models dependency readiness.

The example uses threads because they make the scheduling mechanics easy to see. Threads are not automatically the right execution model. CPU-bound Python work may need processes or native code that releases the GIL, while I/O-heavy work may fit threads or asynchronous I/O.

Treat task failure as a scheduling policy decision

A topological sorter understands two states relevant to dependencies: a node has been reported done, or it has not.

It does not define what “successful” means for your application.

Suppose fetch-users fails. Marking it done would allow join-data to run, which is usually wrong. Leaving it unfinished prevents its dependents from becoming ready, but then the scheduler needs a policy for stopping or skipping blocked work.

A practical design often tracks execution state separately:

status = {
    "fetch-users": "failed",
    "fetch-orders": "succeeded",
    "join-data": "blocked",
}

This separation keeps two concepts distinct:

  • the graph expresses prerequisite relationships;
  • your application expresses success, retries, cancellation, and failure propagation.

Trying to encode every operational state as another graph edge usually makes the model harder to reason about.

Be careful with mutable or unknown task identifiers

Nodes must be hashable because the sorter uses them as graph identities. Strings, integers, tuples of hashable values, and many immutable domain objects work naturally.

Mutable containers such as lists cannot be nodes.

Even with strings, configuration deserves validation. This graph:

dependencies = {
    "deploy-api": {"migrate-db"},
}

implicitly introduces migrate-db as a node even if you forgot to define an executor for it.

If tasks come from a file, validate that every node has a corresponding implementation:

known_tasks = {"deploy-api"}
referenced = set(dependencies)

for predecessors in dependencies.values():
    referenced.update(predecessors)

unknown = referenced - known_tasks

if unknown:
    raise ValueError(f"unknown tasks: {sorted(unknown)}")

Whether implicit predecessor nodes are convenient or dangerous depends on how the graph is assembled. In internal Python code they can reduce boilerplate. At a configuration boundary, explicit validation is usually safer.

Do not use a dependency graph when a simpler structure is enough

TopologicalSorter is useful when work has partial ordering: some tasks depend on others while independent branches can proceed separately.

It is unnecessary for a fixed three-step sequence:

load()
transform()
save()

A list or direct function calls are clearer when the order is linear and unlikely to vary.

It is also not a general-purpose workflow engine. It does not persist state, retry tasks, enforce timeouts, distribute work, record logs, or recover after a process restart.

For a small in-process scheduler, build tool, plugin initializer, migration planner, or test dependency runner, those omissions can be advantages because the dependency mechanism remains small and explicit. For durable distributed workflows, use infrastructure designed for those operational requirements.

Know the boundary between guarantees and scheduling policy

TopologicalSorter guarantees dependency ordering for the graph you provide: a node is not ready until its predecessors have been marked done.

Several other properties are outside that guarantee:

  • Independent nodes do not have a meaningful dependency order.
  • The class does not choose how many ready tasks to run concurrently.
  • It does not decide whether failures count as completion.
  • It does not detect missing executor implementations.
  • It does not make task side effects idempotent or transactional.

Keeping that boundary clear prevents a useful graph primitive from being mistaken for a complete job scheduler.

Conclusion

When work is governed by prerequisites, model the prerequisites directly.

Use static_order() when you only need a valid sequential order. Use prepare(), get_ready(), and done() when independent tasks may execute concurrently. Detect cycles before side effects begin, validate task identifiers at configuration boundaries, and mark nodes done only after the execution policy considers them successfully complete.

The main benefit is not merely obtaining an order. It is making the dependency rules explicit, so scheduling can change without rewriting those rules into another fragile sequence of conditionals.

Python Graphlib Algorithms Concurrency