#!/usr/bin/python

import sys

d = {} # best known cost from starting node
p = {} # previous node
S = [] # Nodes for which we have found the shortest path
Q = [] # Our worklist

class GraphObject:
    count = 0
    def __init__(self):
        GraphObject.count += 1

class GraphNode (GraphObject):
  count = 0
  def __init__(self, name):
    self.edges = []
    self.name = name
    GraphNode.count += 1
    GraphObject.__init__(self)
  def add_edge(self, edge):
    self.edges.append(edge)

class GraphEdge (GraphObject):
  count = 0
  def __init__(self, weight, target):
    self.weight = weight
    self.target = target
    GraphEdge.count += 1
    GraphObject.__init__(self)

# main algorithm
def dijkstra(nodes):

  def find_min(lst):
    value2beat = -1
    bestnode   = None
    bestindex  = -1
    i = 0
    for node in lst:
      if d[node] != -1 and (value2beat == -1 or d[node] < value2beat):
        value2beat = d[node]
        bestnode   = node
        bestindex  = i
      i += 1
    if bestindex == -1:
      print "Graph is segmented, giving up ..."
      sys.exit(3)
    del nodes[bestindex] # remove from workqueue
    print p[bestnode].name+" -> "+bestnode.name
    return bestnode
  
  while len(Q) > 0:
    u = find_min(Q)
    S.append(u)
    for edge in u.edges:
      target = edge.target
      if d[u] + edge.weight < d[target] or d[target] == -1:
        d[target] = d[u] + edge.weight
        p[target] = u

# read graph
def read_graph (file):
  global conf_filename, conf_skip
  fh = open(file, "r")
  lines = fh.readlines()
  name2node = {}
  for line in lines:
    line = line.strip()
    parts = line.split()
    if   parts[0] == "start":
      print "Adding starting node "+parts[1]
      node = GraphNode(parts[1])
      name2node[parts[1]] = node
      d[node] = 0
      p[node] = node
      Q.append(node) # add to worklist
    elif parts[0] == "node":
      print "Adding node "+parts[1]
      node = GraphNode(parts[1])
      name2node[parts[1]] = node
      d[node] = -1 # coding of infinity
      p[node] = None
      Q.append(node) # add to worklist
    elif parts[0] == "edge":
      print "Adding edge("+name2node[parts[2]].name+","+name2node[parts[3]].name+") of weight "+parts[1]
      edge = GraphEdge(int(parts[1]), name2node[parts[3]])
      name2node[parts[2]].add_edge(edge)
    elif parts[0] == "#":
      a = 42 # line is a comment, skipping ...
    else:
      print "Unable to parse line '"+line+"'"
      system.exit(2)

# guard
if len(sys.argv) != 2:
  print "Syntax: "+sys.argv[0]+" graphfile"
  sys.exit(1)

read_graph(sys.argv[1])
print "Read "+str(GraphNode.count)+" nodes and "+str(GraphEdge.count)+" edges ("+str(GraphObject.count)+" objects)"
print ""
print "Edges chosen:"
dijkstra(Q)