#Tyler Moore
#Code for traverse.pdf lecture CS 2123
#Last Modified 2016-09-08
#Much code writte by/adapted from Magnus Hetland

#example undirected graph
N = {
    'a':['b', 'c', 'd', 'e', 'f'],    # a
    'b': ['c', 'e'],             # b
    'c': ['d'],                # c
    'd': ['e'],                # d
    'e': ['f'],                # e
    'f': ['c', 'g', 'h'],          # f
    'g': ['f', 'h'],             # g
    'h': ['f', 'g']              # h
}

#smaller graph
N2 = {
    'a': ['b', 'c'],
    'b': ['d'],
    'c': ['e', 'f'],
    'd': ['e'],                # d
    'e': ['f', 'g'],                # e
    'f': ['d'],
    'g': ['f']
}


def rec_dfs(G, s, S=None):
    if S is None: S = set()# Initialize the history
    S.add(s)               # We've visited s
    for u in G[s]:         # Explore neighbors
        if u in S: continue# Already visited: Skip
        rec_dfs(G, u, S)   # New: Explore recursively
    return S # For testing

def iter_dfs(G, s):
    S, Q = set(), []       # Visited-set and queue
    Q.append(s)            # We plan on visiting s
    while Q:               # Planned nodes left?
        u = Q.pop()        # Get one
        if u in S: continue# Already visited? Skip it
        S.add(u)           # We've visited it now
        Q.extend(G[u])     # Schedule all neighbors
        yield u            # Report u as visited


from collections import deque
def iter_bfs(G, s):
    S, Q = set(), deque()  # Visited-set and queue
    Q.append(s)            # We plan on visiting s
    while Q:               # Planned nodes left?
        u = Q.popleft()        # Get one
        if u in S: continue# Already visited? Skip it
        S.add(u)           # We've visited it now
        Q.extend(G[u])     # Schedule all neighbors
        yield u            # Report u as visited


"""
>>> list(rec_dfs(N, 'a'))
['a', 'c', 'b', 'e', 'd', 'g', 'f', 'h']
>>> list(iter_dfs(N, 'a'))
['a', 'f', 'h', 'g', 'c', 'd', 'e', 'b']
>>> list(iter_bfs(N, 'a'))
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
"""

def bfs_parents(G, s):
    P, Q = {s: None}, deque([s])# Parents and FIFO queue
    while Q:
        u = Q.popleft()         # Constant-time for deque
        for v in G[u]:
            if v in P: continue # Already has parent
            P[v] = u            # Reached from u: u is parent
            Q.append(v)
    return P


P = bfs_parents(N2, 'a')
#>>> P
#{'a': None, 'c': 'a', 'b': 'a', 'e': 'c', 'd': 'b', 'g': 'e', 'f': 'c'}
 

#get shortest path from a to g
path = ['g']
u = 'g'
while P[u] != 'a':
    if P[u] is None: #give up if we find the root
        print('path not found')
        break
    path.append(P[u])
    u = P[u]
    
path.append(P[u]) #don't forget to add the source
path.reverse()    #reorder the path to start from url1
print(path)