"""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()