Depth of node (how to make the looping?)

[Meeko]

Hello,

I've a connection table in access database as below:

ID FROM_NODE TO_NODE
---------------------
1 10 11
2 10 12
3 11 10
4 11 13
5 11 14
6 12 10
7 12 13
8 12 15
9 13 12
10 13 14
11 13 16
12 14 13
13 14 11
14 14 17
15 15 12
16 15 16
17 16 15
18 16 13
19 16 17
20 17 16
21 17 14

I would like to calculate the depth of each node relative to a start node,
say the start node is 15, then the depth table is show as below, node 12 and 16 is directly linked to node 15, so the depth is 1. Node 10, 13, 17 are 2 steps from node 15, so the depth is 2, and so on.

ID NODE DEPTH
-------------------------
1 10 2
2 11 3
3 12 1
4 13 2
5 14 3
6 15 0
7 16 1
8 17 2

How could I make the looping in vb so to obtain the depth table?
I'm quite confused in handling loops in loops.
Thanks for help

[leinad31]

Easiest would be to add the nodes to a treeview or a nodes collection following the parent child relationship. The "depth" would simply be iterating until Node.Parent Is Nothing

Set Node = treeview.nodes(index)  'at which node to start
Do Until (Node.Parent Is Nothing)
   depth = depth + 1
   Set Node = Node.Parent
Loop

[Logophobic]

I'm not familiar with graph theory (I know what it is, but that's about it) but I can give a visual reference to avoid the confusion of TreeView nodes and the nodes of a graph. The numbers are the nodes, the lines between them are the connections. Meeko's post seems to imply that these are one-way connections, as the connection from 13 to 11 is missing. The depth, or distance, from one node to another is very obvious to humans. Computers have a bit more trouble.

[leinad31]

For such cases, the depth depends on which branch or path your currently analyzing. From 15 to 10 could have been 6 deep (15-16-17-14-13-12-10). So you will also have to consider all path possibilities.

[Ellis Dee]

The depth, or distance, from one node to another is very obvious to humans. Computers have a bit more trouble.

