find path from one tree node to another tree node

Discussion in 'Java' started by Peter Mueller, Jan 12, 2008.

  1. 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
     
    Peter Mueller, Jan 12, 2008
    #1
    1. Advertising

  2. Peter Mueller

    Stefan Ram Guest

    Peter Mueller <> 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.
     
    Stefan Ram, Jan 12, 2008
    #2
    1. Advertising

  3. Peter Mueller

    Lars Enderin Guest

    Stefan Ram skrev:
    > Peter Mueller <> 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.
     
    Lars Enderin, Jan 12, 2008
    #3
  4. On Jan 12, 3:26 pm, Lars Enderin <> wrote:
    > Stefan Ram skrev:
    >
    > > Peter Mueller <> 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
     
    Peter Mueller, Jan 12, 2008
    #4
  5. -berlin.de (Stefan Ram) writes:

    > Peter Mueller <> 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 -
    DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
    'Faith without judgement merely degrades the spirit divine.'
     
    Lasse Reichstein Nielsen, Jan 13, 2008
    #5
  6. Peter Mueller

    Stefan Ram Guest

    Lasse Reichstein Nielsen <> 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/.
     
    Stefan Ram, Jan 13, 2008
    #6
  7. Peter Mueller

    Stefan Ram Guest

    Supersedes: <-berlin.de>

    Lasse Reichstein Nielsen <> 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/.
     
    Stefan Ram, Jan 13, 2008
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,465
  2. Thomas Guettler
    Replies:
    3
    Views:
    760
    Andrei
    Oct 27, 2003
  3. Tjerk Wolterink
    Replies:
    2
    Views:
    1,437
    Dimitre Novatchev
    Aug 24, 2006
  4. John Bankhead

    Null parent node on custom tree node after populate on demand

    John Bankhead, Dec 4, 2006, in forum: ASP .Net Web Controls
    Replies:
    0
    Views:
    284
    John Bankhead
    Dec 4, 2006
  5. Robert Cohen
    Replies:
    3
    Views:
    275
    Andrew Durstewitz
    Jul 15, 2003
Loading...

Share This Page