Find indegree and outdegree of a directed graph in vb.net
Vb program for Find indegree and outdegree of a directed graph. Here problem description and explanation.
' Include namespace system
Imports System
' Vb.net Program for
' Show degree of vertex in directed graph
Public Class AjlistNode
' Vertices node key
Public id As Integer
Public [next] As AjlistNode
Public Sub New(ByVal id As Integer)
' Set value of node key
Me.id = id
Me.next = Nothing
End Sub
End Class
Public Class Vertices
Public data As Integer
Public [next] As AjlistNode
Public last As AjlistNode
Public Sub New(ByVal data As Integer)
Me.data = data
Me.next = Nothing
Me.last = Nothing
End Sub
End Class
public Class Graph
' Number of Vertices
Public size As Integer
Public node As Vertices()
Public Sub New(ByVal size As Integer)
' Set value
Me.size = size
Me.node = New Vertices(size){}
Me.setData()
End Sub
' Set initial node value
Public Sub setData()
if (Me.size <= 0) Then
Console.WriteLine(vbLf &"Empty Graph")
Else
Dim index As Integer = 0
While index < Me.size
' Set initial node value
Me.node(index) = New Vertices(index)
index += 1
End While
End IF
End Sub
' Handling the request of adding new edge
Public Sub addEdge(ByVal start As Integer, ByVal last As Integer)
if (start >= 0 AndAlso start < Me.size AndAlso
last >= 0 AndAlso last < Me.size) Then
' Safe connection
Dim edge As AjlistNode = New AjlistNode(last)
if (Me.node(start).[next] Is Nothing) Then
Me.node(start).[next] = edge
Else
' Add edge at the end
Me.node(start).last.[next] = edge
End IF
' Get last edge
Me.node(start).last = edge
Else
' When invalid nodes
Console.WriteLine(vbLf &"Here Something Wrong")
End IF
End Sub
Public Sub printGraph()
if (Me.size > 0) Then
' Print graph ajlist Node value
Dim index As Integer = 0
While index < Me.size
Console.Write(vbLf &"Adjacency list of vertex " + index.ToString() + " : ")
Dim temp As AjlistNode = Me.node(index).[next]
while (temp IsNot Nothing)
' Display graph node
Console.Write(" " + Me.node(temp.id).data.ToString())
' Visit to next edge
temp = temp.[next]
End While
index += 1
End While
End If
End Sub
' Find indegree and outdegree of
' each nodes of a given graph
Public Sub findDegree(ByVal indegree As Integer(),
ByVal outdegree As Integer())
Dim temp As AjlistNode = Nothing
Dim length As Integer = 0
Dim i As Integer = 0
While i < Me.size
temp = Me.node(i).[next]
length = 0
while (temp IsNot Nothing)
' Update indegree
indegree(temp.id) += 1
temp = temp.[next]
length += 1
End While
' Set outdegree value
outdegree(i) = length
i += 1
End While
End Sub
Public Sub showDegree()
if (Me.node IsNot Nothing) Then
Dim indegree As Integer() = New Integer(Me.size){}
Dim outdegree As Integer() = New Integer(Me.size){}
' Set zero degree
Dim i As Integer = 0
While i < Me.size
indegree(i) = 0
outdegree(i) = 0
i += 1
End While
' Find degree
Me.findDegree(indegree, outdegree)
Console.WriteLine(""& vbLf &"")
' Display result
i = 0
While i < Me.size
Console.WriteLine("Node [" + i.ToString() +
"] indegree [" + indegree(i).ToString() +
"] outdegree [" + outdegree(i).ToString() + "]")
i += 1
End While
Else
Console.Write("Empty Graph")
End IF
End Sub
Public Shared Sub Main(ByVal args As String())
' 6 implies the number of nodes in graph
Dim g As Graph = New Graph(6)
' Connected two node with Edges
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(0, 5)
g.addEdge(2, 3)
g.addEdge(3, 1)
g.addEdge(4, 0)
g.addEdge(4, 1)
g.addEdge(5, 0)
g.addEdge(5, 2)
g.printGraph()
' Test
g.showDegree()
End Sub
End Class
Output
Adjacency list of vertex 0 : 1 2 5
Adjacency list of vertex 1 :
Adjacency list of vertex 2 : 3
Adjacency list of vertex 3 : 1
Adjacency list of vertex 4 : 0 1
Adjacency list of vertex 5 : 0 2
Node [0] indegree [2] outdegree [3]
Node [1] indegree [3] outdegree [0]
Node [2] indegree [2] outdegree [1]
Node [3] indegree [1] outdegree [1]
Node [4] indegree [0] outdegree [2]
Node [5] indegree [1] outdegree [2]
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment