0
$\begingroup$

I'm well aware of ways to efficiently calculate the lowest common ancestor in a tree of nodes which converge to a single root (ie, each node has only one parent). Just iterate back to root for each person, then walk back from root tossing off anything common.

In a matriarchal society, for example, this could be used to quickly calculate how any two people are related as long as only the mothers are considered.

But if both parents are considered, eg mother AND father, then the algorithm just described breaks down.

So I wondered is there an algorithm to tell two people how they are related in a family tree where both parents are considered? For example, see the Icelandic genealogy app (https://www.islendingabok.is/) which does precisely that. How's it done, algorithmically speaking?

$\endgroup$
0
$\begingroup$

Just do breadth-first search up the graph, colouring each person you meet as being an ancestor of one person or the other, and stop when you reach a person who's an ancestor of both. You should do the searches in parallel (one generation back on one person, then one generation back on the other, and so on) because any common ancestor will be approximately the same number of generations back on each side.

Indeed, this is exactly what you should do on a tree: going all the way back to the root and then discarding all common ancestors after the first takes more time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.