Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > find path from one tree node to another tree node

Reply
Thread Tools

find path from one tree node to another tree node

 
 
Peter Mueller
Guest
Posts: n/a
 
      01-12-2008
Hello,

I have a non binary tree and looking for a solution to find the path
between two given nodes (not just leaves).
Is there a class in the Java class library that provides the
functionality already? If not, can someone
recommend a library. A description of the algorithm would also help.

Thanks,
Peter


 
Reply With Quote
 
 
 
 
Stefan Ram
Guest
Posts: n/a
 
      01-12-2008
Peter Mueller <(E-Mail Removed)> writes:
>I have a non binary tree and looking for a solution to find the path
>between two given ¯¯¯¯¯¯¯¯


Sometimes, there are /several/ paths between two points. But
you surely can go up to the root and then down to the other
point. (The last path can be constructed by going up to the
root from that other point.)

If you find another common ancester by this, you even can take
an abbreviation.

However, there will not be any path if the tree is empty.

 
Reply With Quote
 
 
 
 
Lars Enderin
Guest
Posts: n/a
 
      01-12-2008
Stefan Ram skrev:
> Peter Mueller <(E-Mail Removed)> writes:
>> I have a non binary tree and looking for a solution to find the path
>> between two given ¯¯¯¯¯¯¯¯

>
> Sometimes, there are /several/ paths between two points. But
> you surely can go up to the root and then down to the other
> point. (The last path can be constructed by going up to the
> root from that other point.)
>
> If you find another common ancester by this, you even can take
> an abbreviation.


ITYM shortcut, not abbreviation.
 
Reply With Quote
 
Peter Mueller
Guest
Posts: n/a
 
      01-12-2008
On Jan 12, 3:26*pm, Lars Enderin <(E-Mail Removed)> wrote:
> Stefan Ram skrev:
>
> > Peter Mueller <(E-Mail Removed)> writes:
> >> I have a non binary tree and looking for a solution to find the path
> >> between two given * * * * * * * * * * * * * * * * * * * * * ¯¯¯¯¯¯¯¯

>
> > * Sometimes, there are /several/ paths between two points. But
> > * you surely can go up to the root and then down to the other
> > * point. *(The last path can be constructed by going up to the
> > * root from that other point.)

>
> > * If you find another common ancester by this, you even can take
> > * an abbreviation.

>
> ITYM shortcut, not abbreviation.


Hello Stefan,

I wrote a tree class realizing this method. Works fine for me.
Thank for the hint.

Peter
 
Reply With Quote
 
Lasse Reichstein Nielsen
Guest
Posts: n/a
 
      01-13-2008
http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Stefan Ram) writes:

> Peter Mueller <(E-Mail Removed)> writes:
>>I have a non binary tree and looking for a solution to find the path
>>between two given ¯¯¯¯¯¯¯¯

>
> Sometimes, there are /several/ paths between two points.


Not in a tree. Unless you allow going back and forth along the
same edge as part of a path (i.e., visiting the same node
twice), there is exactly one path between any two node.

> However, there will not be any path if the tree is empty.


Nor will there be any nodes, and since the question was on how
to find a path between two nodes, we know the tree isn't empty.

Apart from that, the solution is fine. Trace a path from each node
to the root. Then find the lowest node that is on both paths and
make a path from one node to that node, and from there to the other node.

If your tree keeps information about the depth of each node in the node,
then you won't have to trace the paths all the way to the root, but can
compare nodes at the same lavel until the paths meet.

/L
--
Lasse Reichstein Nielsen - http://www.velocityreviews.com/forums/(E-Mail Removed)
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      01-13-2008
Lasse Reichstein Nielsen <(E-Mail Removed)> writes:
>>Sometimes, there are /several/ paths between two points.

>Not in a tree. Unless you allow going back and forth along the
>same edge as part of a path (i.e., visiting the same node
>twice), there is exactly one path between any two node.


This indeed is allowed for a path - otherwise it would be a
called a »simple path«. (Sometimes »simple« might be omitted,
when it can be deduced from the context. This might have been
possible in the case of the OP.)

A tree, then can be /defined/ as a graph, where any two points
can be connected by a unique /simple path/.

 
Reply With Quote
 
Stefan Ram
Guest
Posts: n/a
 
      01-13-2008
Supersedes: <(E-Mail Removed)-berlin.de>

Lasse Reichstein Nielsen <(E-Mail Removed)> writes:
>>Sometimes, there are /several/ paths between two points.

>Not in a tree. Unless you allow going back and forth along the
>same edge as part of a path (i.e., visiting the same node
>twice), there is exactly one path between any two node.


This indeed is allowed for a path - otherwise it would be a
called a »simple path«. (Sometimes »simple« might be omitted,
when it can be deduced from the context. This might have been
possible in the case of the OP.)

A tree, then can be /defined/ as an undirected simple graph,
where any two points can be connected by a unique /simple path/.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to find node in TreeView by using string(the same as Node.Text) ? jiing ASP .Net 0 04-27-2007 02:34 AM
Null parent node on custom tree node after populate on demand John Bankhead ASP .Net Web Controls 0 12-04-2006 06:29 PM
xsl variable $node/text() but $node can non-node-set help! Tjerk Wolterink XML 2 08-24-2006 03:28 AM
How to set the node indent property between the parent node and the leaf node viveknatani@gmail.com ASP .Net 0 02-13-2006 07:11 PM
Make a relative url path from an absolute path to another one Thomas Guettler Python 3 10-27-2003 04:41 PM



Advertisments