1# Adapted from mypy (mypy/build.py) under the MIT license. 2 3from typing import * 4 5 6def strongly_connected_components( 7 vertices: AbstractSet[str], edges: Dict[str, AbstractSet[str]] 8) -> Iterator[AbstractSet[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 http://code.activestate.com/recipes/578507/. 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 52def topsort( 53 data: Dict[AbstractSet[str], Set[AbstractSet[str]]] 54) -> Iterable[AbstractSet[AbstractSet[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 http://code.activestate.com/recipes/577413/. 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, "A cyclic dependency exists amongst %r" % data 98 99 100def find_cycles_in_scc( 101 graph: Dict[str, AbstractSet[str]], scc: AbstractSet[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, []) 129