In this exercise you will write code to construct an undirected, weighted graph.  You will take an object oriented approach, so this will involve a class called Graph and a separate class Vertex.

Make sure you understand

Within the Graph class the connectivity of the graph will be stored in the form of an adjacency matrix.  This is the graph you will test your code with looks like, along with the corresponding adjacency matrix  (although your code should work for any graph):

Each square in the grid can be used to represent an edge in the graph.  An edge connects two vertices together.  The x co-ordinate represents one of these vertices, and the y co-ordinate represents the other.  The weight of the edge between two vertices is therefore stored at the intersection of x and y.  Make sure you are clear about this before you proceed.

Begin by writing a Vertex class as follows:

Public Class Vertex
    Public Value As String    

    Public Sub New(ByVal Value As String)
        Me.Value = Value
    End Sub

End Class

Make sure you understand

Notice that the Vertex class has one public property with the name Value, which has been implemented as a public variable (rather than a property procedure, for simplicity).  This is the payload of the vertex.  The payload could be a location name, a web page on the Internet, or a friend in a social network, depending on what the graph will represent.  Whenever a vertex is added to the graph (that is, when an instance of the Vertex class is created), a value is passed as a parameter to the constructor of the Vertex and this is assigned to the Value property.

Now write a Graph class as follows:

Public Class Graph
  
    Private vertices(4) As Vertex
    Private adjacencyMatrix(4, 4) As Double
    Private iNumberOfVertices As Integer
   
    Public Sub AddVertex(ByVal value As String)
        vertices(iNumberOfVertices) = New Vertex(value)
        iNumberOfVertices += 1
    End Sub

    Public Sub AddEdge(ByVal StartVertex As Integer, ByVal EndVertex As Integer, Weight As Double)
        adjacencyMatrix(StartVertex, EndVertex) = Weight
        adjacencyMatrix(EndVertex, StartVertex) = Weight   
    End Sub

End Class

Make sure you understand

The Graph class maintains three private variables.  Perhaps the most important of these is a two dimensional array of integers called adjacencyMatrix; ultimately, this is how the graph is represented.  The two dimensional array has elements numbered from 0 to 4 in each dimension, so it is effectively a 5 x 5 grid.  This means it will only cater for graphs with up to 5 nodes.  The Graph class also maintains an array of Vertex objects called vertices, and an integer variable to keep count of the number of vertices.

The graph also includes two methods, AddVertex and AddEdge.

When AddVertex is called, it is passed a value as a parameter. This is then passed in turn to the constructor of the Vertex class, so a Vertex object is created (in this implementation, it is the responsibility of the Graph class to create a new vertex).  As it is created, the new Vertex object is put into the vertices array, at a position given by the integer variable iNumberOfVertices.  The variable iNumberOfVertices is then incremented in readiness for the next vertex.  This means that each vertex can be identified by an integer value.

When AddEdge is called, it is passed the integer identifiers of two different vertices, namely the starting vertex and ending vertex of an edge.  It is also passed a weight.  These parameters are used to store information about an edge in the adjacency matrix. Because this code is designed to work with undirected graphs only, two edges are added to the adjacency matrix at the same time.

Test your Graph class with the following code.  You will need to place a button on the form.  Notice that the graph object g is created with form level scope.  This will allow other programs launched from the form to work with the graph.

    Dim g As New Graph
    
    Private Sub btnMakeGraph_Click(sender As Object, e As EventArgs) Handles btnMakeGraph.Click

        g.AddVertex("A")
        g.AddVertex("B")
        g.AddVertex("C")
        g.AddVertex("D")
        g.AddVertex("E")
        g.AddEdge(0, 1, 6)
        g.AddEdge(0, 3, 1)
        g.AddEdge(1, 0, 6)
        g.AddEdge(1, 2, 5)
        g.AddEdge(1, 3, 2)
        g.AddEdge(1, 4, 2)
        g.AddEdge(2, 1, 5)
        g.AddEdge(2, 4, 5)
        g.AddEdge(3, 0, 1)
        g.AddEdge(3, 1, 2)
        g.AddEdge(3, 4, 1)
        g.AddEdge(4, 1, 2)
        g.AddEdge(4, 2, 5)
        g.AddEdge(4, 3, 1)

        MsgBox("Graph Created")

    End Sub

Enhancing the graph

Write a method, as a procedure, of your Graph class to display the payload (the value) of a vertex in a message box when the method is passed the integer identifier of any vertex.  Call this method from a button on your form.

Write a method, as a function, of your Graph class to return the adjacency matrix array. Call this method from a button on your form, then write code to scan the array and display it as shown below:

Write a method of your Graph class which when called allows you to specify a particular vertex by its identifier, and returns the identifiers of its neighbours (that is, the vertices that it shares an edge with).

Your code needs to work for a graph with any number of nodes.  Write a constructor in your graph class that accepts an integer parameter to specify the maximum number of nodes the graph can contain.  Change the array declarations in the Graph class to make the arrays dynamic, and use the constructor’s parameter value to dimension the arrays.  Make any other necessary adjustments to your code to make this modification work properly.