src/third_party/chromite/third_party/digraph.py

   1 # Copyright (c) 2013 Mark Dickinson
   2 #
   3 # Permission is hereby granted, free of charge, to any person obtaining a copy
   4 # of this software and associated documentation files (the "Software"), to deal
   5 # in the Software without restriction, including without limitation the rights
   6 # to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   7 # copies of the Software, and to permit persons to whom the Software is
   8 # furnished to do so, subject to the following conditions:
   9 #
  10 # The above copyright notice and this permission notice shall be included in
  11 # all copies or substantial portions of the Software.
  12 #
  13 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16 # AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17 # LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  18 # OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  19 # SOFTWARE.
  20
  21 def StronglyConnectedComponents(vertices, edges):
  22   """Find the strongly connected components of a directed graph.
  23
  24   Uses a non-recursive version of Gabow's linear-time algorithm [1] to find
  25   all strongly connected components of a directed graph.
  26
  27   A "strongly connected component" of a directed graph is a maximal subgraph
  28   such that any vertex in the subgraph is reachable from any other; any
  29   directed graph can be decomposed into its strongly connected components.
  30
  31   Written by Mark Dickinson and licensed under the MIT license [2].
  32
  33   [1] Harold N. Gabow, "Path-based depth-first search for strong and
  34       biconnected components," Inf. Process. Lett. 74 (2000) 107--114.
  35   [2] From code.activestate.com: http://goo.gl/X0z4C
  36
  37   Args:
  38     vertices: A list of vertices. Each vertex should be hashable.
  39     edges: Dictionary that maps each vertex v to a set of the vertices w
  40            that are linked to v by a directed edge (v, w).
  41
  42   Returns:
  43     A list of sets of vertices.
  44   """
  45   identified = set()
  46   stack = []
  47   index = {}
  48   boundaries = []
  49
  50   for v in vertices:
  51     if v not in index:
  52       to_do = [('VISIT', v)]
  53       while to_do:
  54         operation_type, v = to_do.pop()
  55         if operation_type == 'VISIT':
  56           index[v] = len(stack)
  57           stack.append(v)
  58           boundaries.append(index[v])
  59           to_do.append(('POSTVISIT', v))
  60           to_do.extend([('VISITEDGE', w) for w in edges[v]])
  61         elif operation_type == 'VISITEDGE':
  62           if v not in index:
  63             to_do.append(('VISIT', v))
  64           elif v not in identified:
  65             while index[v] < boundaries[-1]:
  66               boundaries.pop()
  67         else:
  68           # operation_type == 'POSTVISIT'
  69           if boundaries[-1] == index[v]:
  70             boundaries.pop()
  71             scc = set(stack[index[v]:])
  72             del stack[index[v]:]
  73             identified.update(scc)
  74             yield scc