Fredrik Kuivinen <freku045@xxxxxxxxxxxxxx> 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.
-
: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html