blob: 31b51c9e5e9334a75ebf2a934ac46130665192ab [file] [log] [blame]
 # Copyright (c) 2013 Mark Dickinson # # Permission is hereby granted, free of charge, to any person obtaining a copy # of this software and associated documentation files (the "Software"), to deal # in the Software without restriction, including without limitation the rights # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell # copies of the Software, and to permit persons to whom the Software is # furnished to do so, subject to the following conditions: # # The above copyright notice and this permission notice shall be included in # all copies or substantial portions of the Software. # # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE # SOFTWARE. def StronglyConnectedComponents(vertices, edges): """Find the strongly connected components of a directed graph. Uses a non-recursive version of Gabow's linear-time algorithm [1] to find all strongly connected components of a directed graph. A "strongly connected component" of a directed graph is a maximal subgraph such that any vertex in the subgraph is reachable from any other; any directed graph can be decomposed into its strongly connected components. Written by Mark Dickinson and licensed under the MIT license [2]. [1] Harold N. Gabow, "Path-based depth-first search for strong and biconnected components," Inf. Process. Lett. 74 (2000) 107--114. [2] From code.activestate.com: http://goo.gl/X0z4C Args: vertices: A list of vertices. Each vertex should be hashable. edges: Dictionary that maps each vertex v to a set of the vertices w that are linked to v by a directed edge (v, w). Returns: A list of sets of vertices. """ identified = set() stack = [] index = {} boundaries = [] for v in vertices: if v not in index: to_do = [('VISIT', v)] while to_do: operation_type, v = to_do.pop() if operation_type == 'VISIT': index[v] = len(stack) stack.append(v) boundaries.append(index[v]) to_do.append(('POSTVISIT', v)) to_do.extend([('VISITEDGE', w) for w in edges[v]]) elif operation_type == 'VISITEDGE': if v not in index: to_do.append(('VISIT', v)) elif v not in identified: while index[v] < boundaries[-1]: boundaries.pop() else: # operation_type == 'POSTVISIT' if boundaries[-1] == index[v]: boundaries.pop() scc = set(stack[index[v]:]) del stack[index[v]:] identified.update(scc) yield scc