[m-rev.] for review: Implement simple_tc algorithm.

[Zoltan Somogyi]

2023-01-18 17:43 GMT+11:00 "Peter Wang" <novalazy at gmail.com>:
> On Wed, 18 Jan 2023 15:36:57 +1100 Julien Fischer <jfischer at opturion.com> wrote:
>> 
>> On Tue, 17 Jan 2023, Peter Wang wrote:
>> 
>> > Implement transitive closure using the simple_tc algorithm from
>> > Esko Nuutila's doctoral thesis.
>> >
>> > Based on some runs on randomly generated graphs of 100 to 3000 vertices
>> > (see tests/hard_coded/digraph_tc.m), the simple_tc implementation was
>> > about 1.75 to 2.8 times as fast as the old implementation on my machine.
>> > (It would be many times faster if we did not have to maintain the
>> > predecessor maps required by the digraph representation.)
>> >
>> > library/digraph.m:
>> >    Rename digraph.tc and digraph.rtc to digraph.old_tc and
>> >    digraph.old_rtc. They are kept around for benchmarking,
>> >    and will be deleted soon.
>> 
>> I think we should rename them to transitive_closure and
>> reflexive_transitive_closure (even the latter is a bit long).
>> 
> 
> Hmm, I'm not sure it's worth changing.

I agree with Julien: these predicates should be callable as
transitive_closure and reflexive_transitive_closure. However,
we can keep the old names as well. One can be a forwarding
predicate for the other.

Kudos on the speedup.

Zoltan.