'''
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.
'''

from pyliststack import Stack

city_names = ['A', 'B', 'C', 'D', 'E', 'F']
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')
print(list(dfs_paths(graph, 'A', 'F'))) # ['A', 'C', 'F']

print('from D to F')
print(list(dfs_paths(graph, 'D', 'F'))) # ['D', 'B', 'E', 'F']

print('from D to C')
print(list(dfs_paths(graph, 'D', 'C'))) # ['D', 'B', 'E', 'F', 'C']