#Chapter 47 dfs iterative version using a stack
#An iterative version of depth first search

# you should change the word 'queue' to 'stack' throughout
# and compare this code with the program Chapter 47 dfs...

GRAPH = {
    'A': {'colour': 'white', 'neighbours':['B','C']},
    'B': {'colour': 'white', 'neighbours':['A','D','E']},
    'C': {'colour': 'white', 'neighbours':['A','F','G']},
    'D': {'colour': 'white', 'neighbours':['B']},
    'E': {'colour': 'white', 'neighbours':['B']},
    'F': {'colour': 'white', 'neighbours':['C']},
    'G': {'colour': 'white', 'neighbours':['C','H']},
    'H': {'colour': 'white', 'neighbours':['G','I','J']},
    'I': {'colour': 'white', 'neighbours':['H']},
    'J': {'colour': 'white', 'neighbours':['H','K','L']},
    'K': {'colour': 'white', 'neighbours':['J']},
    'L': {'colour': 'white', 'neighbours':['J']}    
    }

def dfs(vertex, graph):
    g = graph
    queue = []
    visitedNodes =[]
    queue.append(vertex)
    while len(queue) > 0:
        print('Queue is now', queue)
        print()
# the next statement is the only one that differs from the bfs algorithm
# it removes from the end of the queue instead of the beginning
# it is using a stack, not a queue
# this turns it into a depth first rather than a breadth first search
# it traverses depth first from right to left
# you should change the word 'queue' to 'stack' throughout ...
        currentNode = queue.pop()      
        print('Visiting', currentNode, '- setting it to black')
        g[currentNode]['colour'] = 'black'
        visitedNodes.append(currentNode)
        for n in g[currentNode]['neighbours']:
            print('  checking neighbour', n, '- colour is', g[currentNode]['colour'])
            if g[n]['colour'] is 'white':
                print('  appending neighbour', n, 'to queue and setting it to grey')
                queue.append(n)
                g[n]['colour'] = 'grey'
            # end if
        # end for
    # end while
    return visitedNodes
# end def bfs


print('Depth first traversal of GRAPH starting at A','\n')
visited = dfs('A', GRAPH)
print('List of nodes visited: ',visited)