All possible paths in decision tree

[Daniel]

I am trying to find all possible routes between two points on a tree using a top to bottom search only. The tree looks like this:

' 1
' / \
' 2 3
' / \
' 4 5 6
' / \ / \
' 7 8 9 10
' / \ \ / \ /
' 11 12 13 14 15
' \ \ / / \ / \
' 16 17 18 19 20 21
' / \ / \ / / / \
' 22 23 24 25 26 27 28
' \ / \ / / / \ / \ / \
' 29 30 31 32 33 34 35 36
' /\ / \ / \ / / / \ / \
' 37 38 39 40 41 42 43 44 45


The problem is that asking for all routes between 1 and 41 should give:

1-3-6-10-14-19-25-32-41
and
1-3-6-10-14-20-26-33-41

However, what I actually get back is:

1-3-6-10-14-19-25-32-41
and
1-20-26-33-41

Currently, my tree has only 2 possible downward paths from each point however, later on, this might be as high as 10 or perhaps higher. Below is the code I am using. Can anyone see what is wrong? Have I totally got it wrong perhaps and there is a better/simpler way to do this?

The function FindWaypoints called in the below code returns a string such as 2-3. This represents all the points that point 1 connects to.

tmpRoute is a string

AllRoutes is an array list that holds all possible routes

Private Sub FindSingleRoute(ByVal Start As String, ByVal Finish As String)

Dim Connections As Array = Strings.Split(FindWaypoints(Start), "-")

If Array.IndexOf(Connections, Finish) > -1 Then

tmpRoute += "-" & Finish
AllRoutes.Add(StartPoint & tmpRoute)
tmpRoute = ""

Else

If Connections(0) <> "" Then

For Each RoutePoint As String In Connections

If RoutePoint = "*" Then

If tmpRoute.Contains(Finish) = False Then tmpRoute = ""

Else

tmpRoute += "-" & RoutePoint

End If

Call FindSingleRoute(RoutePoint, Finish)

Next

End If

End If

End Sub


Any help is greatly appreciated. I suspect that I have the code totally wrong because I am completely lost now in the logic after staring at it for so long. If anyone can help with writing a (recursive i assume) function that finds all routes possible between 2 points I will be super grateful!

TIA

(if the tree looks weird then it is the formatting of my newsreader. i also attach a text file containing the samge tree.

Daniel

 

[Daniel]

I am trying to find all possible routes between two points on a tree

using a top to bottom search only. The tree looks like this:

' 1
' / \
' 2 3
' / \
' 4 5 6
' / \ / \
' 7 8 9 10
' / \ \ / \ /
' 11 12 13 14 15
' \ \ / / \ / \
' 16 17 18 19 20 21
' / \ / \ / / / \
' 22 23 24 25 26 27 28
' \ / \ / / / \ / \ / \
' 29 30 31 32 33 34 35 36
' /\ / \ / \ / / / \ / \
' 37 38 39 40 41 42 43 44 45
The problem is that asking for all routes between 1 and 41 should
give:

I think I need a variant of Djikstra's algorithm but simplified. I hope
someone can help because I have spent another day banging my head against
a wall with this :-(

Arrrggghhhh!!

Daniel

 

[Tim Patrick]

If I were to implement this, I would design a special class that identified
the two branches from any given node.

Public Class BranchNode
Public NodeValue As Integer ' The node value itself
Public LeftBranch As NodeValue
Public RightBranch As NodeValue
' If both LeftBranch and RightBranch are Nothing, this is a Leaf node
End Class

It would take some work to populate all of the nodes, but once you had it
you could traverse all the way down to the leaves using a recursive routine.
It would be a lot easier to track and debug than using a string array (at
least to me).

 

[Tim Patrick]

Oops, I had typos in the class. Here is the correct class.

Public Class BranchNode
Public NodeValue As Integer ' The node value itself
Public LeftBranch As BranchNode
Public RightBranch As BranchNode
' If both LeftBranch and RightBranch are Nothing, this is a Leaf node
End Class

 

[Daniel]

If I were to implement this, I would design a special class that

identified the two branches from any given node.

Public Class BranchNode
Public NodeValue As Integer ' The node value itself
Public LeftBranch As NodeValue
Public RightBranch As NodeValue
' If both LeftBranch and RightBranch are Nothing, this is a Leaf
node
End Class

Thanks Tim. I'll have a look at it over the weekend and see how I get on.
Not sure I totally understand what you have said but we'll see! Any other
tips you can give?

Thanks,

Daniel

 

[Tim Patrick]

You might want to read up a little on data structures, a basic computer science
idea. Here is a starting point on Wikipedia.

http://en.wikipedia.org/wiki/Data_structures

Also, I posted a correction to the class below in another message in this
same thread that replaces "NodeValue" in the LeftBranch and RightBranch lines
with "BranchNode". Sorry for the mistake.