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

[Peter Wang]

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.

Peter