{{{id=1|
# Derrick's code that makes the Line graph for strong edge coloring
# and preserves the location of points = nice drawing
def StrongEdgeGraph(G):
    G.plot(save_pos=True);
    gpos = G.get_pos();
    
    H = Graph(G.num_edges());
    hpos = {};
    
    for i in range(G.num_edges()):
        x,y,e = G.edges()[i];
        
        H.set_vertex(i, (x,y));
        hpos[i] = ( (gpos[x][0] + gpos[y][0])/2, (gpos[x][1] + gpos[y][1])/2);
        
        for j in range(i+1, G.num_edges()):
            u,v,f = G.edges()[j];
            
            if x == u or x == v or y == u or y == v or G.has_edge(x,u) or G.has_edge(x,v) or G.has_edge(y,u) or G.has_edge(y,v):
                H.add_edge(i,j);

    H.set_pos(hpos);
    return H;


# Test if precoloring extends
# L ... graph
# coloring ... vector with colors, 0 means not colored yet
# v ... next vertex to color
def extend_precoloring_recursive(L, coloring, v):
    if (v >= L.order()):
        #print coloring
        return True
    
    # skip precolored vertex
    if coloring[v] != 0:
        return extend_precoloring_recursive(L,coloring,v+1)
    
    for color in range(1,6):
        color_used = False;
        for u in L.neighbor_iterator(v):
            if coloring[u] == color:
                color_used = True
                break
        if color_used: continue
        
        coloring[v] = color
        if extend_precoloring_recursive(L, coloring, v+1): 
            coloring[v] = 0
            return True
        coloring[v] = 0
    return False

def extend_precoloring(L, coloring):
    return extend_precoloring_recursive(L, coloring, 0)
     

# G is a graph
# uv is a pair of vertices
# returns id of edge uv - it corresponds to the name of the vertex in line graph
def RemapEdgeToLineGraph(G,uv):
    for i in range(G.num_edges()):
        x,y,e = G.edges()[i];
        if ((x == uv[0]) and (y ==uv[1])) or ((x == uv[1]) and (y == uv[0])): return i
    return -1    


# Tests if Y configuration can be colored/reducible
# The function tries all possible colorings of ends of t1 and t2 and finds
# coloring that forbids the most colorings on t3
# t1,t2,t3 ... lengths of the paths Y(t1,t2,t3)
# do_plot  ... some plotting and info
# ignore_not_colorable ... if there is a coloring of t1 and t2 that never
#      extends to t3, we can ignore it - the reason is that t1 and t2 are
#      too close to each other
def TestClawReducibility(t1,t2,t3,do_plot=True, ignore_not_colorable=False):
    
    # wrong numbers when I was writig the code :-)
    t1 += 1
    t2 += 1
    t3 += 1
    
    # Derrick's version - it needs deleting
    #t = max(t1,t2,t3) + 1
    #G = Graph([ [0,1], [0,2], [0,3] ] + [ [1 + 6*i, 4 + 6*i] for i in range(t)] + [ [2 + 6*i, 5 + 6*i] for i in range(t)] + [ [3 + 6*i, 6 + 6*i] for i in range(t)] + [ [1 + 6*i, 7 + 6*i] for i in range(t)] + [ [2 + 6*i, 8 + 6*i] for i in range(t)] + [ [3 + 6*i, 9 + 6*i] for i in range(t)] )

    # version with no deleting needed
    x1 = 0
    x2 = 2*t1+1
    x3 = x2+2*t2+1
    G = Graph( [[0,2], [0,x2+2], [0,x3+2]] + [ [x1+2*i, x1+2*i+2] for i in range(1,t1)] + [[x1+2*i+2, x1+2*i+1] for i in range(t1)] + [[x1+2*t1, x1+2*t1+1]]  +   [ [x2+2*i, x2+2*i+2] for i in range(1,t2)] + [[x2+2*i+2, x2+2*i+1] for i in range(t2)] + [[x2+2*t2, x2+2*t2+1]]  +   [ [x3+2*i, x3+2*i+2] for i in range(1,t3)] + [[x3+2*i+2, x3+2*i+1] for i in range(t3)] + [[x3+2*t3, x3+2*t3+1]] )


    # Triples of verices at the end of the three tentacles of Y
    triple1 = [x1+2*t1-1,x1+2*t1,x1+2*t1+1]
    triple2 = [x2+2*t2-1,x2+2*t2,x2+2*t2+1]
    triple3 = [x3+2*t3-1,x3+2*t3,x3+2*t3+1]
    
    # The triples as edges
    edges1 = [[x1+2*t1, x1+2*t1-2], [x1+2*t1, x1+2*t1-1], [x1+2*t1, x1+2*t1+1]]
    if t2 != 1:
        edges2 = [[x2+2*t2, x2+2*t2-2], [x2+2*t2, x2+2*t2-1], [x2+2*t2, x2+2*t2+1]]
    else:
        edges2 = [[x2+2*t2, 0], [x2+2*t2, x2+2*t2-1], [x2+2*t2, x2+2*t2+1]]
    if t3 != 1:
        edges3 = [[x3+2*t3, x3+2*t3-2], [x3+2*t3, x3+2*t3-1], [x3+2*t3, x3+2*t3+1]]
    else:
        edges3 = [[x3+2*t3, 0], [x3+2*t3, x3+2*t3-1], [x3+2*t3, x3+2*t3+1]]
    
    center  = [2,x2+2,x3+2]  # not really used - for debugging
    L = StrongEdgeGraph(G)
    if do_plot:
        G.show()
        print triple1, triple2, triple3, center
        print edges1, edges2, edges3
        L.show()

    # End triples in line graph    
    triple1L = [ RemapEdgeToLineGraph(G,edges1[0]), RemapEdgeToLineGraph(G,edges1[1]), RemapEdgeToLineGraph(G,edges1[2]) ]
    triple2L = [ RemapEdgeToLineGraph(G,edges2[0]), RemapEdgeToLineGraph(G,edges2[1]), RemapEdgeToLineGraph(G,edges2[2]) ]
    triple3L = [ RemapEdgeToLineGraph(G,edges3[0]), RemapEdgeToLineGraph(G,edges3[1]), RemapEdgeToLineGraph(G,edges3[2]) ]
    
    if do_plot: 
        print triple1L, triple2L, triple3L
    
    coloring = [0] * L.order()
    
    # Always pre color the first triple with 1,2,3. It is by permuting the colors
    coloring[triple1L[0]] = 1  
    coloring[triple1L[1]] = 2  
    coloring[triple1L[2]] = 3  

    # Creates triples for coloring 3 edges sharing a vertex. Notice
    # that the triples have symmetry between second and third coordinate
    color_lists = []
    for i in range(1,6):
        for j in range(1,6):
            for k in range(j+1,6):
                if i == j or j == k or i == k: continue
                color_lists.append([i,j,k])

    max_notextends_cnt = 0

    for list2 in color_lists:
        coloring[triple2L[0]] = list2[0] 
        coloring[triple2L[1]] = list2[1]
        coloring[triple2L[2]] = list2[2]
        
        notextends_cnt = 0

        for list3 in color_lists:
            coloring[triple3L[0]] = list3[0] 
            coloring[triple3L[1]] = list3[1]
            coloring[triple3L[2]] = list3[2]
            
            #print "Testing ",coloring
            if not extend_precoloring(L, coloring):
                notextends_cnt += 1
        if  (not ignore_not_colorable) and (max_notextends_cnt < notextends_cnt):
            max_notextends_cnt = notextends_cnt                 
        if  (ignore_not_colorable) and (max_notextends_cnt < notextends_cnt) and (notextends_cnt != 30):
            max_notextends_cnt = notextends_cnt                 
            
    # We multiply by two since the colorings we were testing have
    # the symmetry there - I mean - we test [1,2,3] but not [1,3,2] and
    # if [1,2,3] does not extend, neither does [1,3,2]
    print "Max not extending:", 2*max_notextends_cnt    
        
    return 2*max_notextends_cnt

# Tries all possible Y with 12 vertices in the responsibility set
# and checks how many colorings do not extend.
def MakeFullTest():
    max_non_extending = 0    
    for x in range(0,8):
        for y in range(x,8):
            z = 12-x-y
            if (z >= 8 or z < 0): continue
            print "Testing Y({},{},{})".format(x,y,z)
            non_extending = TestClawReducibility(x,y,z,False, True)
            #print non_extending
            if non_extending > max_non_extending:
                max_non_extending = non_extending

    print "Max max_non_extending is ", max_non_extending,"We win if it is less than 20" 
    
        
#TestClawReducibility(1,0,0)
#StrongEdgeGraph(G).show()

MakeFullTest()
///
Testing Y(0,5,7)
Max not extending: 2
Testing Y(0,6,6)
Max not extending: 4
Testing Y(0,7,5)
Max not extending: 14
Testing Y(1,4,7)
Max not extending: 2
Testing Y(1,5,6)
Max not extending: 2
Testing Y(1,6,5)
Max not extending: 4
Testing Y(1,7,4)
Max not extending: 8
Testing Y(2,3,7)
Max not extending: 2
Testing Y(2,4,6)
Max not extending: 0
Testing Y(2,5,5)
Max not extending: 2
Testing Y(2,6,4)
Max not extending: 2
Testing Y(2,7,3)
Max not extending: 6
Testing Y(3,3,6)
Max not extending: 0
Testing Y(3,4,5)
Max not extending: 0
Testing Y(3,5,4)
Max not extending: 0
Testing Y(3,6,3)
Max not extending: 2
Testing Y(3,7,2)
Max not extending: 8
Testing Y(4,4,4)
Max not extending: 12
Testing Y(4,5,3)
Max not extending: 0
Testing Y(4,6,2)
Max not extending: 2
Testing Y(4,7,1)
Max not extending: 12
Testing Y(5,5,2)
Max not extending: 2
Testing Y(5,6,1)
Max not extending: 6
Testing Y(5,7,0)
Max not extending: 8
Testing Y(6,6,0)
Max not extending: 6
Max max_non_extending is  14 We win if it is less than 20
}}}

{{{id=4|

///
}}}