generic tree pathfinding

Discussion in 'C++' started by Nevyn, Aug 14, 2003.

  1. Nevyn

    Nevyn Guest

    Hi, having a class like the following

    class node
    {
    int nodeID;
    list<node> listOfChildren;
    list<node> listOfParents;
    }

    what is the smartest/fastest way to find the nearest common parent given
    any 2 nodes?

    i thought about using Djikstra alg. any other possibilities?

    thanks a lot
     
    Nevyn, Aug 14, 2003
    #1
    1. Advertising

  2. "Nevyn" <> wrote in message
    news:p...
    > Hi, having a class like the following
    >
    > class node
    > {
    > int nodeID;
    > list<node> listOfChildren;
    > list<node> listOfParents;
    > }


    I think you mean

    class node
    {
    int nodeID;
    list<node*> listOfChildren;
    list<node*> listOfParents;
    };

    >
    > what is the smartest/fastest way to find the nearest common parent given
    > any 2 nodes?


    How do you define nearest common parent? Suppose there's a common parent 1
    away from one node and 4 away from the other node, it that nearer or further
    than one which is 2 away from both nodes?

    >
    > i thought about using Djikstra alg. any other possibilities?
    >
    > thanks a lot
    >



    Presumably parent nodes are found by following parent links only? Presumably
    the parent links and child links are reciprocal?

    Assuming the above to be true it strikes me that you are looking for the
    shortest path between the two nodes (in some sense) which consists of a
    sequence of parent links followed by a sequence of child links (or vice
    versa), the node where you switch from parent links to child links being the
    common parent.

    I would consider a simple breadth first search, the A* algorithm for
    instance. But really it all depends on the nature of your graph (which is
    not a tree I think).

    john
     
    John Harrison, Aug 14, 2003
    #2
    1. Advertising

  3. Nevyn

    Nevyn Guest

    On Thu, 14 Aug 2003 06:47:29 +0100, John Harrison wrote:

    > I think you mean
    >
    > class node
    > {
    > int nodeID;
    > list<node*> listOfChildren;
    > list<node*> listOfParents;
    > };
    >
    >

    obviously ;-)
    but it was pretty late at night when i wrote it :)

    >> what is the smartest/fastest way to find the nearest common parent
    >> given any 2 nodes?

    >
    > How do you define nearest common parent? Suppose there's a common parent
    > 1 away from one node and 4 away from the other node, it that nearer or
    > further than one which is 2 away from both nodes?


    good question... :)
    i forgot to tell that it is not possible for 2 different nodes to have the
    same 2 children, so 2 node (above) can share at most 1 children

    > Presumably parent nodes are found by following parent links only?
    > Presumably the parent links and child links are reciprocal?


    again, yes and yes

    > Assuming the above to be true it strikes me that you are looking for the
    > shortest path between the two nodes (in some sense) which consists of a
    > sequence of parent links followed by a sequence of child links (or vice
    > versa), the node where you switch from parent links to child links being
    > the common parent.
    >
    > I would consider a simple breadth first search, the A* algorithm for
    > instance. But really it all depends on the nature of your graph (which
    > is not a tree I think).


    well, i'll try to be clearer and state the problem more precisely this
    time.
    i built this graph from archeological data, where each node represent an
    excavation stratum which is under some and above others. now, two strata
    might share an horizontal relationship, that is they must be as close as
    possible on the same level. e.g.

    A
    |_______
    | | |
    B C D

    if there is a Hrelation between B & D i have to show

    A
    |______
    | | |
    B D C


    or if

    A
    |__________
    | | |
    B D C
    |_ | |_
    | | E | |
    F G H I

    suppose the relation is between G&I
    the desired result is

    A
    |__________
    | | |
    B C D
    |_ |_ |
    | | | | E
    F G I H

    so my idea was:
    find the closest common parent (A in this case) move the appropriate
    sub-trees (B,D and their descendants) in the right direction

    i used a depth-first alg., but it fails if there is more than one path to
    one of the 'h related' stratums

    Hope i had been clearer this time :)
    thanks a lot
     
    Nevyn, Aug 14, 2003
    #3
    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. Murat Tasan
    Replies:
    1
    Views:
    8,051
    Chaitanya
    Feb 3, 2009
  2. Replies:
    2
    Views:
    437
  3. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,131
  4. Bonj

    high-end generic binary tree

    Bonj, Mar 17, 2005, in forum: C Programming
    Replies:
    0
    Views:
    389
  5. minlearn
    Replies:
    2
    Views:
    456
    red floyd
    Mar 13, 2009
Loading...

Share This Page