"""Biconnectivity.py DFS-based algorithm for computing biconnected components. D. Eppstein, April 2004. """ import unittest from Graphs import isUndirected from Util import arbitrary_item from PartialOrder import TopologicalOrder import DFS disconnected = object() # flag for BiconnectedComponents class BiconnectedComponents(DFS.Searcher): """ Generate the biconnected 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 BiconnectedComponents(G) is a sequence of subgraphs of G. """ def __init__(self,G): """Search for biconnected components of graph G.""" if not isUndirected(G): raise ValueError("BiconnectedComponents: input not undirected graph") # set up data structures for DFS self._components = [] self._dfsnumber = {} self._activelen = {} self._active = [] self._low = {} self._ancestors = {} # directed subgraph from nodes to DFS ancestors # perform the Depth First Search DFS.Searcher.__init__(self,G) # clean up now-useless data structures del self._dfsnumber, self._activelen, self._active del self._low, self._ancestors def __iter__(self): """Return iterator for sequence of biconnected components.""" return iter(self._components) def preorder(self,parent,child): if parent == child: self._active = [child] else: self._active.append(child) self._low[child] = self._dfsnumber[child] = len(self._dfsnumber) self._ancestors[child] = set() self._activelen[child] = len(self._active) def backedge(self,source,destination): if self._dfsnumber[destination] < self._dfsnumber[source]: self._low[source] = min(self._low[source], self._dfsnumber[destination]) self._ancestors[source].add(destination) def postorder(self,parent,child): if self._low[child] != self._dfsnumber[parent]: self._low[parent] = min(self._low[parent],self._low[child]) self._activelen[parent] = len(self._active) elif parent != child: self._component(self._activelen[parent],parent) elif not self._components or child not in self._components[-1]: self._component() def _component(self,start=0, articulation_point=disconnected): """Make new component, removing active vertices from start onward.""" component = {} if articulation_point is not disconnected: component[articulation_point] = set() for v in self._active[start:]: component[v] = set() for w in self._ancestors[v]: component[v].add(w) component[w].add(v) del self._active[start:] self._components.append(component) class NotBiconnected(Exception): pass class BiconnectivityTester(DFS.Searcher): """ Stripped down version of BiconnectedComponents. Either successfully inits or raises NotBiconnected. Otherwise does nothing. """ def __init__(self,G): """Search for biconnected components of graph G.""" if not isUndirected(G): raise NotBiconnected self._dfsnumber = {} self._low = {} self._rootedge = None DFS.Searcher.__init__(self,G) def preorder(self,parent,child): if parent == child and self._rootedge: raise NotBiconnected # two roots, not even connected elif not self._rootedge and parent != child: self._rootedge = (parent,child) self._low[child] = self._dfsnumber[child] = len(self._dfsnumber) def backedge(self,source,destination): self._low[source] = min(self._low[source],self._dfsnumber[destination]) def postorder(self,parent,child): if self._low[child] != self._dfsnumber[parent]: self._low[parent] = min(self._low[parent],self._low[child]) elif (parent,child) == self._rootedge: pass # end of first component, >1 vertices elif parent != child: raise NotBiconnected # articulation point elif not self._rootedge: self._rootedge = parent,child # end of first component, isolani def isBiconnected(G): """Return True if graph G is biconnected, False otherwise.""" try: BiconnectivityTester(G) return True except NotBiconnected: return False class stOrienter(DFS.Searcher): """ Subclass for st-orienting a biconnected graph. """ def __init__(self,G): """Relate edges for st-orientation.""" if not isUndirected(G): raise ValueError("stOrienter: input not undirected graph") # set up data structures for DFS self._dfsnumber = {} self._low = {} self._down = {} # down[v] = child we're currently exploring from v self._lowv = {} # lowv[n] = vertex with low number n # The main data structure! # a dictionary mapping edges to lists of edges # each of which should be oriented the same as the key. self.orient = {} self.roots = [] # edges with no predecessor # perform the Depth First Search DFS.Searcher.__init__(self,G) # clean up now-useless data structures del self._dfsnumber, self._low, self._down, self._lowv def __iter__(self): """Return iterator for sequence of biconnected components.""" return iter(self._components) def preorder(self,parent,child): self._low[child] = self._dfsnumber[child] = len(self._dfsnumber) self._lowv[self._low[child]] = self._down[parent] = child def backedge(self,source,destination): if self._dfsnumber[destination] < self._dfsnumber[source]: self._low[source] = min(self._low[source], self._dfsnumber[destination]) if source != self._down[destination]: self.addOrientation(destination,source,destination) def postorder(self,parent,child): if self._low[child] != self._dfsnumber[parent]: self._low[parent] = min(self._low[parent],self._low[child]) self.addOrientation(child,parent,self._lowv[self._low[child]]) elif parent != child: self.roots.append((parent,child)) def addOrientation(self,source,dest,anchor): """Store orientation info for source->dest edge. It should be oriented the same as the edge from the anchor to the current child of the anchor.""" child = self._down[anchor] L = self.orient.setdefault((anchor,child),[]) L.append((source,dest)) def stOrientation(G): """Find an acyclic orientation of G, with one source and one sink.""" stO = stOrienter(G) if len(stO.roots) != 1: raise NotBiconnected source,dest = stO.roots[0] G = {v:set() for v in G} orientable = [] while True: G[source].add(dest) for u,v in stO.orient.get((source,dest),[]): orientable.append((u,v)) for v,u in stO.orient.get((dest,source),[]): orientable.append((u,v)) if not orientable: break source,dest = orientable.pop() return G # If run as "python Biconnectivity.py", run tests on various small graphs # and check that the correct results are obtained. class BiconnectivityTest(unittest.TestCase): G1 = { 0: [1,2,5], 1: [0,5], 2: [0,3,4], 3: [2,4,5,6], 4: [2,3,5,6], 5: [0,1,3,4], 6: [3,4], } G2 = { 0: [2,5], 1: [3,8], 2: [0,3,5], 3: [1,2,6,8], 4: [7], 5: [0,2], 6: [3,8], 7: [4], 8: [1,3,6], } def testIsBiconnected(self): """G1 is biconnected but G2 is not.""" self.assertEqual(isBiconnected(self.G1), True) self.assertEqual(isBiconnected(self.G2), False) def testBiconnectedComponents(self): """G2 has four biconnected components.""" C = BiconnectedComponents(self.G2) CV = sorted(sorted(component.keys()) for component in C) self.assertEqual(CV,[[0,2,5],[1,3,6,8],[2,3],[4,7]]) def testSTOrientation(self): STO = stOrientation(self.G1) L = list(TopologicalOrder(STO)) indegree = dict([(v,0) for v in self.G1]) for v in L: for w in STO[v]: indegree[w] += 1 outdegree = dict([(v,len(STO[v])) for v in self.G1]) self.assertEqual(len([v for v in self.G1 if indegree[v] == 0]), 1) self.assertEqual(len([v for v in self.G1 if outdegree[v] == 0]), 1) if __name__ == "__main__": unittest.main()