60 lines
1.7 KiB
Python
60 lines
1.7 KiB
Python
"""Tarjan's strongly connected components algorithm.
|
|
|
|
Public API:
|
|
scc(graph) -> list[list[node]]
|
|
graph: mapping node -> iterable of successors (edges u -> v).
|
|
Returns components in reverse topological order (SCC DAG topologically sorted).
|
|
Each component is a list of nodes; singletons for acyclic nodes.
|
|
"""
|
|
from __future__ import annotations
|
|
|
|
|
|
def scc(graph):
|
|
# materialise successors once
|
|
succ = {n: tuple(v for v in (graph.get(n) or ())) for n in graph}
|
|
# ensure all referenced nodes exist
|
|
nodes = set(graph.keys())
|
|
for ds in succ.values():
|
|
nodes.update(ds)
|
|
for n in nodes:
|
|
succ.setdefault(n, ())
|
|
|
|
index_counter = [0]
|
|
stack = []
|
|
on_stack = set()
|
|
indices = {}
|
|
lowlink = {}
|
|
result = []
|
|
|
|
import sys
|
|
sys.setrecursionlimit(max(sys.getrecursionlimit(), len(nodes) + 100))
|
|
|
|
def strongconnect(v):
|
|
indices[v] = index_counter[0]
|
|
lowlink[v] = index_counter[0]
|
|
index_counter[0] += 1
|
|
stack.append(v)
|
|
on_stack.add(v)
|
|
for w in succ[v]:
|
|
if w not in indices:
|
|
strongconnect(w)
|
|
lowlink[v] = min(lowlink[v], lowlink[w])
|
|
elif w in on_stack:
|
|
lowlink[v] = min(lowlink[v], indices[w])
|
|
if lowlink[v] == indices[v]:
|
|
comp = []
|
|
while True:
|
|
w = stack.pop()
|
|
on_stack.discard(w)
|
|
comp.append(w)
|
|
if w == v:
|
|
break
|
|
result.append(comp)
|
|
|
|
for v in sorted(nodes, key=lambda x: (type(x).__name__, repr(x))):
|
|
if v not in indices:
|
|
strongconnect(v)
|
|
|
|
# result is in reverse topological order already (Tarjan property)
|
|
return result
|