Constructing Tree (forest) from Ancestor function

Question

Question:

Suppose I have a

• set of male people, and
• a function isAncestor(person1,person2) that checks whether person1 is an ancestor of person2 in O(1) time. Eg, isAncestor(grandfather, grandson) would return true.

What are some fast algorithms for constructing a complete "family tree" by using only this information? (or "family forest" as not everyone may be related to a single common ancestor).

Comment:

This is not homework or from a book. It is derived from some issues I'm having coupling an adaptive finite element code to some blackbox mesh generation software, boiled down to the core problem and expressed in an analogy that shares the same mathematical structure. Right now I have a brute-force $O(n^3)$ method that seems horribly inefficient.

Thank you for any help.

Results:

I've implemented Gilles suggestion in Matlab and tested it. Here is the pseudocode, code, and unit test script. I release it all to the public domain.

Pseudo-code:

function buildAncestorForest
    roots = empty list
    for each person p
        roots = graft(p, roots)

    subfunction new_roots = graft(q, old_roots)
        descendents = empty list
        nondescendents = empty list
        for each person t in old_roots
            if q is an ancestor of t
                append t to descendents
            else
                append t to nondescendents

        if descendents is still empty
            q_is_incomparable = true; 
            for each person t in old_roots
                if t is an ancestor of q
                    new_roots = old_roots;
                    new children of t = graft(q, old children of t)
                    q_is_incomparable = false;
                    break for loop
            if (q_is_incomparable)
                new_roots = append q to old_roots;
        else
            new_roots = append q to nondescendents;
            for each person t in descendents
                children of q = graft(t, children of q);

Matlab code:

https://github.com/NickAlger/MeshADMM/blob/master/buildAncestorForest.m

Unit test script:

https://github.com/NickAlger/MeshADMM/blob/master/test_buildAncestorForest.m

Answer 1

Assumptions

We have a finite set $\mathscr{D}$ of persons and a relation $\prec$: $x \prec y$ means that $x$ is an ancestor of $y$. This relation has the following properties:

• Transitivity: if $x \prec y$ and $y \prec z$ then $x \prec z$ (the ancestor of my ancestor is my ancestor).
• Antisymmetry: if $x \prec y$ then $y \nprec x$ (I am not my ancestor's ancestor).
• Chain: if $x \prec z$ and $y \prec z$ then either $x \prec y$ or $x = y$ or $y \prec x$ (my ancestors form an ordered chain).

Data structures

Let it be given a set data structure on which the following operations are defined:

• empty set
• add an element to a set
• splitting a set according to a property: iterate over the elements, compute a property on each element, and build two subsets, the set of elements for which the property is true and the set for which the property is false. This operation is assumed to be linear in the size of the set.

We will also use a tree data structure, in which each node contains a person and the set of its children. If $t$ is a tree, write $t_R$ for the person at the root node and $t_C$ for the set of children. A forest is a set of trees.

Algorithm

We start with an empty forest and add persons one by one. At each step, the parent-child relationship in the forest is the parent-child relationship for the ancestor relation. We define a recursive function graft that inserts a tree into a forest.

Input of graft: a forest $F$, and a tree $s$ such that none of the elements of the tree is related to any of the persons in $F$. Let $x = s_R$.

First, check whether $x$ is the ancestor of any of the existing persons: split the set $F$ according to the property $x \prec t_R$ for $t \in F$. Let $C$ be the subset of $F$ consisting of descendants of $x$ (if the root of a tree is a descendant of $x$ then all elements are also descendants by transitivity), and $F'$ be the remaining subset. By antisymmetry, none of the persons in $C$ is an ancestor of $x$. None of the elements of $s_C$ are related to any of the persons in $C$ by assumption. Let $u$ be the tree where the root person is $x$ and the set of children of the root is $C \cup s_C$.

By the chain assumption, $x$ can have ancestors in at most one of the trees in $F'$. Iterate over the trees $t \in F'$, and determine which one if any has an ancestor of $x$ at its root (this is a splitting operation where one of the sets is guaranteed to contain at most one element).

Output of graft:

• If no tree in $F'$ has an ancestor of $F'$ at the root, then add the new node to the remaining forest: return $F' \cup \{u\}$.
• If there is a tree $t$ in $F'$ such that $t_R \prec s$, then we need to insert the new element with its descendants into that tree. Let $G = \text{graft}(t_C, u)$. Return $(F' \setminus \{t\}) \cup \{t'\}$ where $t'$ has $t_R$ at the root and $G$ for children.

Main algorithm: Start from an empty forest, and iteratively graft the persons in $\mathscr{D}$ (grafting a person means grafting the tree with this person at the root and no children).

Correctness

From the remarks of this algorithm, it should be easy to prove that the recursive calls to graft are valid (all relatives of the nodes in the tree being inserted are inside that tree), and that $x$ is an ancestor of $y$ in the tree iff $x \prec y$.

Complexity

$\textrm{graft}(F,t)$ performs at most $2 n$ ancestor tests, where $n$ is the number of persons in $F$: one test per root of $F$, one test per root that is not a descendant of the new node, and tests performed by the recursive call if any which applies to a subset of $F$ not including any of its roots. The complexity of other operations is linear in the number of ancestor tests performed.

Therefore the forest construction algorithm performs at most $2 + 4 + 6 + \ldots + 2(n-1) = n (n-1)$ ancestor tests where $n$ is the total number of persons. In fact, it is easy to see that it never performs the same test twice. The overall complexity is therefore $O(n^2)$.

In the worst case, all possible $n (n-1)$ tests are performed. This happens when no two persons are related, and it is unavoidable in this case.

Answer 2

what follows is a somewhat informal description of an $O(n^2)$ algorithm:

main idea:

we build a dag $G=(V,E)$ expressing ancestor relations and subsequently thin it into a family tree. the dag nodes will be the persons involved, edges shall represent ancestor relationships ($(u,v) \in E \to \text{$u$ is ancestor of $v$}$). let $n = |V|$.

algorithmis steps

1. step 1:
   build the transitive closure of the ancestor relation by iterating over all pairs of candidates and adding $(u,v)$ to $E$ iff isAncestor(u, v). complexity: $O(n^2)$.

2. step 2:
   determine the source nodes in the dag. the source nodes represent the minimal elements in the ancestor relation seen as a partial order. note that there will be exactly 1 source node per connected component since we consider only ancestors among the same sex. thus all but 1 edge ending at any given node $v$ are actually forward edges introduced by the transitive closure of the underlying family tree. this step can actually be implemented as a part of step 1 by counting incoming edges for all visited nodes, adding any node $v$ with $indeg(v) = 0$ to a heap while deleting any node with $indeg(v) > 0$ from that heap. after completion of step 1, the heap only contains nodes with $indeg(\cdot) = 0$ ie. all source nodes. as each node is at max once inserted into and once deleted from the heap, this step contributes $O(n \; log\,n)$.

3. step 3:
   perform a depth first search on tha dag starting at the source nodes. if a node is visited for the first time, record the distance from the current source node and the immediate predecessor on the current dfs root path. if a node has been visited and if the current root path length is greater than that recorded with the node, set length and immediate predecessor to the values from the current dfs path and delete the recorded edge from the dag. after the dfs has finished the dag has been reduced to a family forest. as every edge is visited at max once, complexity is $O(E)$. this step works because the dag does not contain crossing edges. therefore for any given pair $(u,v) \in V$ there will never be 2 different paths from $u$ to $v$ of equal length.

in summary:

$O(n^2) + O(n \; log\,n) + O(E) = O(n^2)$