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