##  Program to find shortest path in Multigraph

import sys
from time import clock


class Arc:
    weight = 0
    startNode = None
    endNode = None

    def __init__(self, startNode, endNode, weight):
        if weight > 0:
            self.weight = weight
        else:
            raise ValueError("Weight cannot be negative.")
        self.startNode = startNode
        self.endNode = endNode
        memory=sys.getsizeof(weight)+sys.getsizeof(startNode)+sys.getsizeof(endNode)

class Node:
    name = None

    order = None
    pLabel = None
    tLabel = None

  

    def __init__(self, name):
        self.name = name
##    memory+=sys.getsizeof(name)+sys.getsizeof(order)+sys.getsizeof(pLabel)+sys.getsizeof(tLabel)
    
class Construct_Graph:
    nodes = {}
    arcs = []
    results = []

##    memory+=sys.getsizeof(nodes)+sys.getsizeof(arcs)+sys.getsizeof(results)+sys.getsizeof(node)+sys.getsizeof(arc)+sys.getsizeof(current)+sys.getsizeof(newTLabel)+sys.getsizeof(lowest)

    def addNode(self, name = None, node = None):
        if node == None:
            node = Node(name)
        self.nodes[node.name] = (node)
        return node.name

    def addNodes(self, nodeList):
        for name in nodeList:
            node = Node(name)
            self.nodes[node.name] = (node)

    def addArc(self, startNode = None, endNode = None, weight = None, arc = None):
        if arc == None:
            arc = Arc(startNode, endNode, weight)
        self.arcs.append(arc)
        return arc

    def addArcs(self, arcList):
        for (startNode, endNode, weight) in arcList:
            arc = Arc(startNode, endNode, weight)
            self.arcs.append(arc)

    def find_shortest_path(self, startNode, endNode):
        current = startNode
        order = 1
        self.nodes[current].pLabel = 0
        self.nodes[current].order = order
        order += 1
        while self.nodes[endNode].pLabel == None:
            for arc in self.arcs:
                if arc.startNode == current:
                    if self.nodes[arc.endNode].pLabel == None:
                        if not self.nodes[current].tLabel == None:
                            newTLabel = self.nodes[current].tLabel + arc.weight
                        else:
                            newTLabel = arc.weight
                        if newTLabel < self.nodes[arc.endNode].tLabel or self.nodes[arc.endNode].tLabel == None:
                            self.nodes[arc.endNode].tLabel = newTLabel
                elif arc.endNode == current:
                    if self.nodes[arc.startNode].pLabel == None:
                        if not self.nodes[current].tLabel == None:
                            newTLabel = self.nodes[current].tLabel + arc.weight
                        else:
                            newTLabel = arc.weight
                        if newTLabel < self.nodes[arc.startNode].tLabel or self.nodes[arc.startNode].tLabel == None:
                            self.nodes[arc.startNode].tLabel = newTLabel
            lowest = None
            for name in self.nodes.iterkeys():
                if self.nodes[name].pLabel == None:
                    if not self.nodes[name].tLabel == None:
                        if lowest:
                                if self.nodes[name].tLabel < self.nodes[lowest].tLabel:
                                    lowest = name
                        else:
                            lowest = name
            self.nodes[lowest].pLabel = self.nodes[lowest].tLabel
            self.nodes[lowest].order = order
            order += 1
            current = lowest
        current = endNode
        done = False
        while done == False:
            for arc in self.arcs:
                if arc.startNode == current:
                    if not self.nodes[arc.endNode].pLabel == None:
                        if arc.weight+self.nodes[arc.endNode].pLabel == self.nodes[current].pLabel:
                            current = arc.endNode
                            self.results.append(arc)
                elif arc.endNode == current:
                    if not self.nodes[arc.startNode].pLabel == None:
                        if arc.weight+self.nodes[arc.startNode].pLabel == self.nodes[current].pLabel:
                            current = arc.startNode
                            self.results.append(arc)
            if current == startNode:
               done = True
        self.results.reverse()
    
        return (self.nodes[endNode].pLabel, self.results)
    

start=clock()
memory=0
##InFile=open('in_sec19_5.txt','r')
OutFile=open('out_15_sec17_5.txt','w')

testGraph = Construct_Graph()

#'''
A = testGraph.addNode("A")
B = testGraph.addNode("B")
C = testGraph.addNode("C")
D = testGraph.addNode("D")
E = testGraph.addNode("E")
F = testGraph.addNode("F")
G = testGraph.addNode("G")

startNode = A
endNode = G

testGraph.addArcs([ (A, B, 1),
                    (A, C, 2),
                    (A, D,14),
                    (B, E, 5),
                    (B, D, 5),
                    (C, D, 4),
                    (C, F, 6),
                    (D, E, 1),
                    (D, F, 2),
                    (D, G, 11),
                    (E, G, 9),
                    (F, G, 7)])
#'''


(weight, results) = testGraph.find_shortest_path(startNode, endNode)
old = None
OutFile.write("Shortest Path in MutiStage Graph(Weight)= " + str(weight) )

for arc in results:
    if old == None:
        if arc.startNode == startNode:
            print (" | " + arc.startNode)
            print ("-> " + arc.endNode)
            old = arc.endNode
        elif arc.endNode == startNode:
            print (" | " + arc.endNode)
            print ("-> " + arc.startNode)
            old = arc.startNode
    elif old == arc.startNode:
        print ("-> " + arc.endNode)
        old = arc.endNode
    elif old == arc.endNode:
        print ("-> " + arc.startNode)
        old = arc.startNode


OutFile.write("\n Total Execution Time : "+str(clock()-start)+" seconds")                    
      
##OutFile.write("\n Memory used : "+str(memory)+" Bytes")        


##InFile.close()
OutFile.close()

print " Output File  is Generated"