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.
from graphlib import TopologicalSorter order = list(TopologicalSorter({"app": {"lib"}, "lib": set()}).static_order()) # ['lib', 'app']
Try it
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.
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
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"}},libcomes first. If your data says "A comes before B", reverse it or useadd(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, calldone()as each finishes, and ask for more.static_order()is the simple choice when you run tasks one at a time. - A
TopologicalSorteris 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.
Related
dict,set,concurrent.futures,collections- Lessons: Dictionaries, Algorithms