By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
426,179 Members | 2,175 Online
Bytes IT Community
+ Ask a Question
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
Share this Question
Share on Google+
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 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 #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 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 #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 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 #6

This discussion thread is closed

Replies have been disabled for this discussion.