Skip to content
Tutorials Center
My learning

Topics

Python Reference ยท Standard Library: Data Structures and Functional Tools

The graphlib module

Reference for Python's graphlib module: TopologicalSorter, static_order(), prepare/get_ready/done for parallel work, and CycleError for circular dependencies.

The graphlib module contains one tool: TopologicalSorter. Given tasks and the tasks each one depends on, it produces an order in which every task comes after everything it needs. That is the core of build systems, package installers, spreadsheet recalculation and course-prerequisite planners.

You describe the graph as a dictionary that maps each node to the nodes it depends on (its predecessors). Nodes that only appear as dependencies are included automatically. If the dependencies form a cycle, no valid order exists and CycleError is raised.

Python
from graphlib import TopologicalSorter

order = list(TopologicalSorter({"app": {"lib"}, "lib": set()}).static_order())
# ['lib', 'app']

Try it

Python Dependency order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python Waves of parallel work and cycles

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Syntax

Python
TopologicalSorter(graph=None)
Name Description
graph Optional mapping from each node to an iterable of its predecessors (the nodes that must come first).
Method Description
add(node, *predecessors) Adds a node and the nodes it depends on. May be called repeatedly, but not after prepare().
prepare() Marks the graph as complete and checks for cycles. Raises CycleError.
get_ready() Returns a tuple of nodes whose dependencies are all finished and that were not handed out before.
done(*nodes) Tells the sorter that these nodes are finished, which unlocks their dependents.
is_active() True while more nodes are waiting or ready.
static_order() Returns an iterator over all nodes in a valid order (calls prepare() for you).

Raises: CycleError (a subclass of ValueError) for circular dependencies; its second argument is a list of nodes forming the cycle, with the first and last the same. ValueError if you call add() after prepare(), or done() for a node that was not handed out.

Usage notes

  • Direction matters. In {"app": {"lib"}}, lib comes first. If your data says "A comes before B", reverse it or use add(B, A).
  • The order is not unique. Independent nodes can appear in several valid orders. Sort them yourself when you need stable output, as the examples do.
  • Nodes must be hashable and comparable by equality.
  • Use get_ready() / done() for concurrency. Hand every ready node to a thread pool, call done() as each finishes, and ask for more. static_order() is the simple choice when you run tasks one at a time.
  • A TopologicalSorter is single-use. After iterating, build a new one for another pass.
  • Cycle detection is found early (in prepare()), before any work is done. Self-dependencies ({"a": {"a"}}) count as cycles.
  • The module is small on purpose. It does not find shortest paths or strongly connected components; write those yourself or use a graph library.
  • Added in Python 3.9.