`graphlib`

The Python graphlib module provides functionality for working with graph-like structures. Its main class, TopologicalSorter, performs topological sorting of a directed acyclic graph (DAG), producing a linear order in which every node appears after all of its dependencies.

Here’s a quick example:

>>> from graphlib import TopologicalSorter

>>> graph = {"D": ["B", "C"], "C": ["A"], "B": ["A"]}
>>> sorter = TopologicalSorter(graph)
>>> tuple(sorter.static_order())
('A', 'C', 'B', 'D')

Each key in the input dictionary is a node, and its value is an iterable of predecessor nodes that must come before it in the final order.

Key Features

Performs topological sorting of directed acyclic graphs
Accepts a dependency mapping at construction time or through incremental .add() calls
Detects cycles and reports the offending nodes through CycleError
Supports both one-shot sorting through .static_order() and step-by-step processing through .get_ready() and .done()
Enables parallel scheduling by exposing the set of nodes ready to be processed at each step
Accepts any hashable value as a node

Frequently Used Classes and Functions

Object	Type	Description
`graphlib.TopologicalSorter`	Class	Represents a directed acyclic graph and performs topological sorting
`TopologicalSorter.add()`	Method	Adds a node and its predecessors to the graph
`TopologicalSorter.prepare()`	Method	Marks the graph as complete and checks for cycles
`TopologicalSorter.get_ready()`	Method	Returns a tuple of nodes that have no unresolved dependencies
`TopologicalSorter.done()`	Method	Marks nodes returned by `.get_ready()` as processed
`TopologicalSorter.is_active()`	Method	Returns whether more progress can still be made
`TopologicalSorter.static_order()`	Method	Returns an iterator over all nodes in a valid topological order
`graphlib.CycleError`	Exception	Raised by `.prepare()` when the graph contains a cycle

Examples

Building a graph incrementally with .add():

>>> from graphlib import TopologicalSorter

>>> sorter = TopologicalSorter()
>>> sorter.add("test_login", "db")
>>> sorter.add("test_checkout", "db", "test_login")
>>> sorter.add("db")
>>> list(sorter.static_order())
['db', 'test_login', 'test_checkout']

Detecting a cycle in the graph:

>>> from graphlib import TopologicalSorter, CycleError

>>> sorter = TopologicalSorter({"a": ["b"], "b": ["a"]})

>>> try:
...     sorter.prepare()
... except CycleError as error:
...     print(error.args[1])
...
['a', 'b', 'a']

Walking the graph manually to reveal one dependency level at a time:

>>> from graphlib import TopologicalSorter

>>> sorter = TopologicalSorter({"D": ["B", "C"], "C": ["A"], "B": ["A"]})
>>> sorter.prepare()

>>> while sorter.is_active():
...     ready = sorter.get_ready()
...     print(ready)
...     sorter.done(*ready)
...
('A',)
('C', 'B')
('D',)

Common Use Cases

The most common tasks for graphlib include:

Ordering build or compilation steps so that each target runs after its dependencies
Scheduling tasks in a data pipeline or workflow engine
Resolving the load order of plugins, modules, or configuration files
Validating that a set of dependencies does not contain a cycle
Dispatching independent work to threads or processes in parallel while respecting dependency constraints

Real-World Example

Consider a small build system that needs to compile several source files, where some files depend on others. The TopologicalSorter can generate a safe build order and, through .get_ready(), expose the files that can be compiled in parallel at each stage:

>>> from graphlib import TopologicalSorter

>>> dependencies = {
...     "app.o": ["main.c", "utils.o", "parser.o"],
...     "utils.o": ["utils.c", "utils.h"],
...     "parser.o": ["parser.c", "parser.h", "utils.h"],
...     "main.c": [],
...     "utils.c": [],
...     "utils.h": [],
...     "parser.c": [],
...     "parser.h": [],
... }

>>> sorter = TopologicalSorter(dependencies)
>>> sorter.prepare()
>>> stage = 1

>>> while sorter.is_active():
...     ready = sorter.get_ready()
...     print(f"Stage {stage}: {sorted(ready)}")
...     sorter.done(*ready)
...     stage += 1
...
Stage 1: ['main.c', 'parser.c', 'parser.h', 'utils.c', 'utils.h']
Stage 2: ['parser.o', 'utils.o']
Stage 3: ['app.o']

Each stage contains files whose dependencies have already been built, so the items within a stage can be processed in any order or in parallel, while the stages themselves run sequentially.

Tutorial

Build a Maze Solver in Python Using Graphs

In this step-by-step project, you'll build a maze solver in Python using graph algorithms from the NetworkX library. Along the way, you'll design a binary file format for the maze, represent it in an object-oriented way, and visualize the solution using scalable vector graphics (SVG).

intermediate projects

For additional information on related topics, take a look at the following resources: