import networkx as nx
import datetime

#this is the main recursive coloring procedure
def color_proc(ht):
    cv = len(ht)
    foundpath=False
    #this for loop cycles through all 8 possibilities for up(cv)
    extend()
    for c in range(8):
        if (cv == 0 and c in avoidcase):
            continue
        #if we found a blue path in a previous iteration, then this same blue path is valid for the current
        #iteration as long as we are not in the case RRR or RRB
        if c not in avoidcase and foundpath:
            continue
        ht.append([c,[]])       
        paint_with_list(cv,clists[c])
        #this `try' looks for a red cycle
        try:   
            cycle = nx.find_cycle(RG)
            print cv,";", [ht[i][0] for i in range(cv+1)],";", cycle,";",len(cycle),";", "r"
            #if no red cycle is found, we look for a high density blue path
        except:  
            foundpath = False
            if c not in avoidcase:   
                #if cv is not too large, we look for a path beginning at 0 and ending at cv 
                if cv < stitchcutoff:
                    BGI = BG.subgraph(range(cv+1))
                    for path in nx.all_simple_paths(BGI, 0, cv):
                        #this if clause stores the longest path ending at cv seen so far
                        if len(path)> len(ht[cv][1]):
                            ht[cv][1] = path
                        if len(path)>= ratio*cv+1:
                            print cv,";", [ht[i][0] for i in range(len(ht))],";", path,";",(len(path)-1.)/cv,";",  "b"
                            foundpath=True
                            break
                #if cv is large, it is too computationally expensive to search for a path from 0 to cv, so we search for a 
                #path starting at a later vertex (newstart) and append it to the longest path found ending at newstart.
                else:
                    for newstart in range(cv-lookback, cv):
                        if foundpath:
                            break
                        if ht[newstart][0]==0:
                            continue
                        if len(ht[newstart][1]) < .7*newstart+1:
                            continue
                        BGI = BG.subgraph(range(newstart,cv+1))
                        for path in nx.all_simple_paths(BGI, newstart, cv):
                            stitch = ht[newstart][1][:-1] + path
                            if len(stitch) > len(ht[cv][1]):
                                ht[cv][1] = stitch
                            if len(stitch) >= ratio*cv+1:
                                print cv,";", [ht[i][0] for i in range(len(ht))],";", stitch,";",(len(stitch)-1.)/cv,";",  "b"
                                foundpath=True
                                break
            if(foundpath==False):
                color_proc(ht)

        uncolor(cv)
        ht.pop()
    shorten()
def uncolor(v):
    RG.remove_edges_from([(v, v+1), (v, v+2), (v, v+3)])
    BG.remove_edges_from([(v, v+1), (v, v+2), (v, v+3)])

            
def paint_with_list(v, l):
    for i in range(3):
        if l[i] == 0:
            RG.add_edges_from([(v, v+i+1)])
        else:
            BG.add_edges_from([(v, v+i+1)])
    return 1


def extend():
    RG.add_node(RG.number_of_nodes())
    BG.add_node(BG.number_of_nodes())
def shorten():
    RG.remove_node(RG.number_of_nodes()-1)
    BG.remove_node(BG.number_of_nodes()-1)
 
 
 

    
n=5
avoidcase = {0, 3} #we don't start or end with RRR or RRB
clists = [[0,0,0], [1,0,0], [0,1,0], [0,0,1], [1,1,0], [1,0,1], [0,1,1], [1,1,1]]
BG = nx.Graph()
RG = nx.Graph()
BG.add_nodes_from(range(n))
RG.add_nodes_from(range(n))
print "Enter desired density as a decimal. e.g., `.75' or `4./7.' "
ratio=input()
ht=[] 
stitchcutoff = 17
lookback =12
begin_time = datetime.datetime.now()   
color_proc(ht)
end_time = datetime.datetime.now()  
print end_time-begin_time