from Domain import *
inf = 20000000000

def mini(x, y):
    if x < y:
        return x
    else:
        return y

def checkNegativeCycle(d,n):
    #check if there exists a negative cycle
    for i in range(0,n):
        if d[n*n-1][i]!=d[n*n-2][i]:
            return True
        return False


def printPath(path,current,stop):
    if path[current] == -1 or path[current] == current:
        print(current,'->')
        return

    printPath(path, path[current], stop)
    print(current)
    if current!=stop:
        print('->')


def lowestCostWalk(graph,start,stop):
    n=graph.getSize()
    #print(n)
    #d=[[inf for x in range((n-1)*(n-1)+1)] for y in range(n)]
    d=[]

    for i in range((n-2)*(n-2)+1):
        d.append([])
        for j in range(n):
            d[i].append(inf)

    print(d[0][0])
    print(d[6][4])

    #5/4


    path=[0 for x in range(n)]



    #print(d[5][0])
    d[0][start]=0
    # print(d[n-1])

    for k in range(1,(n-2)*(n-2)):
        #k=k+1
        for x in range(0,n,1):
            #print("k: ",k,"x: ",x,"\n")
            print("k:",k," x:",x)
            print("\n","list in for x:",graph.getListOut()[x],"\n")
            bestFromOutside=inf
            for y in graph.getListOut()[x]:
                print("y:",y)
                if graph.isEdge(y,x):
                    if bestFromOutside>d[k-1][y]+graph.findCost(y,x):
                        bestFromOutside=d[k-1][y]+graph.findCost(y,x)
                        path[x]=y
            if bestFromOutside>d[k-1][x]:
                path[x]=x

            d[k][x]=mini(d[k-1][x],bestFromOutside)

    if checkNegativeCycle(d, n-2):
        print("Negative cycle!")

    print("\n",d)

    if d[(n-2) * (n-2) - 1][stop] == inf:
        print("No path from start to stop!")
        return

    print("the cost is: ",d[n-2][stop])
    print("\n",d)
    print("\n")
    printPath(path, stop, stop)
    print("\n")