1  # Adapted from mypy (mypy/build.py) under the MIT license.
       2  
       3  from typing import *
       4  
       5  
       6  def 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  
      52  def 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  
     100  def 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, [])