Halin.py

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