[Monotone-devel] Re: Bug in monotone lca

[Wim Oudshoorn]

Nathaniel Smith <address@hidden> writes:

> On Fri, May 20, 2005 at 09:48:06AM +0200, Wim Oudshoorn wrote:

>> 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?
>
> It is supposed to find the unique node A such that:
>   - A is a common ancestor
>   - A is comparable to all ancestors of one side
>   - no descendents of A have the above two properties
> This is always unique, and so long as the graph is single rooted,
> always defined.

Yes, I see.  
However in that case lcad has a bug :-)

Consider the following graph:

                  A
                 / \
                B   C
                |  /|
                | / E
                D   |\
                |   F \
                |   |  G
                |   H  |
                |   |  I
                \   J  |
                 \ /   K
                  L

monotone lcad L K             // version 0.19
will return C, not E.

I have database with this example (artifically constructed).

>> P.S.:  As a stopgap measure, I still think my proposal of a week
>> ago is better :-)
>
> Indeed, it looked quite interesting and plausible; I've been meaning
> to respond, but it takes some effort to wrap my head back around what
> sort of properties are needed and figure out whether I really believe
> your suggestion handles all the bad cases...

Ah, I don't think it will handle all the bad cases,
I just thought it was better than lcad. 
But I can be persuaded otherwise :-)

And as suggested in another thread, it really depends on the
development model you choose.

At the moment I am trying to wrap my head around the merging problem as 
well.  It is rather tricky and just creating a mathematical vocabulary
is already quite challenging.  I am writing everything down and 
when it comes to a stage that I can draw some conclusions and can
be understood by more people than just me I will publish it.
>
>>   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.
>
> './configure CFLAGS="-O0 -ggdb3" CXXFLAGS="-O0 -ggdb3"' makes a huge
> difference :-).  (Actually just the -O0 part, but when you're
> developing, it's sorta handy to always have debugging info there
> without having to recompile for it.)

I will try this.  Hopefully it compiles faster.

Wim Oudshoorn.