'''
The exercise is based on the following website
http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
2017-10-04
Xiannong Meng
Revisions include
1. Used our own queue so students can practice with queues.
2. Added some functions such as unvisit_all(), mark_visited() and variables
   such as city_names, visited to be as close to our original stack
   solution as possible.

Revised: 
2020-02-29
Xiannong Meng
Added a case in which no path exists.
'''

from pylistqueue import Queue

city_names = ['A', 'B', 'C', 'D', 'E', 'F', 'G'] # 'G' has no connections
graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}

def unvisit_all():
    """Mark all cities unvisited"""
    visited = {}
    for i in range(len(city_names)):
        visited[city_names[i]] = False
    return visited

def mark_visited(visited, which):
    """Mark a particular city visited"""
    visited[which] = True
    
def bfs_paths(graph, start, goal):
    """Breadth first search using a queue"""

    visited = unvisit_all()
    
    queue = Queue()
    queue.enqueue((start, [start]))    # put both the city and path on queue
    mark_visited(visited, start)

    while queue.is_empty() == False:
        (vertex, path) = queue.dequeue()
        for next in graph[vertex]:     # try each city that is connected
            if visited[next] == False:
                mark_visited(visited, next)
                if next == goal:
                    return path + [next]
                else:
                    queue.enqueue((next, path + [next]))

print('from A to F')
paths = bfs_paths(graph, 'A', 'F')
if paths is None:
    print('There is no path from "A" to "F"')
else:
    print(list(paths)) # ['A', 'C', 'F']

print('from D to F')
paths = bfs_paths(graph, 'D', 'F')
if paths is None:
    print('There is no path from "D" to "F"')
else:
    print(list(paths)) # ['D', 'B', 'E', 'F']

print('from D to C')
paths = bfs_paths(graph, 'D', 'C')
if paths is None:
    print('There is no path from "D" to "C"')
else:
    print(list(paths)) # ['D', 'B', 'A', 'C']

print('from A to G')
paths = bfs_paths(graph, 'A', 'G')
if paths is None:
    print('There is no path from "A" to "G"')
else:
    print(list(paths)) # should be None