#!/usr/bin/python

import sys
from Graph import *

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

# 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)