Python Graphlib Module
The graphlib module, introduced in Python 3.9, provides functionality to perform topological sorting of a graph of hashable nodes.
Importing the Module
import graphlibTopological Sorting
A topological sort of a directed graph is a linear ordering of its vertices such that for every directed edge u -> v from vertex u to vertex v, u comes before v in the ordering.
TopologicalSorter
The TopologicalSorter class allows you to perform topological sorting. You can initialize it with a dictionary where keys are nodes and values are iterables of their predecessors (dependencies).
import graphlib
# Create a graph: key depends on values (predecessors)
graph = {
"D": {"B", "C"},
"C": {"A"},
"B": {"A"}
}
ts = graphlib.TopologicalSorter(graph)static_order()
Returns an iterable of nodes in a topological order.
print(list(ts.static_order()))
# Output: ['A', 'C', 'B', 'D'] (Order of C and B may vary)Step-by-Step Execution
For more control (e.g., parallel processing), you can use prepare(), get_ready(), and done().
ts = graphlib.TopologicalSorter(graph)
ts.prepare()
while ts.is_active():
ready_nodes = ts.get_ready()
print(f"Ready: {ready_nodes}")
# Process nodes...
for node in ready_nodes:
ts.done(node)Handling Cycles
If the graph contains a cycle, static_order() raises a CycleError.