Given an edge-coloring ec, compute the $c^*$ value at a vertex, which is the color-blind partition at $v$.
{{{id=1| def cstar(G, v, k, ec): c = [0] * k; for x,y in ec.keys(): if v in [x,y]: c[ec[(x,y)]] += 1; c.sort(); return c; /// }}}BFSOrder returns a list of the edges of $G$ that match the order they would be visited by a breadth-first search.
{{{id=3| def BFSOrder(G, u): O = [u]; Q = [u]; d = {}; for v in G.vertices(): d[v] = G.num_verts(); d[u] = 0; while len(Q) > 0: v = Q[0]; Q.remove(v); for y in G.neighbors(v): if d[y] == G.num_verts(): d[y] = d[v] + 1; Q.append(y); O.append(y); return O; /// }}}colexEdgeOrder returns a list of the edges of $G$ minimizing the co-lexicographic rank of the pair $uv$.
{{{id=5| def colexEdgeOrder(G, Vorder): Eorder = []; for i in range(0,len(Vorder)): for j in range(0,i): if G.has_edge( [Vorder[i],Vorder[j]] ): Eorder.append( (Vorder[i],Vorder[j]) ); return Eorder; /// }}}getColorBlindPartition does the same as cstar
{{{id=7| def getColorBlindPartition(G,r, v, coloring): overc = [0]*r; for u in G.neighbors(v): edge1 = (v,u); edge2 = (u,v); if edge1 in coloring.keys(): overc[ coloring[edge1] ] += 1; elif edge2 in coloring.keys(): overc[ coloring[edge2] ] += 1; else: return None; # not fully defined! # overc is determined! overc.sort(); # ok, now we have it! return overc; /// }}}compareLists checks if two sorted lists contain the same elements.
{{{id=9| def compareLists( l1, l2 ): if l1 == None: return False; if l2 == None: return False; if len(l1) != len(l2): return False; for i in range( len(l1) ): if l1[i] != l2[i]: return False; return True; /// }}}dal computes the color-blind index of a graph $G$, it returns a pair $(r,c)$ where $c$ is a $r$-dal-coloring of $G$. It uses the recursive method findColorBlindColoring.
If no dal-coloring exists, then (None,None) is returned.
{{{id=11| def findColorBlindColoring(G, r, EdgeOrder, coloring, cur_edge, covered_vertices = [], timeout = None ): if timeout != None and timeout < time(): return None, "Timeout!"; for u,v,e in G.edges(): cstaru = getColorBlindPartition(G, r, u, coloring); cstarv = getColorBlindPartition(G, r, v, coloring); if compareLists(cstaru, cstarv): return None, None; if cur_edge >= len(EdgeOrder): return r, coloring; # create a random offset, helps to explore random-ish colorings first. offset = int(random()* r); # select a color for cur_edge... for i in range(r): e = EdgeOrder[cur_edge]; u = e[0]; v = e[1]; newcolors = {}; for f in coloring.keys(): newcolors[f] = coloring[f]; newcolors[ e ] = (i + offset) % r; # Determine if this is a good choice... # Does it distinguish any pair that is determined so far? newr,c = findColorBlindColoring(G, r, EdgeOrder, newcolors, cur_edge + 1, timeout = timeout ); if c != None: return newr,c; # otherwise, loop again. return None, None; def dal(G, maxtime=None, r=1): if not G.is_connected(): val = 0; fullc = {}; for C in G.components(): v,c = dal(C); if v == None: return None,None; for e in c.keys(): fullc[e] = c[e]; if v > val: val = v; return val, fullc; k = G.chromatic_number(); D = G.degree_sequence()[0]; if Partitions(D).cardinality() < k: # a very simple failure! return None, None; # if dal is not defined, then we will spin our wheels for a long time. # when do we know we can stop? while r < G.num_edges(): # We will try to find an edge-coloring on r colors # that distinguishes all neighbors. # Let's select a vertex ordering based on BFS u = None; du = G.num_verts(); for v in G.vertices(): if G.degree(v) < du: u = v; du = v; # ok, u is a vertex of minimum degree. VOrder = BFSOrder(G, u); Eorder = colexEdgeOrder(G, VOrder); timeout = None; if maxtime != None: timeout = time() + r * maxtime; newr, coloring = findColorBlindColoring(G, r, Eorder, {}, 0, timeout=timeout); if coloring != None: return newr, coloring; print "No coloring for r=%d" % r; r += 1; return None, None; /// }}}ShowEdgeColoredGraph draws the graph $G$ with colors representing the colors on the edges of $G$.
{{{id=13| def ShowEdgeColoredGraph(G, r, c): color_names = ["red", "green", "black", "blue", "purple" ]; edge_colors = {}; for i in range(r): edge_colors[ color_names[i] ] = []; for e in c.keys(): if c[e] == i: edge_colors[ color_names[i] ].append(e); G.show(save_pos=True,edge_colors=edge_colors); /// }}}dalColorings is an iterator for all colorings of some edges and with some vertices being assigned a $c^*$-value. This is used to test reducibility.
{{{id=15| class dalColorings(object): def __init__(self, G, k, to_assign_cstar=[], show=True): self.G = G; self.k = k; self.ec = {}; self.vc = {}; self.i = 0; self.to_assign = to_assign_cstar; self.show = show; self.colorings = []; self.E = G.edges(); # colexEdgeOrder(G, G.vertices()); def __iter__(self): return self; def __next__(self): return self.next(); def next(self): # goal: construct the NEXT coloring! if self.i >= len(self.E): self.i -= 1; while self.i >= 0: if self.i >= len(self.E): return self.ec; m = 0; for j in range(self.i): x,y,_ = self.E[j]; if self.ec[(x,y)] >= m: m = self.ec[(x,y)]+1; d = 0; u,v,_ = self.E[self.i]; if (u,v) in self.ec.keys(): d = self.ec[(u,v)] + 1; if d >= min(self.k, m + 1): del self.ec[(u,v)]; self.i -= 1; continue; # try the next color! self.ec[(u,v)] = d; # does it work? fails = False; cstaru = getColorBlindPartition(self.G, self.k, u, self.ec); cstarv = getColorBlindPartition(self.G, self.k, v, self.ec); if cstaru != None: for x in self.G.neighbors(u): cstarx = getColorBlindPartition(self.G, self.k, x, self.ec); if compareLists(cstarx, cstaru): fails = True; if cstarv != None: for x in self.G.neighbors(v): cstarx = getColorBlindPartition(self.G, self.k, x, self.ec); if compareLists(cstarx, cstarv): fails = True; if not fails: self.i += 1; # loop ends... so we are done with things! raise StopIteration(); /// }}}canExtend tests if a given edge coloring and $c^*$-assignment to some vertices can be extended to a dal-coloring of the configuration (where $c^*(v) \neq c^*(u)$ for all edges $uv$, even if one of the endpoints was preset).
{{{id=17| def CERecurse(G, k, E, c, cstar, i): #print i, E; for x,y,_ in G.edges(): if x in cstar.keys(): cx = cstar[x]; else: cx = getColorBlindPartition(G,k,x,c); if y in cstar.keys(): cy = cstar[y]; else: cy = getColorBlindPartition(G,k,y,c); if compareLists(cx,cy): return False; if i >= len(E): return c; x,y = E[i]; for d in range(0,k): c[(x,y)] = d; cp = CERecurse(G, k, E, c, cstar, i+1); if cp != False: return cp; del c[(x,y)]; return False; def canExtend(G, k, c, cstar): E = []; for x,y,e in G.edges(): if (x,y) not in c.keys() and (y,x) not in c.keys(): E.append( (x,y) ); return CERecurse(G, k, E, c, cstar, 0); /// }}}enumerate3Colorings enumerates all possible 3-edge-colorings of a subset of edges and 3-colorings of the specified vertices. Used for reducibility.
{{{id=19| def e3CRecurse(H, tac, E, vc, ec, vi, ei): l = []; if vi < len(tac): # select partitions! for p in [ [1,1,1], [0,1,2], [0,0,3] ]: vc[tac[vi]] = p; lp = e3CRecurse(H, tac, E, vc, ec, vi + 1, ei); for vcp, ecp in lp: l.append( (vcp,ecp) ); del vc[tac[vi]]; return l; if ei >= len(E): vcp = {}; ecp = {}; for v in vc.keys(): vcp[v] = vc[v]; for e in ec.keys(): ecp[e] = ec[e]; return [ (vcp, ecp) ]; for c in range(3): ec[E[ei]] = c; lp = e3CRecurse(H, tac, E, vc, ec, vi, ei + 1); for vcp, ecp in lp: l.append( (vcp,ecp) ); del ec[E[ei]]; return l; def enumerate3Colorings(H, to_assign_cstar): vc = {}; ec = {}; E = H.edges(); return e3CRecurse(H, to_assign_cstar, E, vc, ec, 0, 0); /// }}}is3Reducible determines if a configuration is reducible after deleting some vertices and edges.
{{{id=20| def is3Reducible(G, Deletion): H = Graph(); count = 0; to_assign_cstar = []; for x,y,e in G.edges(): if x not in Deletion and y in Deletion: H.add_edge(x,y); if x not in to_assign_cstar: to_assign_cstar.append(x); if y not in Deletion and x in Deletion: H.add_edge(x,y); if y not in to_assign_cstar: to_assign_cstar.append(y); F = Graph(G.edges()); for v in G.vertices(): if v not in Deletion and v not in to_assign_cstar: F.delete_vertex(v); hpos = {}; for v in H.vertices(): if v in G.vertices(): hpos[v] = G.get_pos()[v]; H.set_pos(hpos); H.show(); for vc, ec in enumerate3Colorings(H, to_assign_cstar): # try to extend to edges of G count += 1; #print vc; #print ec; ecp = canExtend(F, 3, ec, vc); if not ecp: print "Vertices:", vc; print "Edges:", ec; ShowEdgeColoredGraph(F, 3, ec); return False; #else: # ShowEdgeColoredGraph(F, 3, ecp); if count % 100 == 0: print "checked %d colorings" % count; return True; /// }}}is3DCReducible tests if a configuration is reducible after deleting some vertices and edges and contracting others.
{{{id=22| def is3DCReducible(G, Deletion, Matching): H = Graph(); count = 0; to_assign_cstar = []; for x,y,e in G.edges(): if x not in Deletion and y in Deletion: H.add_edge(x,y); if x not in to_assign_cstar: to_assign_cstar.append(x); if y not in Deletion and x in Deletion: H.add_edge(x,y); if y not in to_assign_cstar: to_assign_cstar.append(y); F = Graph(G.edges()); for v in G.vertices(): if v not in Deletion and v not in to_assign_cstar: F.delete_vertex(v); hpos = {}; for v in H.vertices(): if v in G.vertices(): hpos[v] = G.get_pos()[v]; H.set_pos(hpos); H.show(); for vc, ec in enumerate3Colorings(H, to_assign_cstar): valid = True; for x,y in Matching: if compareLists(vc[x],vc[y]): valid = False; if not valid: continue; # try to extend to edges of G count += 1; #print vc; #print ec; ecp = canExtend(F, 3, ec, vc); if not ecp: print "Vertices:", vc; print "Edges:", ec; ShowEdgeColoredGraph(F, 3, ec); return False; #else: # ShowEdgeColoredGraph(F, 3, ecp); if count % 100 == 0: print "checked %d colorings" % count; return True; /// }}}We now test if the 1-buoy reduction is reducible.
{{{id=31| G = Graph(); G.add_cycle(range( 0, 3)); G.add_cycle(range( 3, 7)); G.add_edge(0,3); G.add_edge(4,6); G.add_edge(1,7); G.add_edge(2,8); G.add_edge(5,9); pos = {}; pos[0] = (0, 0); pos[3] = ( 1, 0); pos[1] = (-1,-1); pos[7] = (-2,-2); pos[2] = (-1, 1); pos[8] = (-2, 2); pos[4] = (2,1); pos[5] = (3,0); pos[6] = (2,-1); pos[9] = (4,0); G.set_pos(pos) G.show(save_pos=True); print is3DCReducible(G, range(0,7), [ [7,8] ]) ///
checked 100 colorings
checked 200 colorings
checked 300 colorings
checked 400 colorings
True
}}}
We now test that the 2-triangle reduction is reducible.
{{{id=25| G = Graph(); G.add_cycle(range( 0, 3)); G.add_cycle(range( 3, 6)); G.add_cycle(range( 6, 9)); G.add_cycle(range( 9,12)); G.add_edge(0,3); G.add_edge(1,4); G.add_edge(2,6); G.add_edge(5,9); G.add_edge(7,12); G.add_edge(8,13); G.add_edge(10,14); G.add_edge(11,15); pos = {}; pos[0] = (-1, 1); pos[3] = ( 1, 1); pos[1] = (-1,-1); pos[4] = ( 1,-1); pos[2] = (-2, 0); pos[5] = ( 2, 0); pos[9] = ( 3, 0); pos[10] = (4, 1); pos[11] = (4,-1); pos[14] = (5, 2); pos[15] = (5,-2); pos[6] = (-3,0); pos[7] = (-4,1); pos[8] = (-4,-1); pos[12] = (-5, 2); pos[13] = (-5,-2); G.set_pos(pos) G.show(save_pos=True); print is3Reducible(G, range(6)) ///
True
}}}
We now test if the 2-buoy reduction is reducible.
{{{id=27| G = Graph(); G.add_cycle(range( 0, 4)); G.add_cycle(range( 4, 8)); G.add_cycle(range( 8, 11)); G.add_cycle(range( 11,14)); G.add_edge(0,2); G.add_edge(4,6); G.add_edges([ [1,8], [3,5], [ 7, 11] ] ); pos = {}; pos[0] = (-2, 1); pos[1] = (-3, 0); pos[2] = (-2,-1); pos[3] = (-1, 0); pos[4] = ( 2, 1); pos[5] = ( 1, 0); pos[6] = ( 2,-1); pos[7] = ( 3, 0); pos[8] = (-4,0); pos[9] = (-5,1); pos[10] = (-5,-1); pos[11] = ( 4,0); pos[12] = ( 5,1); pos[13] = ( 5,-1); G.set_pos(pos) G.show(save_pos=True); print is3DCReducible(G, range(8), [ [8,11] ]) ///
True
}}}
We now test if the sparse reduction is reducible.
{{{id=29| G = Graph(); G.add_cycle(range( 0, 3)); G.add_cycle(range( 3, 6)); G.add_cycle(range( 6, 9)); G.add_cycle(range( 9,12)); G.add_cycle(range(12,15)); G.add_cycle(range(15,18)); G.add_edges( [ [0,6], [2,9], [1,4], [3,15], [5,12] ] ); G.delete_vertices([7,8,10,11,13,14,16,17]); pos = {}; pos[1] = (-1,0); pos[4] = (1,0); pos[0] = (-2,1); pos[2] = (-2,-1); pos[6] = (-3,2); pos[9] = (-3,-2); pos[3] = (2,1); pos[5] = (2,-1); pos[12]= (3,-2); pos[15] = (3,2); G.set_pos(pos); G.show(); print is3DCReducible(G, range(6), [ [12,15], [9,6] ]) ///
checked 100 colorings
checked 200 colorings
checked 300 colorings
checked 400 colorings
checked 500 colorings
checked 600 colorings
checked 700 colorings
checked 800 colorings
checked 900 colorings
checked 1000 colorings
checked 1100 colorings
checked 1200 colorings
checked 1300 colorings
checked 1400 colorings
checked 1500 colorings
checked 1600 colorings
checked 1700 colorings
checked 1800 colorings
checked 1900 colorings
checked 2000 colorings
checked 2100 colorings
checked 2200 colorings
checked 2300 colorings
checked 2400 colorings
checked 2500 colorings
checked 2600 colorings
checked 2700 colorings
checked 2800 colorings
checked 2900 colorings
True
}}}
We now create a variable gadget and test all possible colorings (see Claim 2.3 in the paper).
{{{id=33| G = Graph(); G.add_edges([ ("p%d"%i,"p%d"%(i+1)) for i in range(7) ]); G.add_edges([ ("p%d"%i,"v%d"%i) for i in range(1, 7) ]); G.add_edges([ ("v%d"%i,"r%d"%(2*i-1)) for i in range(1, 7) ]); G.add_edges([ ("v%d"%i,"r%d"%(2*i)) for i in range(1, 7) ]); pos = {}; for i in range(8): pos["p%d"%i] = (i,0); for i in range(1,7): pos["v%d"%i] = (i,1); pos["r%d"%(2*i-1)] = (i-0.25,2); pos["r%d"%(2*i)] = (i+0.25,2); G.set_pos(pos); G.show() ///
}}}
{{{id=34|
H3 = G.subgraph(["p1","p0","p2","v1", "v3", "p3", "r5","r6"]);
H3.delete_edge("p2","p3");
H4 = G.subgraph(["p1","p0","p2","v1", "v4", "p4", "r7","r8"]);
H3.show();
H4.show();
///
}}}
{{{id=36|
x = "p1";
y = "v3";
for c in dalColorings(H3,2):
if cstar(H3,x,2,c) == cstar(H3,y,2,c):
continue;
cnew = {};
for e in c.keys():
cnew[e] = c[e];
ShowEdgeColoredGraph(H3,2,cnew);
cp = canExtend(G, 2, cnew, {});
if cp == None:
print "Problem! Cannot extend!";
else:
ShowEdgeColoredGraph(G,2,cp);
///
}}}
{{{id=38|
x = "p1";
y = "v4";
for c in dalColorings(H4,2):
if cstar(H4,x,2,c) != cstar(H4,y,2,c):
continue;
cnew = {};
for e in c.keys():
cnew[e] = c[e];
ShowEdgeColoredGraph(H4,2,cnew);
cp = canExtend(G, 2, cnew, {});
if cp == None:
print "Problem! Cannot extend!";
else:
ShowEdgeColoredGraph(G,2,cp);
///
}}}
{{{id=37|
///
}}}