
From:  Wim Oudshoorn 
Subject:  [Monotonedevel] Bug in monotone lca 
Date:  Thu, 19 May 2005 18:40:03 +0200 
Useragent:  Gnus/5.1002 (Gnus v5.10.2) Emacs/21.3.50 (darwin) 
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.
[Prev in Thread]  Current Thread  [Next in Thread] 