[Monotone-devel] Bug in monotone lca

[Wim Oudshoorn]

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.

This seems to be caused by the fact that the algorithme
to determine the lca works rougly as follows:

 Take initial ancestors of "M"
 Take initial ancestors of "N"

 Now repeat until we find an intersection:
    expand ancestors of "M" by parents of current
        ancestor set.
    expand ancestors of "N" by parents of current
        ancestor set.

This algorithme will not always yield the correct
result.

The above makes me wonder if the lcad algorithme
always yields an optimal result.  However my
C++ skills are not good enough to understand what
is going on.


Wim Oudshoorn.