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