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

[Julien Fischer]

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).

>    Use the simple_tc algorithm to implement digraph.tc.
>
>    Use digraph.tc to implement digraph.rtc.
>
>    Let key_set_map_add call sparse_bitset.insert_new instead of
>    sparse_bitset.contains followed by sparse_bitset.insert.

...

> diff --git a/library/digraph.m b/library/digraph.m
> index cf2e8e896..fb831e84e 100644
> --- a/library/digraph.m
> +++ b/library/digraph.m
> +%---------------------------------------------------------------------------%
> +
> +% This implements the simple_tc algorithm from Esko Nuutila's thesis
> +% "Efficient Transitive Closure Computation in Large Digraphs", p 49.
> +% <http://www.cs.hut.fi/~enu/thesis.html>
> +
> +:- type simple_tc_visit(T)
> +    --->    simple_tc_visit(
> +                visit_counter   :: uint,
> +                visit_map       :: map(digraph_key(T), uint)
> +            ).
> +
> +:- type simple_tc_state(T)
> +    --->    simple_tc_state(
> +                % A map from a vertex to the candidate root of the component
> +                % that will include the vertex.
> +                root_map        :: map(digraph_key(T), digraph_key(T)),
> +
> +                % A vertex is included in comp once the component containing
> +                % the vertex has been determined.
> +                comp            :: digraph_key_set(T),
> +
> +                % Stack of vertices being visited.
> +                stack           :: list(digraph_key(T)),
> +
> +                % The successors and precessors of each vertex in the graph

predecessors.

That looks fine otherwise.

Julien.