StrongConnectivity.py

"""StrongConnectivity.py

DFS-based algorithm for computing strongly connected components.

If G is a graph, then
- StronglyConnectedComponents(G) returns a list of
  its components, each represented as a subgraph of G
- Condensation(G) returns a directed acyclic graph, the
  vertices of which are strongly connected components of G.
  Each vertex of the condensation is represented as a frozenset
  of the vertices of G within a single strongly connected component.

D. Eppstein, July 2005.
"""

import unittest
import DFS

class StronglyConnectedComponents(DFS.Searcher):
    """
    Generate the strongly connected components of G.  G should be
    represented in such a way that "for v in G" loops through the
    vertices, and "G[v]" produces a list of the neighbors of v;
    for instance, G may be a dictionary mapping each vertex to its
    neighbor set.  The result of StronglyConnectedComponents(G) is
    a sequence of subgraphs of G.
    """

    def __init__(self,G):
        """Search for strongly connected components of graph G."""

        # set up data structures for DFS
        self._components = []
        self._dfsnumber = {}
        self._activelen = {}
        self._active = []
        self._low = {}
        self._biglow = len(G)
        self._graph = G

        # perform the Depth First Search
        DFS.Searcher.__init__(self,G)

        # clean up now-useless data structures
        del self._dfsnumber, self._activelen, self._active, self._low

    def __iter__(self):
        """Return iterator for sequence of strongly connected components."""
        return iter(self._components)

    def __len__(self):
        """How many components are there?"""
        return len(self._components)

    def _component(self,vertices):
        """Make a new SCC."""
        vertices = set(vertices)
        induced = {v:{w for w in self._graph[v] if w in vertices} for v in vertices}
        self._components.append(induced)

    def preorder(self,parent,child):
        """Handle first visit to vertex in DFS search for components."""
        if parent == child:
            self._active = []
        self._activelen[child] = len(self._active)
        self._active.append(child)
        self._low[child] = self._dfsnumber[child] = len(self._dfsnumber)

    def backedge(self,source,destination):
        """Handle non-tree edge in DFS search for components."""
        self._low[source] = min(self._low[source],self._low[destination])

    def postorder(self,parent,child):
        """Handle last visit to vertex in DFS search for components."""
        if self._low[child] == self._dfsnumber[child]:
            self._component(self._active[self._activelen[child]:])
            for v in self._components[-1]:
                self._low[v] = self._biglow
            del self._active[self._activelen[child]:]
        else:
            self._low[parent] = min(self._low[parent],self._low[child])

def Condensation(G):
    """Return a DAG with vertices equal to sets of vertices in SCCs of G."""
    components = {}
    GtoC = {}
    for C in StronglyConnectedComponents(G):
        C = frozenset(C)
        for v in C:
            GtoC[v] = C
        components[C] = set()
    for v in G:
        for w in G[v]:
            if GtoC[v] != GtoC[w]:
                components[GtoC[v]].add(GtoC[w])
    return components
    
# If run as "python StrongConnectivity.py", run tests on various small graphs
# and check that the correct results are obtained.

class StrongConnectivityTest(unittest.TestCase):

    G1 = { 0:[1], 1:[2,3], 2:[4,5], 3:[4,5], 4:[6], 5:[], 6:[] }
    C1 = [[0],[1],[2],[3],[4],[5],[6]]

    # Work around http://bugs.python.org/issue11796 by using a loop
    # instead of a dict/set comprehension in a class variable initializer
    # should be:
    # Con1 = {frozenset([v]):{frozenset([w]) for w in G1[v]} for v in G1}
    Con1 = {}
    for v in G1:
        Con1[frozenset([v])] = {frozenset([w]) for w in G1[v]}
    
    G2 = { 0:[1], 1:[2,3,4], 2:[0,3], 3:[4], 4:[3] }
    C2 = [[0,1,2],[3,4]]
    f012 = frozenset([0,1,2])
    f34 = frozenset([3,4])
    Con2 = {f012:{f34}, f34:set()}
    
    knownpairs = [(G1,C1),(G2,C2)]

    def testStronglyConnectedComponents(self):
        """Check known graph/component pairs."""
        for (graph,expectedoutput) in self.knownpairs:
            output = [list(C) for C in StronglyConnectedComponents(graph)]
            for component in output:
                component.sort()
            output.sort()
            self.assertEqual(output,expectedoutput)

    def testSubgraph(self):
        """Check that each SCC is an induced subgraph."""
        for (graph,expectedoutput) in self.knownpairs:
            components = StronglyConnectedComponents(graph)
            for C in components:
                for v in C:
                    for w in graph:
                        self.assertEqual(w in graph[v] and w in C, w in C[v])

    def testCondensation(self):
        """Check that the condensations are what we expect."""
        self.assertEqual(Condensation(self.G1),self.Con1)
        self.assertEqual(Condensation(self.G2),self.Con2)

if __name__ == "__main__":
    unittest.main()