Route tracing - tree structures

asp.net / c#

[Argblat]

Hi all,

I'm having trouble coming up with a solution for a logical problem, and I'm wondering if anyone can offer their expertise. I will try to explain it as best I can.

Imagine a tree structure....many points with links between them. The tree is NOT binary as a parent can have more than 2 children, but each child has only one parent.

I have stored the tree structure in a database, by having a 2-column table where column 1 is "point A" and column 2 is "point b"

an example would be
pointa, pointb
--------------
1, 2
1, 3
1, 4
2, 5
2, 6
2, 7
4, 8
4, 9
4, 10

If you draw this out on a piece of paper using three tiers, it makes it much easier to understand what I'm talking about.

Now here is the problem:
Users will enter a starting point and an ending point (i.e. Start at 1, end at 10) and I need a way to logically trace the entire path from the starting point to the end point.

I have been guided in the direction of using a tree structure, but I have no experience with this structure. I am also open to ANY suggestions that will solve the problem.

I appreciate any and all help
Sincerely,
Mike

[aspdaddy]

If children only have one parent then start at the end , look up the parents, until you arrive :0

[Argblat]

AspDaddy,

You are right, unfortunatley I was mistaken and I should have never said "each child has only one parent" as this is currently the case, but (assume) will not be in the future.

Allow me to make a new example:

point_a, point_b
----------------
1,2
1,3
1,4
2,5
2,6
2,7
3,6
3,7
3,8
4,9

[aspdaddy]

There could be more than one route between two points? Then it sounds like an optimisation problem.

You could write a loop to try every possible path (brute force method).

If its a real big tree, and you are serious about doing this check out XPress-Mosel (www.dashoptimization.com) it will solve it visually for you, the model you need to load is the travelling saleman model.

[Argblat]

AspDaddy, thank you for your help.

It turns out that the combination of your two posts helped me to realize what my solution was.

It turns out that the original set of data, including all points DOES in fact include for there to be multiple possibilities from one point to another.

HOWEVER, before we find the path, we define the origin (pointA) and destination (pointB)...in defining these points, we create a subsection of the original data, and in doing this we create a tree where no child has more than one parent.

In doing this, I was able to follow your original advice to work backwards, and everything in honky-dory

thank you
Mike