[m-rev.] for review: Implement two more transitive closure algorithms.

[Julien Fischer]

On Wed, 25 Jan 2023, Peter Wang wrote:

> On Wed, 25 Jan 2023 14:31:16 +1100 Julien Fischer <jfischer at opturion.com> wrote:
>>
>> Hi Peter,
>>
>> On Tue, 24 Jan 2023, Peter Wang wrote:
>>
>>> Implement two transitive closure algorithms in the digraph module:
>>>
>>>  - Basic_TC by Yannis Ioannidis et al.
>>>
>>>  - STACK_TC by Esko Nuutila, a refinement of the SIMPLE_TC algorithm
>>>    previously implemented
>>>
>>> On 115 graphs randomly generated by tests/hard_coded/digraph_tc.m,
>>> ranging from 100 to 3000 vertices:
>>>
>>> - basic_tc ran from 0.79 to 1.66 times as fast as the existing
>>>   simple_tc implementation (mean 1.158, stddev 0.157)
>>>
>>> - basic_tc ran from 0.83 to 1.69 times as fast as stack_tc
>>>   (mean 1.111, stddev 0.157)
>>>
>>> Therefore, after this commit, I will delete the simple_tc and stack_tc
>>> implementations, but they will be available in the version history.
>>
>> For the digraph module in the standard library, that's fair enough.
>> I suggest making a renamed copy of the digraph module that contains the
>> alternative transitive closure implementations and adding it to the
>> benchmark suite.
>
> You mean tests/benchmarks? I suppose I could move the benchmark code
> currently in tests/hard_coded/digraph_tc.m to a driver program in
> tests/benchmarks.

No, I meant benchmarks/progs.

Julien.