#!/usr/bin/python

import sys, time, random
from utilsp import *
from networkx import *

exhaustive=True


def find_shortest_path(D,u,v,G,timeout):
    print "From " +u + " to " +v
    start=time.time()
    
    #recursive algorithm to find a path from u to v,
    #x is the active vertex, k is the remaining number of edges to add (k=0 means end is reached), path is the current path
    def find_path(D,u,v,x,path,k,G):
        if k < 0 : return None #found no path
        elif too_long(start,timeout): return None #abort if algorithm takes to long
        elif x==v and nx.is_connected(G.subgraph(path)): return path
        else: #branch into successors
            for y in D.successors(x):
                if (not y in path) and (nx.has_path(D,y,v)) and (nx.shortest_path_length(D,y,v)<=k-1): #only if new vertex is not in the existing path and it can reach v by at most k-1 hops
                    newpath = list(path)
                    newpath.append(y)
                    result = find_path(D,u,v,y,newpath,k-1,G)
                    if result != None: return result
        return None



    #check instance once more
    #if not proper(D,G,u,v):
    #    return return None, elapsed(start), "-1"

    #edges that are ingoing to u or outgoing from v will never be used
    for w in D.predecessors(u):
        D.remove_edge(w,u)
    for w in D.successors(v):
        D.remove_edge(v,w)
            
    #reduce exhaustively 
    bothstats(D,G);
    if not exreduce(D,G,u,v,exhaustive):
        print "No-Instance by Data Reduction"
        return None, elapsed(start), "-1"
    
    
    for k in range(max(nx.shortest_path_length(D,u,v),nx.shortest_path_length(G,u,v)),
                   min(len(nodes(G)),maxk)+1):
        Dk=D.copy()
        Gk=G.copy()
        #one more data reduction#
        print "k =",k
        if not exkreduce(Dk,Gk,u,v,k,exhaustive):
            print "solved by DR";
            continue
            
        path = list()
        path.append(u)
        result = find_path(Dk,u,v,u,path,k,Gk)
        if result != None:
            return result, elapsed(start),str(k)
        if too_long(start,timeout):
            return None, str(timeout),str(k-1)
        
    #Identified no-instance
    return None, elapsed(start), "-1"