"""Single Source Shortest Path
"""

import graph
import fibonacci_heap as heap
from util import VertexWeight

def __relax(u, v, W, d, p):
    if d[v] > d[u] + W[(u,v)]:
        d[v] = d[u] + W[(u,v)]
        p[v] = u

def __initialise_sssp(V, s, infinity):
    d = {}
    p = {}
    d[s] = 0
    p[s] = None
    for v in V:
        if v == s: continue
        d[v] = infinity
        p[v] = None
    return d,p

def dijkstra(V, adj, W, s, infinity):
    d,p = __initialise_sssp(V, s, infinity)
    S = []
    node = {}
    Q = heap.make_heap()
    for u in V:
        node[u] = heap.make_node(VertexWeight(u, d[u]))
        heap.insert(Q, node[u])
    while not heap.is_empty(Q):
        x = heap.extract(Q)
        u = x.key.get_vertex()
        if DEBUG: print "visit", u
        S.append(u)
        for v in adj[u]:
            __relax(u, v, W, d, p)
            heap.decrease_key(Q, node[v], VertexWeight(v, d[v]))
    return (d, p)

def bellman_ford(V, E, W, s, infinity):
    d,p = __initialise_sssp(V, s, infinity)
    for i in xrange(len(V) - 1):
        for (u,v) in E:
            __relax(u, v, W, d, p)
    for (u,v) in E:
        if d[v] > d[u] + W[(u,v)]:
            return False, d, p
    return True, d, p
        
    

######################################################################
DEBUG = False

def test():
    V = [1,2,3,4,5,6,7,8,9]
    E = [(1,2), (2,3),
         (4,5), (5,6),
         (7,8), (8,9),
         (1,4), (4,7),
         (2,5), (5,8),
         (6,3), (6,9)]
    adj = graph.make_adj(V, E)
    E_weight = [5,8,5,3,2,5,
                3,2,2,1,2,2]

    W = {}
    for i in xrange(len(E)):
        W[E[i]] = E_weight[i]

    print """
    First determine a safe value for infinity.  Since the longest path
    should be no longer than using all the edges, we set infinity to
    the sum of all the weights + 1.
    """

    infinity = sum(E_weight) + 1
    print "infinity =", infinity

    print """
    Test Dijkstra's Single Source Shortest Path
    """
    d, p = dijkstra(V, adj, W, V[0], infinity)
    __print_results(d,p,V)

    print """
    Test Bellman Ford's Single Source Shortest path
    """
    no_cycles, d, p = bellman_ford(V, E, W, V[0], infinity)
    if no_cycles:
        __print_results(d,p,V)
    else:
        print "Cycles were found."

def __print_results(d,p,V):
    for u in V:
        print "Vertex %2s: d=%2s, p=%2s" % (u, d[u], p[u])

######################################################################
if __name__ == '__main__':
    test()

######################################################################