third_party/digraph.py

# 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