| 1 |
# Adapted from mypy (mypy/build.py) under the MIT license. |
| 2 |
|
| 3 |
from collections.abc import Iterable, Iterator, Set |
| 4 |
|
| 5 |
|
| 6 |
def strongly_connected_components( |
| 7 |
vertices: Set[str], edges: dict[str, Set[str]] |
| 8 |
) -> Iterator[Set[str]]: |
| 9 |
"""Compute Strongly Connected Components of a directed graph. |
| 10 |
|
| 11 |
Args: |
| 12 |
vertices: the labels for the vertices |
| 13 |
edges: for each vertex, gives the target vertices of its outgoing edges |
| 14 |
|
| 15 |
Returns: |
| 16 |
An iterator yielding strongly connected components, each |
| 17 |
represented as a set of vertices. Each input vertex will occur |
| 18 |
exactly once; vertices not part of a SCC are returned as |
| 19 |
singleton sets. |
| 20 |
|
| 21 |
From https://code.activestate.com/recipes/578507-strongly-connected-components-of-a-directed-graph/. |
| 22 |
""" |
| 23 |
identified: set[str] = set() |
| 24 |
stack: list[str] = [] |
| 25 |
index: dict[str, int] = {} |
| 26 |
boundaries: list[int] = [] |
| 27 |
|
| 28 |
def dfs(v: str) -> Iterator[set[str]]: |
| 29 |
index[v] = len(stack) |
| 30 |
stack.append(v) |
| 31 |
boundaries.append(index[v]) |
| 32 |
|
| 33 |
for w in edges[v]: |
| 34 |
if w not in index: |
| 35 |
yield from dfs(w) |
| 36 |
elif w not in identified: |
| 37 |
while index[w] < boundaries[-1]: |
| 38 |
boundaries.pop() |
| 39 |
|
| 40 |
if boundaries[-1] == index[v]: |
| 41 |
boundaries.pop() |
| 42 |
scc = set(stack[index[v] :]) |
| 43 |
del stack[index[v] :] |
| 44 |
identified.update(scc) |
| 45 |
yield scc |
| 46 |
|
| 47 |
for v in vertices: |
| 48 |
if v not in index: |
| 49 |
yield from dfs(v) |
| 50 |
|
| 51 |
|
| 52 |
def topsort( |
| 53 |
data: dict[Set[str], set[Set[str]]] |
| 54 |
) -> Iterable[Set[Set[str]]]: |
| 55 |
"""Topological sort. |
| 56 |
|
| 57 |
Args: |
| 58 |
data: A map from SCCs (represented as frozen sets of strings) to |
| 59 |
sets of SCCs, its dependencies. NOTE: This data structure |
| 60 |
is modified in place -- for normalization purposes, |
| 61 |
self-dependencies are removed and entries representing |
| 62 |
orphans are added. |
| 63 |
|
| 64 |
Returns: |
| 65 |
An iterator yielding sets of SCCs that have an equivalent |
| 66 |
ordering. NOTE: The algorithm doesn't care about the internal |
| 67 |
structure of SCCs. |
| 68 |
|
| 69 |
Example: |
| 70 |
Suppose the input has the following structure: |
| 71 |
|
| 72 |
{A: {B, C}, B: {D}, C: {D}} |
| 73 |
|
| 74 |
This is normalized to: |
| 75 |
|
| 76 |
{A: {B, C}, B: {D}, C: {D}, D: {}} |
| 77 |
|
| 78 |
The algorithm will yield the following values: |
| 79 |
|
| 80 |
{D} |
| 81 |
{B, C} |
| 82 |
{A} |
| 83 |
|
| 84 |
From https://code.activestate.com/recipes/577413-topological-sort/history/1/. |
| 85 |
""" |
| 86 |
# TODO: Use a faster algorithm? |
| 87 |
for k, v in data.items(): |
| 88 |
v.discard(k) # Ignore self dependencies. |
| 89 |
for item in set.union(*data.values()) - set(data.keys()): |
| 90 |
data[item] = set() |
| 91 |
while True: |
| 92 |
ready = {item for item, dep in data.items() if not dep} |
| 93 |
if not ready: |
| 94 |
break |
| 95 |
yield ready |
| 96 |
data = {item: (dep - ready) for item, dep in data.items() if item not in ready} |
| 97 |
assert not data, f"A cyclic dependency exists amongst {data}" |
| 98 |
|
| 99 |
|
| 100 |
def find_cycles_in_scc( |
| 101 |
graph: dict[str, Set[str]], scc: Set[str], start: str |
| 102 |
) -> Iterable[list[str]]: |
| 103 |
"""Find cycles in SCC emanating from start. |
| 104 |
|
| 105 |
Yields lists of the form ['A', 'B', 'C', 'A'], which means there's |
| 106 |
a path from A -> B -> C -> A. The first item is always the start |
| 107 |
argument, but the last item may be another element, e.g. ['A', |
| 108 |
'B', 'C', 'B'] means there's a path from A to B and there's a |
| 109 |
cycle from B to C and back. |
| 110 |
""" |
| 111 |
# Basic input checks. |
| 112 |
assert start in scc, (start, scc) |
| 113 |
assert scc <= graph.keys(), scc - graph.keys() |
| 114 |
|
| 115 |
# Reduce the graph to nodes in the SCC. |
| 116 |
graph = {src: {dst for dst in dsts if dst in scc} for src, dsts in graph.items() if src in scc} |
| 117 |
assert start in graph |
| 118 |
|
| 119 |
# Recursive helper that yields cycles. |
| 120 |
def dfs(node: str, path: list[str]) -> Iterator[list[str]]: |
| 121 |
if node in path: |
| 122 |
yield path + [node] |
| 123 |
return |
| 124 |
path = path + [node] # TODO: Make this not quadratic. |
| 125 |
for child in graph[node]: |
| 126 |
yield from dfs(child, path) |
| 127 |
|
| 128 |
yield from dfs(start, []) |