[PATCH 5 of 6 RFC] shrink: add "reverse postorder" and "postorder reverse" toposorts

[Greg Ward]

On Sun, Jan 24, 2010 at 12:51 PM, Benoit Boissinot
<benoit.boissinot at ens-lyon.org> wrote:
>> shrink: add "reverse postorder" and "postorder reverse" toposorts.
>>
>> Based on a rough patch by Benoit Boissinot, adapted to the pluggable
>> sort algorithm design.  toposort_reversepostorder() appears to be
>> equivalent to my toposort_parentdelta(), except it's closer to the
>> textbook algorithm.
>
> Did you have the time to test if that was indeed the case?

Not rigorously.  I only tested on hg-crew itself, because it's small
and therefore fast.  And I only compared file sizes, not contents.  So
as far is it goes, yes my "parent delta" and your "reverse postorder"
appear to be equivalent.  But before I'm convinced, I have to 1) work
through the algorithm on paper and 2) do byte-by-byte comparisons on a
big repository.  Have not had time for that.  I thought it would be
useful to get my "pluggable sort algorithm" patches in first, then we
can more easily compare different algorithms and implementations.

Greg