Re: [Monotone-devel] Bug in monotone lca

[Nathaniel Smith]

On Thu, May 19, 2005 at 07:29:14PM +0200, Wim Oudshoorn wrote:
> Timothy Brownawell <address@hidden> writes:
> > But A *is* the least common ancestor (M->K->B->A; N->L->D->A). That
> > it's also an ancestor of a more distant common ancestor doesn't
> > matter. Distances can be funny that way.
> 
> Ah, I interpreted the least common ancestor in a different way.
> 
> My interpretatio was:
>    Look at all common ancestors, in this case (A, C)
>    And take from all common ancestors the "latest", in this case
>    "C". 
> [Ignoring for the moment that this in the general case this
>  does not give a unique lca].
> 
> Apparently this is not the monotone interpretation.  
> So could you explain, or provide a pointer to, 
> what is the definition of lca?

Hrm, I'm actually more used to the "minimal common ancestor"
definition (i.e., a node A such that no common ancestors are
descendents of A), than the "nearest common ancestor" (which seems to
be what we use).  It doesn't make much of a difference for anything
that monotone uses its LCA algorithm for, though; in fact, "nearest
common ancestor" is probably better.  (We just use LCA when we want a
nearby common ancestor, that we can use to generate a path from one
node to another, for instance.)

This is why, though, if someone wanted to make
unique-lca-or-else-lca+dom into the merge ancestor selection
algorithm as a temporary stopgap measure, they would have to actually
do some work, since for merging you really do need to use the "minimal
common ancestor" variant.

-- Nathaniel

-- 
"Of course, the entire effort is to put oneself
 Outside the ordinary range
 Of what are called statistics."
  -- Stephan Spender