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

# you should change the word 'supporting_adt' 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
    supporting_adt = []
    visitedNodes =[]
    supporting_adt.append(vertex)
    while len(supporting_adt) > 0:
        print('Queue or stack is now', supporting_adt)
        print()
# using a stack for the ADT results in a depth first traversal
# it removes from the end of the ADT instead of the beginning
# this turns it into a depth first rather than a breadth first search
# it traverses depth first from right to left
# Using a queue for the supporting ADT results in a breadth first traversal
        currentNode = supporting_adt.pop() #for depth first
#Using a stack for the supporting ADT results in a depth first traversal
#        currentNode = supporting_adt.pop(0) #for breadth first
#       currentNode = supporting_adt.pop #for depth first
        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 supporting_adt and setting it to grey')
                supporting_adt.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)