"""Halin.py
Reduction-based algorithm for recognizing Halin and D3-reducible graphs
D. Eppstein, January 2015.
"""
import unittest
from Graphs import copyGraph, isUndirected
# ============================================================
# Main reduction algorithm for D3 reducible graphs
# ============================================================
def isK4(G):
"""Is this graph K4?"""
if len(G) != 4:
return False
for v in G:
if v in G[v] or len(set(G[v])) != 3:
return False
return True
def D3reducible(G,triangleHooks=[],pathHooks=[],finalize=isK4):
"""Test if the graph G is D3-reducible.
Whenever a reduction is found, the hook functions are
called in turn on it, and should return True if the reduction
should be allowed to continue or False otherwise.
The arguments to a triangle hook are the graph, the three
triangle vertices, their three neighbors, and the id that
will be given to the new vertex formed by the collapsed
triangle. The arguments to a path hook are the graph, the
three path vertices and the apex.
The finalize hook takes as input the irreducible graph
after all reductions are complete, and produces as output
the return value for the overall computation.
By default the return value is a Boolean that is true
whenever the irreducible graph is K4."""
if not isUndirected(G):
raise TypeError("Argument to D3reducible must be an undirected graph")
G = copyGraph(G) # We are going to change G, so make a copy of it
C = {v for v in G if len(G[v]) == 3} # Active vertices, init. all w/deg=3
def otherNeighbor(u,v,w):
"""Other neighbor of v given known neighbors u,w"""
return [x for x in G[v] if x != u and x != w][0]
def triangle(u,v,w):
"""Try a D3a reduction."""
# u, v, and w are known to form a triangle but we still need to
# check whether they have distinct neighbors."""
Nu = otherNeighbor(v,u,w)
Nv = otherNeighbor(u,v,w)
Nw = otherNeighbor(u,w,v)
if Nu == Nv or Nv == Nw or Nu == Nw:
return # Need to have three distinct neighbors
x = object() # Cons up an id for the triangle
# Run the hooks
for hook in triangleHooks:
if not hook(G,u,v,w,Nu,Nv,Nw,x):
return False
# Make the change!
del G[u],G[v],G[w]
G[Nu].remove(u)
G[Nv].remove(v)
G[Nw].remove(w)
G[x] = {Nu,Nv,Nw}
G[Nu].add(x)
G[Nv].add(x)
G[Nw].add(x)
# Update the active vertices
C.update(z for z in (x,Nu,Nv,Nw) if len(G[z]) == 3)
def path(u,v,w):
"""Try a D3b reduction."""
# u, v, and w are known to induce a path but we still need to
# check whether they have a common neighbor as apex."""
apexes = G[u] & G[v] & G[w]
if len(apexes) != 1:
return
apex = apexes.pop()
# Run the hooks
for hook in pathHooks:
if not hook(G,u,v,w,apex):
return False
# Make the change!
del G[v]
G[u].remove(v)
G[w].remove(v)
G[apex].remove(v)
G[u].add(w)
G[w].add(u)
# Update the active vertices
if len(G[apex]) == 3:
C.add(apex)
pass
def reduce(u,v,w):
"""Try a reduction in which v is the middle vertex"""
for x in (u,v,w):
if x not in G or len(G[x]) != 3:
return # No longer in G or not all degree 3, no redux
if w in G[u]:
triangle(u,v,w)
else:
path(u,v,w)
while C:
v = C.pop()
if v in G and len(G[v]) == 3:
p,q,r = tuple(G[v]) # Decode set of neighbors
reduce(p,v,q)
reduce(p,v,r)
reduce(q,v,r)
# Now check whether we found K4
return finalize(G)
def reconstructD3(G,initialize,triangle,path,recognizer=D3reducible):
"""Recursively reconstruct a D3-reducible graph G
by inverting the reductions used to recognize it.
The other four arguments are functions:
- recognize is a routine for performing D3 reductions
on a graph with triangle hooks, path hooks, and a finalizer
(like D3reducible or isHalin).
- initialize is called first, as the finalizer from
the recognition algorithm. Therefore, its signature
should match what the recognizer is expecting.
If any state passed in by the recognition phase is
needed for later calls, it should be saved here,
because it won't be passed in later. If the graph
is not recognized, this should throw an exception.
- triangle and path take the same eight and five arguments
(respectively) as the triangle and path hooks from the
reductions, but are called in the opposite order to
the order they are called in the reductions."""
calls = []
def thook(*args):
calls.append((triangle,args))
return True
def phook(*args):
calls.append((path,args))
return True
recognizer(G,[thook],[phook],initialize)
calls.reverse()
for fun,args in calls:
fun(*args)
# ============================================================
# Additional reduction rules for Halin graphs
# ============================================================
def isOuterK4(G,outer):
"""Have we reduced to a K4 with a non-outer vertex?"""
if not isK4(G):
return False
for v in G:
if v not in outer:
return True
return False
def isHalin(G,triangleHooks=[],pathHooks=[],finalize=isOuterK4):
"""Test if the graph G is Halin.
The two hook arguments are the same as for D3reducible,
but the finalize argument takes two parameters:
the final graph (as for D3reducible) and a set of
vertices that have been marked as outer."""
outer = set() # Vertices that must be on the outer face
def triangle(G,u,v,w,Nu,Nv,Nw,x):
"""Check and recolor vertices for triangle reduction"""
if u in outer and v in outer and w in outer:
return False # Can't collapse when all three are outer
outer.update(q for p,q in ((u,Nu),(v,Nv),(w,Nw)) if p in outer)
# Mark neighbors of outer as outer
outer.add(x) # As well as the new supervertex
return True
def path(G,u,v,w,x):
"""Check and recolor vertices for path reduction"""
if x in outer:
return False # Can't shorten path with outer apex
if len(G) == 5:
outer.update(v for v in G if v != x)
else:
outer.update((u,w)) # Mark remaining path vertices as outer
return True
def final(H):
"""Have we reduced to a K4 with only one outer face?"""
return finalize(H,outer)
return D3reducible(G,[triangle]+triangleHooks,
[path]+pathHooks,final)
def HalinLeafVertices(G):
"""Reconstruct the leaf cycle of Halin graph G.
The cycle is returned as a set of its vertices."""
outer = set()
def initialize(H,marked):
"""Augment outer to include all outer vertices"""
if not isOuterK4(H,marked):
raise TypeError("Argument to HalinLeafVertices must be Halin")
for v in H:
if v not in marked:
outer.update(w for w in H if v != w) # outerize all but v
break
def triangle(G,u,v,w,Nu,Nv,Nw,x):
"""Undo a D3a reduction"""
nout = 0
for (p,q) in ((u,Nu),(v,Nv),(w,Nw)):
if q in outer:
outer.add(p)
nout += 1
assert nout == 2
def path(G,u,v,w,x):
"""Undo a D3b reduction"""
assert x not in outer
outer.update((u,v,w))
reconstructD3(G,initialize,triangle,path,isHalin)
return outer & set(iter(G)) # Find all marked vertices
# ============================================================
# Hamiltonian cycle
# ============================================================
def D3HamiltonianCycle(G):
ham = {} # Where to put the Hamiltonian cycle
def initialize(H):
"""Start a Hamiltonian cycle on a K4"""
if not isK4(H):
raise TypeError("Argument to D3HamiltonianCycle not D3 reducible")
C = list(H)
for i in range(4):
ham[C[i-1]] = {C[i-2],C[i]}
def triangle(G,u,v,w,Nu,Nv,Nw,x):
"""Undo D3a reduction on Hamiltonian cycle"""
# Permute so the missing edge in the Hamiltonian cycle is Nw-x
if Nu not in ham[x]:
u,Nu,w,Nw = w,Nw,u,Nu
elif Nv not in ham[x]:
v,Nv,w,Nw = w,Nw,v,Nv
assert w not in ham[x]
# Out with the old, in with the new
del ham[x]
ham[Nu].remove(x)
ham[Nu].add(u)
ham[Nv].remove(x)
ham[Nv].add(v)
ham[u] = {Nu,w}
ham[w] = {u,v}
ham[v] = {w,Nv}
def path(G,u,v,w,x):
"""Undo D3b reduction on Hamiltonian cycle"""
if w not in ham[u]: w = x # Permute so w is a ham-neighbor of u
ham[u].remove(w)
ham[u].add(v)
ham[w].remove(u)
ham[w].add(v)
ham[v] = {u,w}
reconstructD3(G,initialize,triangle,path)
return ham
# ============================================================
# Additional reduction rules for other graph classes
# ============================================================
def isDual3Tree(G,triangleHooks=[],pathHooks=[],finalize=isK4):
"""Test if the graph G is the dual of a 3-tree."""
def noPath(G,u,v,w,x): return False
return D3reducible(G,triangleHooks,[noPath],finalize)
def isWheel(G,triangleHooks=[],pathHooks=[],finalize=isK4):
"""Test if the graph G is a wheel."""
def noTriangle(G,u,v,w,Nu,Nv,Nw,x): return False
return D3reducible(G,[noTriangle],pathHooks,finalize)
# ============================================================
# If run from command line, perform unit tests
# ============================================================
class HalinTest(unittest.TestCase):
cube = {i:[i^1,i^2,i^4] for i in range(8)}
trunctet = {(i,j):[(i,k) for k in range(4) if k!=i and k!=j]+[(j,i)]
for i in range(4) for j in range(4) if i!=j}
wheel = {0:[1,2,3,4,5],1:[0,2,5],2:[0,1,3],3:[0,2,4],4:[0,3,5],5:[0,1,4]}
halin8 = {0:[1,7,5],1:[0,2,7],2:[1,3,6],3:[2,4,6],
4:[3,5,6],5:[0,4,6],6:[2,3,4,5,7],7:[0,1,6]}
nonhalin = {0:[1,2,4],1:[0,3,5,7],2:[0,3,4,6],3:[1,2,7],
4:[0,2,6],5:[1,6,7],6:[2,4,5],7:[1,3,5]}
ternary = {0:(1,2,3),13:(4,14,39),39:(12,13,38)}
for i in range(1,13):
ternary[i] = ((i-1)//3,3*i+1,3*i+2,3*i+3)
for i in range(14,39):
ternary[i] = ((i-1)//3,i-1,i+1)
def testD3Reducible(self):
"""Check correct classification of D3-reducible graphs"""
self.assertEqual(D3reducible(self.cube), False)
self.assertEqual(D3reducible(self.trunctet), True)
self.assertEqual(D3reducible(self.wheel), True)
self.assertEqual(D3reducible(self.nonhalin), True)
self.assertEqual(D3reducible(self.ternary), True)
def testReductionTypes(self):
"""Check that the correct reduction types are being applied"""
self.assertEqual(isWheel(self.trunctet),False)
self.assertEqual(isWheel(self.wheel),True)
self.assertEqual(isWheel(self.ternary),False)
self.assertEqual(isWheel(self.nonhalin), False)
self.assertEqual(isDual3Tree(self.trunctet),True)
self.assertEqual(isDual3Tree(self.wheel),False)
self.assertEqual(isDual3Tree(self.ternary),False)
self.assertEqual(isDual3Tree(self.nonhalin), False)
def testHalin(self):
"""Check correct classification of Halin graphs"""
self.assertEqual(isHalin(self.cube), False)
self.assertEqual(isHalin(self.trunctet), False)
self.assertEqual(isHalin(self.wheel), True)
self.assertEqual(isHalin(self.halin8), True)
self.assertEqual(isHalin(self.nonhalin), False)
self.assertEqual(isHalin(self.ternary), True)
self.assertEqual(HalinLeafVertices(self.wheel),{1,2,3,4,5})
self.assertEqual(HalinLeafVertices(self.halin8),{0,1,2,3,4,5})
self.assertEqual(HalinLeafVertices(self.ternary),set(range(13,40)))
def testHamiltonian(self):
"""Check correct construction of Hamiltonian cycle"""
for G in (self.trunctet,self.wheel,self.nonhalin,self.ternary):
H = D3HamiltonianCycle(G)
self.assertEqual(set(H),set(G)) # same vertices?
for v in H:
self.assertEqual(len(H[v]),2) # degree-two?
for w in H[v]:
self.assertEqual(w in G[v], True) # subgraph?
if __name__ == "__main__":
unittest.main()