Module Module1
    ' Chapter 47
    ' This program can be a depth first search if using a stack.
    ' This program can be a breadth first search if using a queue.
    '
    ' You can modify it to see the difference.
    '
    ' Look for the variable 'theADT'.  Each time it is used, you will find two different
    ' lines of code.  One should always be commented out.  One is for a queue and one is
    ' for a stack.  You'll get a compile error if you get them overlapped because the
    ' queue and the stack have different method calls.

    Class NodeClass
        ' This class defines the items associated with each node of the graph
        ' The graph, itself, will be stored as a dictionary with a key and this structure as data
        Public theNeighbours As List(Of String)
        Public theColour As String

        Public Sub New(ByVal inColour As String, ByVal inNeighbours As List(Of String))
            ' Constructor
            theColour = inColour
            theNeighbours = inNeighbours
        End Sub
    End Class
    ' Loads the global dictionary with data
    Sub loadGraphData(ByRef inGraph As Dictionary(Of String, NodeClass))

        Dim newNeighbours As List(Of String)
        Dim newNode As NodeClass

        newNeighbours = New List(Of String) From {"B", "C"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("A", newNode)
        newNeighbours = New List(Of String) From {"A", "D", "E"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("B", newNode)
        newNeighbours = New List(Of String) From {"A", "F", "G"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("C", newNode)
        newNeighbours = New List(Of String) From {"B"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("D", newNode)
        newNeighbours = New List(Of String) From {"B"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("E", newNode)
        newNeighbours = New List(Of String) From {"C"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("F", newNode)
        newNeighbours = New List(Of String) From {"C", "H"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("G", newNode)
        newNeighbours = New List(Of String) From {"G", "I", "J"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("H", newNode)
        newNeighbours = New List(Of String) From {"H"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("I", newNode)
        newNeighbours = New List(Of String) From {"H", "K", "L"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("J", newNode)
        newNeighbours = New List(Of String) From {"J"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("K", newNode)
        newNeighbours = New List(Of String) From {"J"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("L", newNode)

    End Sub
    Function search(ByVal inNode As String, ByRef inGraph As Dictionary(Of String, NodeClass)) As List(Of String)

        ' Abstract Data Structure to support either a depth first (stack) or a breadth first (queue) search
        ' Dim theADT As New Queue(Of String)
        Dim theADT As New Stack(Of String)

        Dim visitedNodes As New List(Of String)
        Dim currentNode As String

        theADT.Push(inNode)           ' A node to be examined
        ' theADT.Enqueue(inNode)        ' A node to be examined

        ' Unitl all the nodes have been looked at
        While (theADT.Count > 0)
            ' Print the contents of the current queue
            Console.WriteLine(String.Format("ADT is now: {0}", String.Join(",", theADT)))
            Console.WriteLine("")

            ' currentNode = theADT.Dequeue()
            currentNode = theADT.Pop()
            Console.WriteLine(String.Format("Visiting {0} - setting it to black", currentNode))

            ' In order to change the colour from white to black, we have to point to the
            ' item field in the dictionary for the required node.  Then, point to the
            ' colour field.  This can be updated directly because we're using the 
            ' pass parameters by Reference, which means we're dealing directly with
            ' the addresses in memory, not copies of the memory content
            inGraph.Item(currentNode).theColour = "black"

            ' Insert this node into the visited list
            visitedNodes.Add(currentNode)

            ' Now, we have to explore each of this node's neighbours
            For Each node In inGraph.Item(currentNode).theNeighbours
                Console.WriteLine(String.Format("    checking neighbour {0} - colour is {1}", node, inGraph.Item(currentNode).theColour))

                If (inGraph.Item(node).theColour = "white") Then
                    Console.WriteLine(String.Format("    appending neighbour {0} to queue - setting it to grey", node))
                    ' theADT.Enqueue(node)
                    theADT.Push(node)
                    inGraph.Item(node).theColour = "grey"
                End If
            Next
        End While
        Return (visitedNodes)
    End Function
    Sub displayGraph(ByVal inGraph As Dictionary(Of String, NodeClass))

        Dim outline As String
        Dim nodeName As String
        Dim theInfo As NodeClass

        For Each entry As KeyValuePair(Of String, NodeClass) In inGraph
            nodeName = entry.Key
            theInfo = entry.Value

            outline = String.Format("Node: {0}  Colour: {1}  Neighbours: {2}", nodeName, theInfo.theColour, String.Join(",", theInfo.theNeighbours))
            Console.WriteLine(outline)
        Next

    End Sub
    Sub Main()
        Dim eat As String
        Dim theGraph As New Dictionary(Of String, NodeClass)
        Dim visitedList As List(Of String)


        loadGraphData(theGraph)
        Console.WriteLine("Original Graph Definition")
        displayGraph(theGraph)

        visitedList = search("A", theGraph)
        Console.WriteLine("Nodes visited in this order: {0}", String.Join(",", visitedList))

        Console.WriteLine("Any key to continue")
        eat = Console.ReadLine()
    End Sub

End Module