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
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
