How to remove cycles or loops in graphs in visual basic?

Question

There are many articles in this site regarding my question. I have a matrix for example (10 x 10) which represents 10 nodes. The matrix called MyMat(9,9)

The rows of this matrix represent the source node (From Node) and the columns represents target node (To Node). It has 14 links which are randomly distributed. The non zero values represent the connections between nodes.

0 0 0 0 1 0 0 0 0 0 
0 0 0 1 0 0 0 0 1 0
0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 1 0 0 0
0 1 1 0 0 1 0 0 0 0

What I want is to prevent the loops (cycles) for each node in the system. For example: Node 1: No loop

Node 2: 2, 9, 7, 8, 10, 2. Here the loop exists because it started with 2 and finished with 2. What I want to prevent the loops in this network. This means that: MyMat(9,1) must be 0 Node 2: 2, 9, 7, 8, 10, 3, 2. This means MyMat(2,1) must be 0

Node 3: No loop

Node 4: 4, 7, 8, 4. This means that MyMat(7,3) must be 0

Node 5: 5, 8, 10, 6, 5. This means that MyMat(5,4) must be 0

Node 6: No Loop

Node 7: No Loop

Node 8: No Loop

Node 9: No Loop

Node 10: No Loop

4 connections were deleted from above matrix.

I have done this via a technique called Depth first search but it is very slow and burden the running time of my programme especially when I use 60 nodes and 100 connections!! Several programming examples can found if you Google it.

Is there an easier (quicker) way for doing this in visual basic or C#?

Answer 1

Depth first search should not take very long at all.

Procedure Depth_First_Clean(graph, v){
  color v grey
  for each edge (v,u){
     if u is grey 
       delete edge (v,u)
     else if u is white
       Depth_First_Clean(graph, u)
  }
  color v black
}

Procedure Clean_all(graph) {
  Mark all nodes white
  While there are white nodes left {
    v = a white node
    Depth_First_Clean(graph, v)
  }

This traverses each edge once, so should take almost no time in a graph with 100 edges.

OK from the example (I'm going to renumber the nodes to get rid of the confusing off by one problem in your example we have

  0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 1 0 0 0 0 0 
1 0 0 0 1 0 0 0 0 1 0
2 0 1 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 1 0 0 0
4 0 0 0 0 0 0 0 1 0 0
5 0 0 0 0 1 0 0 0 0 0
6 0 0 0 0 0 0 0 1 0 0
7 0 0 0 1 0 0 0 0 0 1
8 0 0 0 0 0 0 1 0 0 0
9 0 1 1 0 0 1 0 0 0 0

we mark all nodes white.  
We start with node 0
  mark node 0 grey
   traverse edge (0,4)
     mark node 4 grey
       traverse edge (4, 7)
         mark node 7 grey
           traverse edge (7, 3)
             mark node 3 grey 
               traverse edge (3,6)
                 mark node 6 grey
                   delete edge (6, 7) -- node 7 is grey break cycle 7 3 6 7
                 color node 6 black
             color node 3 black 
           traverse edge (7, 9)
             mark node 9 grey
               traverse edge (9, 1)
                 mark node 1 grey
                   skip edge (1,3) -- 3 is black there are no cycles through 3
                   traverse edge (1, 8)
                     mark node 8 grey
                       skip edge (8, 6)
                     color node 8 black
                 color node 1 black
               traverse edge (9, 2)   
                 color node 2 grey
                   skip edge (2,1)
                 color node 2 black
               traverse edge (9, 5)
                 color node 5 grey
                   delete edge (5, 4)
                 color node 5 black
             color node 9 black
         color node 7 black       
     color node 4 black       
 color node 0 black       
None of the remening nodes are white so we are done

Answer 2

I found the solution.

Public Function DFS3(ByVal V As Integer) As Integer

    TheList(V) = "G"
    For U = 0 To NumberofNodes - 1
        If Matt(V, U) > 0 Then
            If TheList(U) = "G" Then
                Matt(V, U) = 0
                RichTextBox1.AppendText("Link  " & V + 1 & " " & U + 1 & "   Deleted " & vbNewLine)
            ElseIf TheList(U) = "W" Then
                DFS3(U)
            End If
        End If
    Next U
    TheList(V) = "B"

End Function