#!/usr/bin/env python3

"""
Simple implementation of Dijkstra's algorithm with step-by-step
output of intermediate results in GraphViz.

Input cam be either a well-behaved GraphViz graph, or a simple list of
weighted edges. Warnings of the form "Cannot handle X" are usually
benevolent and can probably be ignored.

Note to Coders: For optimal results, the output of all GraphViz tools
should order nodes in ascending order, have all edges be from smaller
to larger node, and have edges be in ascending order. This assures (?)
uniform layout of equivalent graphs.
"""

import sys
import re
import random
import getopt



Infty = 1000000000

class Node(object):
    def __init__(self, id):
        self.id = id
        self.dist     = Infty
        self.visited  = False
        self.current  = False
        self.adj_list = []

    def addEdge(self, edge):
        self.adj_list.append(edge)


    def setVisited(self, state=True):
        self.visited = state

    def setCurrent(self, state=True):
        self.current = state

    def updateDist(self, dist):
        if dist < self.dist:
            self.dist = dist
            return True
        return False

    def nodestr(self):
        color = ",style=filled,color=\"#D0D0D0\""
        if self.dist != Infty:
            color = ",style=filled,color=\"#86BEFF\""
        if self.visited:
            color = ",style=filled,color=\"#FFA1A3\""
        if self.current:
            color = ",style=filled,color=\"#8CFF87\""
        distance = str(self.dist)
        if self.dist == Infty:
            distance="&infin;"
        node = "   %s [label = <%s:%3s>%s]\n"%(self.id,self.id, distance,color)
        return node

    def edgestr(self):
        edges = ["   %s -> %s [label=\"%d\"]\n"%(self.id, id, w) \
                 for id,w in self.adj_list if id>self.id]
        return "".join(edges)

    def edgestrs(self):
        edges = ["   %s -> %s [label=\"%d\"]\n"%(self.id, id, w) \
                 for id,w in self.adj_list if id>self.id]
        return edges

    def __str__(self):
        return self.nodestr()+self.edgestr()


class Graph(object):
    def __init__(self, nodes, edges = []):
        self.nodes = {}
        self.nodes2 = []
        for i in nodes:
            self.addNode(i)
        for e in edges:
            self.addEdge(e)

    def addNode(self, id):
        if not id in self.nodes:
            self.nodes[id] = Node(id)
            self.nodes2.append(id)

    def getNodeNames(self):
        return list(self.nodes.keys())

    def node(self,id):
        return self.nodes[id]

    def addEdge(self, edge):
        (node1, node2),weight = edge
        self.addNode(node1)
        self.addNode(node2)
        self.nodes[node1].addEdge((node2, weight))
        self.nodes[node2].addEdge((node1, weight))

    def __str__(self):
        nodes = self.nodes2
        edges = []
        for n in self.nodes.values():
            edges.extend(n.edgestrs())
        # nodes.sort()
        return """
digraph mygraph {
   rankdir = LR
   #bgcolor=transparent
   node [fontsize=18]
   edge [fontsize=14, dir=none]

"""\
    + "".join(sorted([self.nodes[i].nodestr() for i in nodes]))+"\n"\
    + "".join(sorted(edges))+"""
}
"""


def dijkstra(graph, start):
    writeGraph(graph)
    vc = graph.node(start)
    vc.updateDist(0)
    while vc:
        print("%s  &  %2d  \\\\"%(vc.id, vc.dist))
        vc.setCurrent()
        writeGraph(graph)
        for n,w in vc.adj_list:
            node = graph.node(n)
            node.updateDist(vc.dist+w)
        writeGraph(graph)
        vc.setVisited()
        vc.setCurrent(False)
        vc = None
        for n in graph.nodes.values():
            if not n.visited and n.dist!=Infty:
                if not vc or n.dist < vc.dist:
                    vc = n
    writeGraph(graph)



counter = 0

def newfile():
    global counter
    name = "dijkstra%03d.gv"%(counter,)
    counter = counter+1
    print("Writing to file", name)
    return open(name, "w");

def writeGraph(graph):
    fp = newfile()
    print (graph, file=fp)
    fp.close()


gvvertexRe = re.compile("\s*(\w+)\s*->\s*(\w+)\s*\[label=\"\s*(\d*)\s*\"\]")
gvedgeRe   = re.compile("\s*(\w+)\s*\[label")


def parseGraph(name):
    fp = open(name, "r")
    res = []
    nodes = []
    for line in fp:
        mo1 = gvvertexRe.match(line)
        mo2 = gvedgeRe.match(line)
        if mo1:
            print("Match", line)
            f,t,w = mo1.groups()
            res.append(((f.strip(), t.strip()), int(w)))
        elif mo2:
            nodes.append(mo2.groups()[0])
        else:
            try:
                e,w=line.split(":")
                f,t=e.split("->")
                res.append(((f.strip(), t.strip()), int(w)))
            except ValueError:
                print("Cannot handle ", line)
    fp.close()
    return nodes, res


if __name__ == '__main__':
    opts, args = getopt.gnu_getopt(sys.argv[1:],
                                   "h",
                                   ["help"])
    print(args)
    start = "a"
    if args:
        nodes, edges = parseGraph(args[0])
        graph = Graph(nodes, edges)
        if len(args)>=2:
            start = args[1]
        else:
            start= graph.getNodeNames()[0]

    else:
        graph = Graph([], [
            (("a", "b"), 17),
            (("a", "c"), 8),
            (("a", "f"), 6),
            (("a", "g"), 12),
            (("b", "c"), 4),
            (("b", "d"), 2),
            (("b", "e"), 15),
            (("c", "e"),  5),
            (("c", "g"),  9),
            (("d", "f"), 10),
            (("e", "f"), 14),
            (("e", "g"), 11),
            (("f", "g"), 16)])

    dijkstra(graph, start)
    # writeGraph(graph)