Test whether a graph is an isometric subgraph of a hypercube.
D. Eppstein, September 2005, rewritten May 2007 per arxiv:0705.1025.
import BFS
import Medium
from Bipartite import isBipartite
from UnionFind import UnionFind
from StrongConnectivity import StronglyConnectedComponents
from Graphs import isUndirected
import unittest
def PartialCubeEdgeLabeling(G):
    Label edges of G by their equivalence classes in a partial cube structure.
    We follow the algorithm of arxiv:0705.1025, in which a number of
    equivalence classes equal to the maximum degree of G can be found
    simultaneously by a single breadth first search, using bitvectors.
    However, in order to avoid deep recursions (problematic in Python)
    we use a union-find data structure to keep track of edge identifications
    discovered so far. That is, we repeatedly contract our initial graph,
    maintaining as we do the property that G[v][w] points to a union-find
    set representing edges in the original graph that have been contracted
    to the single edge v-w.
    # Some simple sanity checks
    if not isUndirected(G):
        raise Medium.MediumError("graph is not undirected")
    L = list(StronglyConnectedComponents(G))
    if len(L) != 1:
        raise Medium.MediumError("graph is not connected")
    # Set up data structures for algorithm:
    # - UF: union find data structure representing known edge equivalences
    # - CG: contracted graph at current stage of algorithm
    # - LL: limit on number of remaining available labels
    UF = UnionFind()
    CG = dict([(v,dict([(w,(v,w)) for w in G[v]])) for v in G])
    NL = len(CG)-1
    # Initial sanity check: are there few enough edges?
    # Needed so that we don't try to use union-find on a dense
    # graph and incur superquadratic runtimes.
    n = len(CG)
    m = sum([len(CG[v]) for v in CG])
    if 1<<(m//n) > n:
        raise Medium.MediumError("graph has too many edges")
    # Main contraction loop in place of the original algorithm's recursion
    while len(CG) > 1:
        if not isBipartite(CG):
            raise Medium.MediumError("graph is not bipartite")
        # Find max degree vertex in G, and update label limit
        deg,root = max([(len(CG[v]),v) for v in CG])
        if deg > NL:
            raise Medium.MediumError("graph has too many equivalence classes")
        NL -= deg
        # Set up bitvectors on vertices
        bitvec = dict([(v,0) for v in CG])
        neighbors = {}
        i = 0
        for neighbor in CG[root]:
            bitvec[neighbor] = 1<<i
            neighbors[1<<i] = neighbor
            i += 1
        # Breadth first search to propagate bitvectors to the rest of the graph
        for LG in BFS.BreadthFirstLevels(CG,root):
            for v in LG:
                for w in LG[v]:
                    bitvec[w] |= bitvec[v]
        # Make graph of labeled edges and union them together
        labeled = dict([(v,set()) for v in CG])
        for v in CG:
            for w in CG[v]:
                diff = bitvec[v]^bitvec[w]
                if not diff or bitvec[w] &~ bitvec[v] == 0:
                    continue    # zero edge or wrong direction
                if diff not in neighbors:
                    raise Medium.MediumError("multiply-labeled edge")
                neighbor = neighbors[diff]
        # Map vertices to components of labeled-edge graph
        component = {}
        compnum = 0
        for SCC in StronglyConnectedComponents(labeled):
            for v in SCC:
                component[v] = compnum
            compnum += 1
        # generate new compressed subgraph
        NG = dict([(i,{}) for i in range(compnum)])
        for v in CG:
            for w in CG[v]:
                if bitvec[v] == bitvec[w]:
                    vi = component[v]
                    wi = component[w]
                    if vi == wi:
                        raise Medium.MediumError("self-loop in contracted graph")
                    if wi in NG[vi]:
                        NG[vi][wi] = CG[v][w]
        CG = NG
    # Here with all edge equivalence classes represented by UF.
    # Turn them into a labeled graph and return it.
    return dict([(v,dict([(w,UF[v,w]) for w in G[v]])) for v in G])
def MediumForPartialCube(G):
    Find a medium corresponding to the partial cube G.
    Raises MediumError if G is not a partial cube.
    Uses the O(n^2) time algorithm of arxiv:0705.1025.
    L = PartialCubeEdgeLabeling(G)
    M = Medium.LabeledGraphMedium(L)
    Medium.RoutingTable(M)   # verification step per arxiv:0705.1025
    return M
def PartialCubeLabeling(G):
    """Return vertex labels with Hamming distance = graph distance."""
    return Medium.HypercubeEmbedding(MediumForPartialCube(G))
def isPartialCube(G):
    """Test whether the given graph is a partial cube."""
        return True
    except Medium.MediumError:
        return False
# Perform some sanity checks if run standalone
class PartialCubeTest(unittest.TestCase):
    # make medium from all five-bit numbers that have 2 or 3 bits lit
    twobits = [3,5,6,9,10,12,17,18,20,24]
    threebits = [31^x for x in twobits]
    M523 = Medium.BitvectorMedium(twobits+threebits,5)
    def testIsPartialCube(self):
        M = PartialCubeTest.M523
        G = Medium.StateTransitionGraph(M)
        I = isPartialCube(G)
    def testK4(self):
        G = dict([(i,[j for j in range(4) if j != i]) for i in range(4)])
    def testK33(self):
        G = {0:[3,4,5],1:[3,4,5],2:[3,4,5],3:[0,1,2],4:[0,1,2],5:[0,1,2]}
    def testMediumForPartialCube(self):
        """Check that we get an isomorphic medium via MediumForPartialCube."""
        # Note that we do not get the same tokens.
        # So, we need to check equality of graphs
        # rather than equality of media.
        M = PartialCubeTest.M523
        G = Medium.StateTransitionGraph(M)
        E = MediumForPartialCube(G)
        H = Medium.StateTransitionGraph(E)
        for v in G:
    def test6212(self):
        A graph that can be labeled, but is not a partial cube.
        Tests the code in LabeledGraphMedium that checks for the
        existence of multiple equally labeled edges at a vertex.
        n,a,b,c = 6,2,1,2
        G = {}
        for i in range(n):
            G[i,0] = [(i,1),((i+b)%n,3),((i+c)%n,3)]
            G[i,1] = [(i,0),(i,2),((i-a)%n,2)]
            G[i,2] = [(i,1),(i,3),((i+a)%n,1)]
            G[i,3] = [(i,2),((i-b)%n,0),((i-c)%n,0)]
    def test61150(self):
        Another graph that can be labeled, but is not a partial cube.
        Tests the code in RoutingTable that makes sure that only tokens
        in a single direction belong to the initial list of active tokens.
        G = {}
        n,a,b,c,d = 6,1,1,5,0
        for i in range(n):
            G[i,0] = [(i,1),((i+a)%n,5),((i+b)%n,3)]
            G[i,1] = [(i,0),(i,2),((i-d)%n,4)]
            G[i,2] = [(i,1),(i,3),((i+c)%n,5)]
            G[i,3] = [(i,2),(i,4),((i-b)%n,0)]
            G[i,4] = [(i,3),(i,5),((i+d)%n,1)]
            G[i,5] = [(i,4),((i-a)%n,0),((i-c)%n,2)]
if __name__ == "__main__":