"""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 = {v:{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 = {v:0 for v in CG} neighbors = {} i = 0 for neighbor in CG[root]: bitvec[neighbor] = 1<