This actually isn't true; it's almost as easy for computers as it is for humans. It can be done fairly simply with a recursive function. [Remainder of paragraph cut, though it's still quoted in next post.]

Anyway, to the OP, here's a complete and functional example to accomplish what you're looking for. It's just a very basic framework, so no doubt you'll have to do some extensive adaptation to it, but the fundamental process is there. (Note that I completely ignored the ID field, since I had no need for it.)

EDIT: I enhanced the core function with extra comments and variables for increased readability.

Option Explicit

Public Const MIN_NODE = 10
Public Const MAX_NODE = 17

Public Type NodeType
    Node As Long
    Neighbors() As Long
    Depth(MIN_NODE To MAX_NODE) As Long
End Type

Public nod(MIN_NODE To MAX_NODE) As NodeType

Sub Main()
    AddNeighbor 10, 11
    AddNeighbor 10, 12
    AddNeighbor 11, 10
    AddNeighbor 11, 13
    AddNeighbor 11, 14
    AddNeighbor 12, 10
    AddNeighbor 12, 13
    AddNeighbor 12, 15
    AddNeighbor 13, 12
    AddNeighbor 13, 14
    AddNeighbor 13, 16
    AddNeighbor 14, 13
    AddNeighbor 14, 11
    AddNeighbor 14, 17
    AddNeighbor 15, 12
    AddNeighbor 15, 16
    AddNeighbor 16, 15
    AddNeighbor 16, 13
    AddNeighbor 16, 17
    AddNeighbor 17, 16
    AddNeighbor 17, 14
    ' Create complete depth charts for all nodes
    CalculateAllDepths
    ' Display results for a random node in the debug window
    Randomize Timer
    ShowResults Int((MAX_NODE - MIN_NODE + 1) * Rnd + MIN_NODE)
End Sub

Private Sub AddNeighbor(plngNode As Long, plngNeighbor As Long)
    Dim i As Long
    
    With nod(plngNode)
        If .Node = 0 Then
            i = 1
            ReDim .Neighbors(1 To i)
            .Node = plngNode
        Else
            i = UBound(.Neighbors) + 1
            ReDim Preserve .Neighbors(1 To i)
        End If
        .Neighbors(i) = plngNeighbor
    End With
End Sub

Private Sub CalculateAllDepths()
    Dim i As Long
    
    ' Create the depth chart for all nodes
    For i = MIN_NODE To MAX_NODE
        FindDepths i, i, 0
    Next
End Sub

' This is the main entry point to determine
' the depth chart for a given node. This
' function will exhaustively search all possible
' pathways, finding the shortest pathways
' between the root node and all others.
' Given a root node to generate a depth chart
' for, the first call should be in the form:
' FindDepths MyNode, MyNode, 0
Private Sub FindDepths(plngRoot As Long, plngNode As Long, ByVal plngLevel As Long)
    Dim i As Long
    Dim iMax As Long
    Dim lngNext As Long
    Dim lngDepth As Long
    
    ' Entering this function, we have the shortest
    ' known path so far between the root node
    ' and the node we're currently checking.
    nod(plngRoot).Depth(plngNode) = plngLevel
    ' Now check the neighbors, adding a level
    With nod(plngNode)
        iMax = UBound(.Neighbors)
        For i = 1 To iMax
            ' Grab the next node to a variable for readability
            lngNext = .Neighbors(i)
            ' Also grab the shortest path we've found so far between
            ' the next neighbor and the root node
            lngDepth = nod(plngRoot).Depth(lngNext)
            ' Skip this neighbor if it's the root or we already found a shorter path
            ' but force a recursion if we haven't checked this node at all yet
            If lngNext <> plngRoot And (lngDepth = 0 Or lngDepth > plngLevel + 1) Then
                ' Untried path, so recurse it
                FindDepths plngRoot, lngNext, plngLevel + 1
            End If
        Next
    End With
End Sub

Private Sub ShowResults(plngNode As Long)
    Dim i As Long
    Dim iMax As Long
    Dim strDisplay As String
    
    Debug.Print "Node " & plngNode
    With nod(plngNode)
        iMax = UBound(.Neighbors)
        For i = 1 To iMax
            strDisplay = strDisplay & "," & .Neighbors(i)
        Next
        Debug.Print "Neighbors: " & Mid(strDisplay, 2)
        Debug.Print "Depth Chart:"
        For i = MIN_NODE To MAX_NODE
            Debug.Print "Node: " & i & " is at relative depth of " & .Depth(i)
        Next
    End With
End Sub

[Ellis Dee]

This one here, for example, generates a complete depth chart for any given node in only 8 lines of code. (Not counting comments, variable declarations, and the WITH...END WITH statement, all of which are technically optional.)

heh, to needlessly drive this point home, here's the same function in its most compact form:

Private Sub FindDepths(plngRoot As Long, plngNode As Long, ByVal plngLevel As Long)
    Dim i As Long
    
    nod(plngRoot).Depth(plngNode) = plngLevel
    For i = 1 To UBound(nod(plngNode).Neighbors)
        If nod(plngNode).Neighbors(i) <> plngRoot And (nod(plngRoot).Depth(nod(plngNode).Neighbors(i)) = 0 Or nod(plngRoot).Depth(nod(plngNode).Neighbors(i)) > plngLevel + 1) Then FindDepths plngRoot, nod(plngNode).Neighbors(i), plngLevel + 1
    Next
End Sub

Impressive how much power you can pack into just a few lines of code, isn't it?

This is a pretty good example of why exactly it is better to create longer code with more variables even when they aren't strictly necessary. The first version I posted isn't going to win any awards for readability/maintainability, but this compact version would truly be a nightmare to have to debug.

[Logophobic]

I didn't mean to imply that it was particularly difficult. Just not as simple as the intuitive nature of our brains.

[Ellis Dee]

I didn't mean to imply that it was particularly difficult. Just not as simple as the intuitive nature of our brains.

Agreed. The drawback is that our intuitive nature lends itself to error, whereas a computer -- given a correct set of instructions -- will get it right every time.

It just occured to me that I completely ignored the one-way relationship, but luckily the logic is sound enough to catch it properly. It shows one step from 11 to 13, and two steps from 13 to 11.

[Meeko]

Thanks all for reply.

Ellis, Logophobic, you're right, it is one-way relation and doesn't need to consider all path possible, only the shortest one is considered.

Really thanks Ellis for showing me how it could be done, thanks for the comments also. It works in my case and it has provided a fundamental to expand my project.