Monday, March 21, 2011

Graphs and their applications

In this series of article I'll show you how to represent Graphs
and searching in graphs. We'll be implementing Breadth First Search (BFS), Depth First Search (DFS), Greedy Best First Search and A Star (A*) Search.. Before actually diving into coding these search strategies we'll first build a Graph itself.
As you might know, a graph consists of nodes and arcs that connect the nodes. A graph is very similar to a tree but in graph same node can be reached from multiple paths. Below is a simple representation of a graph.

Ok now we know that a Graph has


  • Nodes



  • Arcs


  • Lets start coding! I'll use Visual Basic.NET as programming language but dont worry if you dont know VB. I'll explain every line of code so you'll have no problem writing it in any other language.
    First we'll build a class for an arc or edge (what ever you might call it)

    Public Class arc
     Dim _arc as Boolean
     Dim _weight as Integer
     Public Sub New()
      _arc = False
      _weight = -1
     End Sub
    
     Public Property adj
            Get
                adj = _adj
            End Get
            Set(ByVal value)
                _adj = value
            End Set
        End Property
    
     Public Property weight
      Get
       weight = _weight
      End Get
      Set(ByVal value)
       _weight = value
      End Set
     End Property
    
    End Class
      
    What happened here? I made a class named arc with private variable called _arc, _weight. _arc variable indicates whether the arc between two nodes is present or not and _weight to store weight for a weighted graph. In the constructor I initialized _adj to False. The Property thing just Gets or Sets the value for this variable. In C++ or Java you can do it by making a public function which can alter or retrieve the value of _adj and _weight variable.
    We have made an arc. Now lets make a class for node.


    Public Class node
      Dim _name As String
        Dim _pathCost As Integer
        Dim _heuristic As Integer
        Dim _eval As Integer ' Result of Evaluation function
       
        Public Sub New()
            _name = ""
            _pathCost = -1
            _heuristic = -1
            _eval = -1
        End Sub
        Public Property name
            Get
                name = _name
            End Get
            Set(ByVal value)
                _name = value
            End Set
        End Property
    
        Public Property pathCost
            Get
                pathCost = _pathCost
            End Get
            Set(ByVal value)
                _pathCost = value
            End Set
        End Property
    
        Public Property heuristic
            Get
                heuristic = _heuristic
            End Get
            Set(ByVal value)
                _heuristic = value
            End Set
        End Property
    
        Public Property evaluationFunction
            Get
                evaluationFunction = _eval
            End Get
            Set(ByVal value)
                _eval = value
            End Set
        End Property
    
    End Class
      
    A node will have some information attached with it like its name, cost to reach this node, etc etc. For BFS and DFS you actually wont need any of the variables defined in this class! We'll use variables like _pathCost, _heuristic and _eval in Greedy Best First Search and A* Search. Now lets look at these variables.

    _name: This variable holds the name for a node

    _pathCost: This variable holds the cost to reach this node from the start node (used in A*)

    _heuristic: This variable holds well... heuristic that will guide the search algorithm

    _eval: This variable holds the value after applying evaluation function to the node
    Building blocks for a graph are finished! Now lets make a Graph class.
    Public Class graph
        
        Private _numberOfNodes As Integer
        Private _nodes() As node
        Private _arcs(,) As arc
        Private _fringe, _visited As Queue
        Private _stack As Stack
    
        Public Sub New(ByVal numberofNodes As Integer)
            _fringe = New Queue
            _visited = New Queue
            _stack = New Stack
            _numberOfNodes = numberofNodes
    
            ReDim _nodes(numberofNodes)
            ReDim _arcs(numberofNodes, numberofNodes)
            
    
            For i As Integer = 0 To numberofNodes - 1
                _nodes(i) = New node
            Next
    
            For i As Integer = 0 To numberofNodes - 1
                For j As Integer = 0 To numberofNodes - 1
                    _arcs(i, j) = New arc
                Next
            Next
    
        End Sub
      

    A graph consists of nodes and arcs. So we have _numberOfNodes to store number of nodes in the graph, _nodes() which is an 1-D array of nodes, _arcs(,) which is a 2-D array of arc, _fringe, _visited and _stack are used in various search strategies which I'll discuss later.

    The constructor of this class requires numberofNodes as
    its parameter which is then used to create new instances of nodes and arcs.
    Now we'll add two functions to this class... well make that three, isAdjacent(i,j), addArc(i,j) and removeArc(i,j). isAdjacent(i,j) function determines whether two nodes i and j are adjacent or not and addArc(i,j) function simply adds and arc between nodes i and j.
    Public Function isAdjacent(ByVal i As Integer, ByVal j As Integer) As Boolean
            If _arcs(i, j).adj = True Then
                Return True
            Else
                Return False
            End If
        End Function
    
        Public Sub addArc(ByVal i As Integer, ByVal j As Integer)
            _arcs(i, j).adj = True        
        End Sub
        
         Public Sub removeArc(ByVal i As Integer, ByVal j As Integer)
            _arcs(i, j).adj = False
         End Sub
      


    Now, having made all of this, how to use it?


    Public Class Form1
        Private numNodes As Integer
        Dim g As graph
    
    On Form load event i.e Form1_Load(...)
    numNodes = InputBox("How many nodes?", , "5")
    g = New graph(numNodes)
    
    Then for numNodes times, take input for node name and other variables.

    Add arcs using addArc() function and finally search.

    No comments:

    Recent Posts