"""CubicHam.py
Generate all Hamiltonian cycles in graphs of maximum degree three.
D. Eppstein, April 2004.
"""
import unittest
from Graphs import *
from Biconnectivity import isBiconnected
from CardinalityMatching import matching
from Util import arbitrary_item, map_to_constant
def HamiltonianCycles(G):
"""
Generate a sequence of all Hamiltonian cycles in graph G.
G should be represented in such a way that "for v in G" loops through
the vertices, and "G[v]" produces a collection of neighbors of v; for
instance, G may be a dictionary mapping vertices to lists of neighbors.
Each cycle is returned as a graph in a similar representation, and
should not be modified by the caller. Running time is O(2^{3n/8}) as
analyzed in my paper, The Traveling Salesman Problem for Cubic Graphs.
"""
# Check input and copy it so we can modify the copy.
# In the copied graph G, G[v][w] is True when vw is an original edge
# of the input, and False when it was produced by a contraction.
if not G or not isUndirected(G) or maxDegree(G) > 3:
raise ValueError("HamiltonianCycles input must be undirected degree three graph")
if minDegree(G) < 2:
return
G = copyGraph(G,map_to_constant(True))
# Subgraph of forced edges in the input
forced_in_input = {v:{} for v in G}
# Subgraph of forced edges in current G
forced_in_current = {v:{} for v in G}
# List of vertices with degree two
degree_two = [v for v in G if len(G[v]) == 2]
# Collection of vertices with forced edges
forced_vertices = {}
# Reuse results of call to matching() to speed up subsequent calls
previous_matching = {}
# The overall backtracking algorithm is implemented by means of
# a stack of actions. At each step we pop the most recent action
# off the stack and call it. Each stacked function should return None or False
# normally, or True to signal that we have found a Hamiltonian cycle.
# Whenever we modify the graph, we push an action undoing that modification.
# Below are definitions of actions and action-related functions.
def remove(v,w):
"""Remove edge v,w from edges of G."""
was_original = G[v][w]
del G[v][w],G[w][v]
was_forced = w in forced_in_current[v]
if was_forced:
del forced_in_current[v][w],forced_in_current[w][v]
def unremove():
G[v][w] = G[w][v] = was_original
if was_forced:
forced_in_current[v][w] = forced_in_current[w][v] = True
actions.append(unremove)
def now_degree_two(v):
"""Discover that changing G has caused v's degree to become two."""
degree_two.append(v)
def not_degree_two():
top = degree_two.pop()
assert v == top
actions.append(not_degree_two)
def safely_remove(v,w):
"""
Remove edge v,w and update degree two data structures.
Returns True if successful, False if found a contradiction.
"""
assert w in G[v]
if w in forced_in_current[v] or len(G[v]) < 3 or len(G[w]) < 3:
return False
remove(v,w)
now_degree_two(v)
now_degree_two(w)
return True
def remove_third_leg(v):
"""
Check if v has two forced edges and if so remove unforced one.
Returns True if successful, False if found a contradiction.
"""
if len(G[v]) != 3 or len(forced_in_current[v]) != 2:
return True
w = [x for x in G[v] if x not in forced_in_current[v]][0]
if len(G[w]) <= 2:
return False
return safely_remove(v,w)
def force(v,w):
"""
Add edge v,w to forced edges.
Returns True if successful, False if found a contradiction.
"""
if w in forced_in_current[v]:
return True # Already forced, nothing to do
if len(forced_in_current[v]) > 2 or len(forced_in_current[w]) > 2:
return False # Three incident forced => no cycle exists
if w not in G[v] or v not in G[w]:
return False # Removed from G after we decided to force it?
forced_in_current[v][w] = forced_in_current[w][v] = True
not_previously_forced = [x for x in (v,w) if x not in forced_vertices]
for x in not_previously_forced:
forced_vertices[x] = True
was_original = G[v][w]
if was_original:
forced_in_input[v][w] = forced_in_input[w][v] = True
def unforce():
"""Undo call to force."""
for x in not_previously_forced:
del forced_vertices[x]
del forced_in_current[v][w],forced_in_current[w][v]
if was_original:
del forced_in_input[v][w],forced_in_input[w][v]
actions.append(unforce)
return remove_third_leg(v) and remove_third_leg(w) and \
force_into_triangle(v,w) and force_into_triangle(w,v) and \
force_from_triangle(v,w)
def force_into_triangle(v,w):
"""
After v,w has been added to forced edges, check if w
belongs to a triangle, and if so force the opposite edge.
Returns True if successful, False if found a contradiction.
"""
if len(G[w]) != 3:
return True
x,y = [z for z in G[w] if z != v]
if y not in G[x]:
return True
return force(x,y)
def force_from_triangle(v,w):
"""
After v,w has been added to forced edges, check whether it
belongs to a triangle, and if so force the opposite edge.
Returns True if successful, False if found a contradiction.
"""
for u in list(G[v]): # Use list to avoid dict changes
if u in G[w]:
if len(G[u]) < 3:
return len(G) == 3 # deg=2 only ok if 3 verts left
x = [y for y in G[u] if y != v and y != w][0]
if not force(u,x):
return False
return True
def contract(v):
"""
Contract out degree two vertex.
Returns True if cycle should be reported, False or None otherwise.
Appends recursive search of contracted graph to action stack.
"""
assert len(G[v]) == 2
u,w = G[v]
if w in G[u]: # About to create parallel edge?
if len(G) == 3: # Graph is a triangle?
return force(u,v) and force(v,w) and force(u,w)
if not safely_remove(u,w):
return None # Unable to remove uw, no cycles exist
if not force(u,v) or not force(v,w):
return None # Forcing the edges led to a contradiction
remove(u,v)
remove(v,w)
G[u][w] = G[w][u] = False
forced_in_current[u][w] = forced_in_current[w][u] = True
del G[v],forced_vertices[v]
def uncontract():
del G[u][w],G[w][u]
del forced_in_current[u][w],forced_in_current[w][u]
forced_vertices[v] = True
G[v] = {}
actions.append(uncontract)
if force_from_triangle(u,w): # Contraction may have made a triangle
actions.append(main) # Search contracted graph recursively
def handle_degree_two():
"""
Handle case that the graph has a degree two vertex.
Returns True if cycle should be reported, False or None otherwise.
Appends recursive search of contracted graph to action stack.
"""
v = degree_two.pop()
def unpop():
degree_two.append(v)
actions.append(unpop)
return contract(v)
def main():
"""
Main event dispatcher.
Returns True if cycle should be reported, False or None otherwise.
Appends recursive search of contracted graph to action stack.
"""
if degree_two:
return handle_degree_two()
# At this point, we are going to branch, and if the time is really
# exponential in the size of the remaining graph we can afford some
# more expensive pruning steps first.
# If graph is Hamiltonian it must be biconnected
if not isBiconnected(G):
return None
# If graph is Hamiltonian, unforced edges must have a perfect matching.
# We jump-start the matching algorithm with our previously computed
# matching (or as much of it as fits the current graph) since that is
# likely to be near-perfect.
unforced = {v:{} for v in G}
for v in G:
for w in G[v]:
if w not in forced_in_current[v]:
unforced[v][w] = True
for v in list(previous_matching.keys()):
if v not in unforced or previous_matching[v] not in unforced[v]:
del previous_matching[v]
M = matching(unforced, previous_matching)
previous_matching.clear()
previous_matching.update(M)
if len(M) != len(G):
return None
# Here with a degree three graph in which the forced edges
# form a matching. Pick an unforced edge adjacent to a
# forced one, if possible, else pick any unforced edge,
# and branch on the chosen edge.
if forced_vertices:
v = arbitrary_item(forced_vertices)
else:
v = arbitrary_item(G)
w = [x for x in G[v] if x not in forced_in_current[v]][0]
def continuation():
"""Here after searching first recursive subgraph."""
if force(v,w):
actions.append(main)
actions.append(continuation)
if safely_remove(v,w):
actions.append(main)
# The main backtracking loop
actions = [main]
while actions:
if actions.pop()():
yield forced_in_input
# If run as "python CubicHam.py", run tests on various small graphs
# and check that the correct number of cycles is generated.
class CubicHamTest(unittest.TestCase):
def check(self,G,N):
"""Make sure G has N Hamiltonian cycles."""
count = 0
for C in HamiltonianCycles(G):
# Count the cycle.
count += 1
# Check that it's a degree-two undirected subgraph.
for v in C:
self.assertEqual(len(C[v]),2)
for w in C[v]:
assert v in G and w in G[v] and v in C[w]
# Check that it connects all vertices.
nreached = 0
x = arbitrary_item(G)
a,b = x,x
while True:
nreached += 1
a,b = b,[z for z in C[b] if z != a][0]
if b == x:
break
self.assertEqual(nreached,len(G))
# Did we find enough cycles?
self.assertEqual(count,N)
def testCube(self):
"""Cube has six Hamiltonian cycles."""
cube = {i:(i^1,i^2,i^4) for i in range(8)}
self.check(cube,6)
def twistedLadder(self,n):
"""Connect opposite vertices on an even length cycle."""
return {i:((i+1)%n,(i-1)%n,(i+n//2)%n) for i in range(n)}
def testEvenTwistedLadders(self):
"""twistedLadder(4n) has 2n+1 Hamiltonian cycles."""
for n in range(4,50,4):
self.check(self.twistedLadder(n),n//2+1)
def testOddTwistedLadders(self):
"""twistedLadder(4n+2) has 2n+4 Hamiltonian cycles."""
for n in range(6,50,4):
self.check(self.twistedLadder(n),n//2+3)
def truncate(self,G):
"""Replace each vertex of G by a triangle and return the result."""
return {(v,w):{(v,u) for u in G[v] if u != w} | {(w,v)}
for v in G for w in G[v]}
def testSierpinski(self):
"""
Sierpinski triangle like graphs formed by repeated truncation
of K_4 should all have exactly three Hamiltonian cycles.
"""
G = self.twistedLadder(4) # Complete graph on four vertices
for i in range(3):
G = self.truncate(G)
self.check(G,3)
if __name__ == "__main__":
unittest.main()