Skip to content

Topological sorting with `graphlib` [ref]

Problem

  • Order "parse" before dependent node "compile".
  • Add isolated node "test" and check that all three nodes appear.
  • Catch the cycle formed by mutual dependencies of "a" and "b".
  • Construct a sorter from a mapping of each node to its predecessors.

Python solution

from graphlib import CycleError, TopologicalSorter

graph = TopologicalSorter()
graph.add("parse")
graph.add("compile", "parse")
tuple(graph.static_order())  # ('parse', 'compile')

graph = TopologicalSorter()
graph.add("compile", "parse")
graph.add("test")
set(graph.static_order())  # {'parse', 'compile', 'test'}

graph = TopologicalSorter()
graph.add("a", "b")
graph.add("b", "a")
try:
    tuple(graph.static_order())
except CycleError:
    has_cycle = True
has_cycle  # True

mapping = {"parse": set(), "compile": {"parse"}}
tuple(TopologicalSorter(mapping).static_order())
# ('parse', 'compile')