Debian Codegraph @

Tools/peg_generator/pegen/sccutils.py

raw
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, [])