Depth of node (how to make the looping?)

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 :o

Re: Depth of node (how to make the looping?)

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

Code:

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

1 Attachment(s)

Re: Depth of node (how to make the looping?)

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.

Re: Depth of node (how to make the looping?)

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.

Re: Depth of node (how to make the looping?)

Quote:

Originally Posted by Logophobic

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.

Code:

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

Re: Depth of node (how to make the looping?)

Quote:

Originally Posted by 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:
vb Code:
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.

Re: Depth of node (how to make the looping?)

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

Re: Depth of node (how to make the looping?)

Quote:

Originally Posted by Logophobic

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.

Re: Depth of node (how to make the looping?)

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.:)