Re: [Monotone-devel] Bug in monotone lca

[Wim Oudshoorn]

Timothy Brownawell <address@hidden> writes:

> On 5/19/05, Wim Oudshoorn <address@hidden> wrote:
>> 
>> If you have the following revision graph:
>> 
>>                        A
>>                       /|\
>>                      B C D
>>                     / / \ \
>>                    / E   F \
>>                   / /     \ \
>>                  / G       H \
>>                 /  |       |  \
>>                 |  I       J  |
>>                 \ /        \ /
>>                  K          L
>>                  |          |
>>                  M          N
>> 
>> and ask for
>> 
>> monotone lca M N
>> 
>> it will return A and not C.
>
> 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?

Wim Oudshoorn.