from graph import *

class Queue:            # naive; should be modified for constant time enqueue
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def enqueue(self, item):
        self.items.insert(0,item)
    def dequeue(self):
        return self.items.pop()
    def size(self):
        return len(self.items)
    
# explore from node with key vertKey, calling f at each node
def bfs(g, vertKey, f):     
    s = g.getVertex(vertKey)
    s.setDistance(0)
    s.setPred(None)
    s.setColor('gray')
    Q = Queue()
    Q.enqueue(s)
    while (Q.size() > 0):
        w = Q.dequeue()
        for v in w.getAdj():
            if (v.getColor() == 'white'):
                v.setColor('gray')
                f(w, v)
                # v.setDistance( w.getDistance() + 1 )
                # v.setPred(w)
                Q.enqueue(v)
        # w.setColor('black')

def findPaths(g, source):           # source is a key
    def buildPath(from_v, to_v):
        to_v.setDistance(from_v.getDistance() + 1)
        to_v.setPred(from_v)
    bfs(g, source, buildPath)

def shortestPath(g, source, dest):  # source and dest are keys
    class GotIt (Exception):
        pass
    def eureka(from_v, to_v):       # from_v and to_v are nodes
        to_v.setDistance(from_v.getDistance() + 1)
        to_v.setPred(from_v)
        if to_v.id == dest:
            raise GotIt
    try:
        bfs(g, source, eureka)
    except GotIt:
        n = g.getVertex(dest)
        s = g.getVertex(source)
        stk = [n]
        while n != s:
            n = n.getPred()
            stk.append(n)
        while len(stk) > 0:
            print stk.pop().id,
        print ""

