# Minimum weight cycle in an undirected weighted graph in vb.net

Vb program for Minimum weight cycle in an undirected weighted graph. Here problem description and explanation.

``````' Include namespace system
Imports System
'    Vb.net program for
'    Minimum weight cycle in an undirected graph

Public Class AjlistNode
'  Vertices node key
Public  id As Integer
Public  weight As Integer
Public  [next] As AjlistNode
Public Sub New(ByVal id As Integer, ByVal weight As Integer)
'  Set value of node key
Me.id = id
Me.weight = weight
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  result As Integer
Public  node As Vertices()
Public Sub New(ByVal size As Integer)
'  Set value
Me.size = size
Me.result = 0
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

Public Sub connection(ByVal start As Integer,
ByVal last As Integer,
ByVal weight As Integer)
'  Safe connection
Dim edge As AjlistNode = New AjlistNode(last, weight)
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
End Sub
'   Handling the request of adding new edge
Public Sub addEdge(ByVal start As Integer,
ByVal last As Integer,
ByVal weight As Integer)
if (start >= 0 AndAlso start < Me.size AndAlso
last >= 0 AndAlso last < Me.size) Then
'  Connect edge with weight
Me.connection(start, last, weight)
Me.connection(last, start, weight)
Else
'  When invalid nodes
Console.Write( vbLf &"Node missing ({0},{1})",start,last)
End IF
End Sub
Public Sub printGraph()
if (Me.size > 0) Then
'  Print graph ajlist
Dim index As Integer = 0
While index < Me.size
Console.Write( vbLf &"Adjacency list of vertex " +
index.ToString() + " :")
Dim edge As AjlistNode = Me.node(index).[next]
while (edge IsNot Nothing)
'  Display graph node value and weight
Console.Write("  " + Me.node(edge.id).data.ToString() +
"[" + edge.weight.ToString() + "]")
'  Visit to next edge
edge = edge.[next]
End While
index += 1
End While
End If
End Sub
Public Sub minimumCycle(ByVal start As Integer,
ByVal last As Integer,
ByVal visit As Boolean(),
ByVal sum As Integer, ByVal length As Integer)
if (start >= Me.size OrElse last >= Me.size OrElse
start < 0 OrElse last < 0 OrElse Me.size <= 0) Then
Return
End If
if (visit(start) = True) Then
'  Here length are indicate loop length
if (length > 2 AndAlso start = last AndAlso sum < Me.result) Then
'  Here length is indicate number of nodes
'  Because graph is undirected so we consider all cycle
'  Which contains more than 2 node
'  ---------------------
'  When find a new min weight cycle
Me.result = sum
End If
Return
End If
'  Here modified  the value of visited node
visit(start) = True
'  This is used to iterate nodes edges
Dim edge As AjlistNode = Me.node(start).[next]
while (edge IsNot Nothing)
'   Find solution using recursion
Me.minimumCycle(edge.id, last, visit,
sum + (edge.weight), length + 1)
'  Visit to next edge
edge = edge.[next]
End While
'  Reset the value of visited node status
visit(start) = False
End Sub
Public Sub minWeightCycle()
if (Me.size <= 0) Then
'  Empty graph
Return
End If
'  Auxiliary space which is used to store
'  Set initial visited node status
Dim visit As Boolean() = New Boolean(Me.size){}
Me.result = Integer.MaxValue
Dim i As Integer = 0
While i < Me.size
'  Check cycle of node i to i
'  Here initial cycle weight is zero
Me.minimumCycle(i, i, visit, 0, 0)
i += 1
End While
'  Display result
Console.WriteLine( vbLf &"Min weight cycle : " + Me.result.ToString())
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)
'  Connect node with an edge
'  First and second parameter indicate node
'  Last parameter is indicate weight
'  Print graph element
g.printGraph()
'  Test
g.minWeightCycle()
End Sub
End Class

``````

Output

``````Adjacency list of vertex 0 :  1[3]  3[-3]  4[7]  5[1]
Adjacency list of vertex 1 :  0[3]  2[11]  4[8]  5[0]
Adjacency list of vertex 2 :  1[11]  3[1]  5[4]
Adjacency list of vertex 3 :  0[-3]  2[1]  4[2]
Adjacency list of vertex 4 :  0[7]  1[8]  3[2]  5[8]
Adjacency list of vertex 5 :  0[1]  2[4]  4[8]  1[0]
Min weight cycle : 3``````

## Comment

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.