'''
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 stack so students can practice with stacks.
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 pyliststack import Stack

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 dfs_paths(graph, start, goal):
    """Depth first search using a stack"""
    visited = unvisit_all()
    stack = Stack()
    
    stack.push((start, [start]))   # push both the city and the path to stack
    mark_visited(visited, start)

    while stack.is_empty() == False:
        (vertex, path) = stack.pop()
        for next in graph[vertex]:
            if visited[next] == False:
                mark_visited(visited, next)
                if next == goal:
                    return path + [next]
                else:
                    stack.push((next, path + [next]))

print('from A to F')
paths = dfs_paths(graph, 'A', 'F')
if paths is None:
    print('There is no path from "A" to "F"')
else:
    print(list(paths)) # ['A', 'B', 'E', 'F']. Even though 
                       # ['A', 'C', 'F'] is also a path, 'B' is checked first

print('from D to F')
paths = dfs_paths(graph, 'D', 'F')
if paths is None:
    print('There is no path from "D" to "F"')
else:
    print(list(paths)) # ['D', 'B', 'A', 'C', 'F']. Even though
                       # ['D', 'B', 'E', 'F'] is also a path, 
                       # 'A' is checked first

print('from D to C')
paths = dfs_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']. Even though
                       # ['D', 'B', 'E', 'F', 'C'] is also a path,
                       # 'A' is checked first

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