|  |
| |
Here is the algorithm for finding the nearest common
ancestor of two taxa t1 and
t2:
If t1 and t2 have the same depth, see if they are
identical. If so, the result is t1.
If t1 and t2 are not at the same depth, replace
the deeper with its parent and
return to Step 1.
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.
# - - - 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