```"""PartialCube.py

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 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]
UF.union(CG[v][w],CG[root][neighbor])
UF.union(CG[w][v],CG[neighbor][root])

# 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]:
UF.union(NG[vi][wi],CG[v][w])
else:
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."""
try:
MediumForPartialCube(G)
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)
self.assertEqual(I,True)

def testK4(self):
G = dict([(i,[j for j in range(4) if j != i]) for i in range(4)])
self.assertEqual(isPartialCube(G),False)

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]}
self.assertEqual(isPartialCube(G),False)

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)
self.assertEqual(set(G),set(H))
for v in G:
self.assertEqual(set(G[v]),set(H[v]))

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)]
self.assertEqual(isPartialCube(G),False)

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)]
self.assertEqual(isPartialCube(G),False)

if __name__ == "__main__":
unittest.main()

```