CubicHam.py

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