Fredrik Kuivinen <freku045@student.liu.se> writes: >> See the big illustration at the top of the source for how you >> can construct pathological case to defeat an attempt to >> guarantee such. --all guarantees that the output contains all >> interesting ones, but does not guarantee the output has no >> suboptimal merge bases. > > There are two examples at the top of the source. In the first one a > least common ancestor is returned. As I interpret the second one, it > is an example of how the old algorithm without the postprocessing step > produced a common ancestor which is not least. Ah, yes, I remember now. The drawing was done while we were working on the solution to that pathological case; mark_reachable_commits() solves that horizon effect. http://article.gmane.org/gmane.comp.version-control.git/11410 http://article.gmane.org/gmane.comp.version-control.git/11429 http://article.gmane.org/gmane.comp.version-control.git/11552 http://article.gmane.org/gmane.comp.version-control.git/11613 However, our inability to come up with one is not a nonexistence proof of cases the current algorithm can fail, so math minded people _might_ want to prove the algorithm is optimal. Not me, though. - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.htmlReceived on Tue May 16 17:52:05 2006
This archive was generated by hypermail 2.1.8 : 2006-05-16 17:52:26 EST