from fibheap import FibHeap

class Graph:
    def __init__(self):
        self.vertices = []

class Vertex:
    def __init__(self, Id):
        self.Id = Id  # only used for printing
        self.neighbours = []
    def __str__(self):
        return self.Id


def dijkstra(g, s):
    for v in g.vertices:
        v.distance = float('inf')
    s.distance = 0
    toexplore = FibHeap(key=lambda v: v.distance)
    toexplore.push(s)
    while toexplore:
        print(toexplore)
        v = toexplore.popmin()
        print("visit", v)
        for w,edgecost in v.neighbours:
            dist_w = v.distance + edgecost
            if dist_w < w.distance:
                w.distance = dist_w
                print("->", w, "distance", w.distance)
                if w in toexplore:
                    toexplore.decreasekey(w)
                else:
                    toexplore.push(w)


if __name__ == '__main__':

    # Create a random graph with <= 30 edges
    g = Graph()
    for i in 'abcdefghijk':
        g.vertices.append(Vertex(i))
    import random
    random.seed('dahlia')
    for _ in range(30):
        u,v = random.choice(g.vertices), random.choice(g.vertices)
        if u==v: continue
        if v in {w for w,dist in u.neighbours}: continue
        u.neighbours.append((v, random.randint(0,10)))

    dijkstra(g, g.vertices[0])