generic tree pathfinding

[Nevyn]

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

[John Harrison]

Re: generic tree pathfinding


"Nevyn" <nevynZEROSPAM@ hotmail.com> wrote in message
news:pan.2003.0 8.14.00.10.25.8 24989@hotmail.c om...[color=blue]
> Hi, having a class like the following
>
> class node
> {
> int nodeID;
> list<node> listOfChildren;
> list<node> listOfParents;
> }[/color]

I think you mean

class node
{
int nodeID;
list<node*> listOfChildren;
list<node*> listOfParents;
};
[color=blue]
>
> what is the smartest/fastest way to find the nearest common parent given
> any 2 nodes?[/color]

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?
[color=blue]
>
> i thought about using Djikstra alg. any other possibilities?
>
> thanks a lot
>[/color]


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

[Nevyn]

Re: generic tree pathfinding

On Thu, 14 Aug 2003 06:47:29 +0100, John Harrison wrote:
[color=blue]
> I think you mean
>
> class node
> {
> int nodeID;
> list<node*> listOfChildren;
> list<node*> listOfParents;
> };
>
>[/color]
obviously ;-)
but it was pretty late at night when i wrote it :-)
[color=blue][color=green]
>> what is the smartest/fastest way to find the nearest common parent
>> given any 2 nodes?[/color]
>
> 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?[/color]

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
[color=blue]
> Presumably parent nodes are found by following parent links only?
> Presumably the parent links and child links are reciprocal?[/color]

again, yes and yes
[color=blue]
> 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).[/color]

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