blob: f563fd03f3f8814b7abe9c3990729bef449b77f1 [file]
# Copyright 2026 The Fuchsia Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
"""Graph algorithms and utilities."""
from collections.abc import KeysView
from typing import Any
class Graph:
"""A simple directed graph implementation."""
def __init__(self) -> None:
# Maps each vertex to its successors. Vertices are kept in insertion
# order, so that traversals, and the numbering of the SCCs they
# produce, are the same from one run to the next.
self.graph: dict[Any, list[Any]] = {}
@property
def vertices(self) -> KeysView[Any]:
"""The vertices of the graph, in insertion order."""
return self.graph.keys()
def add_vertex(self, u: Any) -> None:
"""Adds a vertex to the graph."""
self.graph.setdefault(u, [])
def add_edge(self, u: Any, v: Any) -> None:
"""Adds a directed edge from u to v."""
self.add_vertex(u)
self.add_vertex(v)
self.graph[u].append(v)
def get_sccs(self) -> list[list[Any]]:
"""
Finds Strongly Connected Components using Tarjan's algorithm.
The depth-first search is iterative, so that call chains deeper than
Python's recursion limit are handled.
"""
index_counter = 0
stack: list[Any] = []
on_stack: set[Any] = set()
lowlink: dict[Any, int] = {}
index: dict[Any, int] = {}
result: list[list[Any]] = []
for root in self.vertices:
if root in index:
continue
# Each work item is a node and an iterator over its successors,
# which records how far the node's successors have been visited.
work = [(root, iter(self.graph[root]))]
index[root] = lowlink[root] = index_counter
index_counter += 1
stack.append(root)
on_stack.add(root)
while work:
node, successors = work[-1]
descended = False
for successor in successors:
if successor not in index:
index[successor] = lowlink[successor] = index_counter
index_counter += 1
stack.append(successor)
on_stack.add(successor)
work.append((successor, iter(self.graph[successor])))
descended = True
break
if successor in on_stack:
lowlink[node] = min(lowlink[node], index[successor])
if descended:
continue
# All successors of node have been visited.
work.pop()
if work:
parent = work[-1][0]
lowlink[parent] = min(lowlink[parent], lowlink[node])
if lowlink[node] == index[node]:
# SCC found. The current node is the root of the SCC.
# Nodes belonging to this SCC are currently on the stack.
connected_component = []
while True:
member = stack.pop()
on_stack.discard(member)
connected_component.append(member)
if member == node:
break
result.append(connected_component)
return result
def topological_sort(self) -> list[Any]:
"""
Returns vertices in topological order (u before v if u->v).
Note: This is only valid for DAGs. For cyclic graphs, this returns
*some* order compatible with the condensation DAG if used on SCCs,
but here it's run directly on the SCC DAG.
So this function just needs to support DAGs.
"""
visited = set()
stack = []
for root in self.vertices:
if root in visited:
continue
visited.add(root)
work = [(root, iter(self.graph[root]))]
while work:
node, neighbors = work[-1]
for neighbor in neighbors:
if neighbor not in visited:
visited.add(neighbor)
work.append((neighbor, iter(self.graph[neighbor])))
break
else:
work.pop()
stack.append(node)
# Stack has reverse topological order (children first).
# We want u before v (parents first).
return stack[::-1]