Next / Previous / Contents / Shipman's homepage

9.2. Taxon.nearestAncestor()

Here is the algorithm for finding the nearest common ancestor of two taxa t1 and t2:

  1. If t1 and t2 have the same depth, see if they are identical. If so, the result is t1.

  2. If t1 and t2 are not at the same depth, replace the deeper with its parent and return to Step 1.

  3. At this point, we know that t1 and t2 are at the same depth but are not the same taxon. Replace each with its parent and return to Step 1.

This procedure is guaranteed to terminate, assuming that the taxa are nodes in a tree. If all else fails, it will terminate when both taxa rise to the root.

xnomo3.py
# - - -   T a x o n . n e a r e s t A n c e s t o r   - - -

    def nearestAncestor ( self, other ):
        """Find the nearest ancestor of self and other.
        """

        #-- 1 --
        t1 = self
        t2 = other

        #-- 2 --
        # [ return the nearest ancestor of t1 and t2 ]
        while t1 is not t2:
            #-- 2 body --
            # [ if t1.rank.depth < t2.rank.depth ->
            #     t1  :=  parent of t1
            #   else if t1.rank.depth > t2.rank.depth ->
            #     t2  :=  parent of t2
            #   else ->
            #     t1  :=  parent of t1
            #     t2  :=  parent of t2 ]
            if  t1.rank.depth < t2.rank.depth:
                t2 = t2.parent
            elif  t1.rank.depth > t2.rank.depth:
                t1 = t1.parent
            else:
                t1 = t1.parent
                t2 = t2.parent

        #-- 3 --
        return t1