426,179 Members | 2,175 Online
Need help? Post your question and get tips & solutions from a community of 426,179 IT Pros & Developers. It's quick & easy.

# All possible paths in decision tree

 P: n/a 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 --------------------------------------------------- To contact me you need to clean up my email address. It should be fairly obvious... Oct 26 '06 #1
5 Replies

 P: n/a 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 Oct 27 '06 #2

 P: n/a 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 Start-to-Finish Visual Basic 2005 >I am trying to find all possible routes between two points on a treeusing 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 45The problem is that asking for all routes between 1 and 41 shouldgive: 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 Oct 27 '06 #3

 P: n/a 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 ----- Tim Patrick Start-to-Finish Visual Basic 2005 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 Start-to-Finish Visual Basic 2005 >>I am trying to find all possible routes between two points on a treeusing 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 45The problem is that asking for all routes between 1 and 41 shouldgive: I think I need a variant of Djikstra's algorithm but simplified. Ihope someone can help because I have spent another day banging myhead against a wall with this :-(Arrrggghhhh!!Daniel Oct 27 '06 #4

 P: n/a 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 --------------------------------------------------- To contact me you need to clean up my email address. It should be fairly obvious... Oct 27 '06 #5

 P: n/a 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. ----- Tim Patrick Start-to-Finish Visual Basic 2005 >If I were to implement this, I would design a special class thatidentified the two branches from any given node.Public Class BranchNodePublic NodeValue As Integer ' The node value itselfPublic LeftBranch As NodeValuePublic RightBranch As NodeValue' If both LeftBranch and RightBranch are Nothing, this is a LeafnodeEnd 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 --------------------------------------------------- To contact me you need to clean up my email address. It should be fairly obvious... Oct 27 '06 #6

### This discussion thread is closed

Replies have been disabled for this discussion.