[Monotone-devel] Re: Bug in monotone lca

[Wim Oudshoorn]

Nathaniel Smith <address@hidden> writes:

> 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.

>> 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].
>
> 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). 

That is what I thought as well (although my explanation
was a little awkward).

> 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.

Yes indeed.  But a looked at the code a little and although 
the lca code I more or less undestand, I can't figure
out what lcad is doing.

Is there some precise specification of what it is supposed to do?

I ask because I was wrong with respect to lca and because some
code is shared I suspect I am wrong on my assumptions for lcad as well.

Wim Oudshoorn.

P.S.:  As a stopgap measure, I still think my proposal of a week
ago is better :-)  However that also requires real implementation
work :-(.   I might want to try to refresh my C++ knowledge,
however monotone takes over 2hrs to compile on my fast computer :-(.
I dread how long it will take to compile on my server 
which is really slow.