"""Chordal.py Recognize and compute elimination ordering of chordal graphs, using an algorithm from Habib, McConnell, Paul, and Viennot, "Lex-BFS and Partition Refinement, with Applications to Transitive Orientation, Interval Graph Recognition, and Consecutive Ones Testing", Theor. Comput. Sci. 234:59-84 (2000), http://www.cs.colostate.edu/~rmm/lexbfs.ps D. Eppstein, November 2003. """ import unittest from LexBFS import LexBFS from Graphs import isUndirected def PerfectEliminationOrdering(G): """Return a perfect elimination ordering, or raise an exception if not chordal. 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. Running time is O(n+m) and additional space usage over G is O(n+m). """ alreadyProcessed = set() B = list(LexBFS(G)) position = {B[i]:i for i in range(len(B))} leftNeighbors = {} parent = {} for v in B: leftNeighbors[v] = set(G[v]) & alreadyProcessed alreadyProcessed.add(v) if leftNeighbors[v]: parent[v] = B[max([position[w] for w in leftNeighbors[v]])] if not leftNeighbors[v] - {parent[v]} <= leftNeighbors[parent[v]]: raise ValueError("Input to PerfectEliminationOrdering is not chordal") B.reverse() return B def Chordal(G): """Test if a given graph is chordal.""" if not isUndirected(G): raise ValueError("Input to Chordal is not an undirected graph") try: PerfectEliminationOrdering(G) except: return False return True class ChordalTest(unittest.TestCase): claw = {0:[1,2,3],1:[0],2:[0],3:[0]} butterfly = {0:[1,2,3,4],1:[0,2],2:[0,1],3:[0,4],4:[0,3]} diamond = {0:[1,2],1:[0,2,3],2:[0,1,3],3:[1,2]} quad = {0:[1,3],1:[0,2],2:[1,3],3:[0,2]} graphs = [(claw,True), (butterfly,True), (diamond,True), (quad,False)] def testChordal(self): """Check that Chordal() returns the correct answer on each test graph.""" for G,isChordal in ChordalTest.graphs: self.assertEqual(Chordal(G), isChordal) def testElimination(self): """Check that PerfectEliminationOrdering generates an elimination ordering.""" for G,isChordal in ChordalTest.graphs: if isChordal: eliminated = set() for v in PerfectEliminationOrdering(G): eliminated.add(v) for w in G[v]: for x in G[v]: if w != x and w not in eliminated and x not in eliminated: self.assertTrue(w in G[x] and x in G[w]) if __name__ == "__main__": unittest.main()