Finding path between two nodes in a directed graph using BFS.

find_path.py

from Queue import Queue

def find_path(E, V, n1, n2):
    """Find path between n1,n2 of a directed graph"""
    for n in E:
        n.from_ = None
    q = Queue()
    q.put(n1)
    found = False
    while not q.empty():
        cur = q.get()
        if cur == n2:
            found = True
            break
        for n in V[cur]:
            if n.from_ == None:
                n.from_ = cur
                q.put(n)
    if not found: return None
    p = []
    cur = n2
    while cur != None:
        p.insert(0, cur)
        cur = cur.from_
    return p

class Node:pass

def test_find_path():
    n1 = Node()
    n2 = Node()
    n3 = Node()
    n4 = Node()
    n5 = Node()
    n6 = Node()
    n7 = Node()
    n8 = Node()
    E = [n1, n2, n3, n4, n5, n6, n7, n8]
    V = {n1:[n2,n3,n4],
         n2:[n5],
         n3:[n6],
         n4:[n5,n6,n8],
         n5:[n7],
         n6:[n8],
         n7:[],
         n8:[n7]}

    assert [n1,n4] == find_path(E,V,n1,n4)
    assert [n1,n4,n8] == find_path(E,V,n1,n8)
    assert None == find_path(E,V,n8, n1)