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

[Julien Fischer]

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.

> library/digraph.m:
>    Implement Basic_TC and STACK_TC.
>
>    Use map.transform_value in key_set_map_union to replace a search
>    followed by update.
>
> tests/hard_coded/digraph_tc.m:
>    Test and benchmark the new algorithms.
>
>    Also compare inverse graphs to check that predecessor maps are
>    maintained properly.

That's fine.

Julien.