[m-rev.] for review: Fix digraph.tc and digraph.rtc.

[Julien Fischer]

On Tue, 10 Jan 2023, Peter Wang wrote:

> The implementation of digraph.rtc was incorrect (as demonstrated in the
> new test case), which meant that digraph.tc was also incorrect.

Ouch!

> library/digraph.m:
>    Fix the implementation of rtc (reflexive transitive closure):
>
>    - Following the algorithm used in digraph.cliques, it needs to
>      traverse the graph G in *reverse* depth-first order.
>
>    - To find the clique containing a vertex X, it needs to do a DFS on
>      the *reversed* graph to find the vertices with a path to X.
>      The vertices that were previously unvisited will be members of
>      the same clique as X.
>
>    - Previously it found the "followers" of the elements of the clique,
>      and the followers of those followers, then added edges from the
>      members of the current clique to those followers. However, that
>      only includes vertices two steps removed from the clique.
>      I have fixed it to add edges to *all* vertices reachable from
>      members of the clique.
>
>    Add straightforward implementations of tc and rtc for comparison.
>
>    Add some comments.

...

> diff --git a/library/digraph.m b/library/digraph.m
> index 3dd0d35cc..7529bd1f9 100644
> --- a/library/digraph.m
> +++ b/library/digraph.m

> @@ -362,6 +365,24 @@
> 
> :- implementation.
> 
> +% Everything below here is not intended to be part of the public interface,
> +% and will not be included in the Mercury library reference manual.
> +
> +:- interface.
> +
> +    % Straightforward implementation of tc for debugging.
> +    %
> +:- pred slow_tc(digraph(T)::in, digraph(T)::out) is det.
> +
> +    % Straightforward implementation of rtc for debugging.
> +    %
> +:- pred slow_rtc(digraph(T)::in, digraph(T)::out) is det.
> +
> +%---------------------------------------------------------------------------%
> +%---------------------------------------------------------------------------%
> +
> +:- implementation.
> +
> :- import_module bimap.
> :- import_module uint.
> :- import_module require.
> @@ -1048,14 +1069,24 @@ tc(G, Tc) :-
>     % digraph.tc returns the transitive closure of a digraph.
>     % We use this procedure:
>     %
> -    % - Compute the reflexive transitive closure.
> +    % - Compute the reflexive transitive closure, which is
> +    %   the reflexive closure of the transitive closure of G:
> +    %       G* = (G+)=

What's that supposed to mean?

> +    %
>     % - Find the "fake reflexives", that is, the set of vertices x for which
>     %   (x,x) is not an edge in G+. This is done by noting that G+ = G . G*
>     %   (where '.' denotes composition). Therefore x is a fake reflexive
>     %   iff there is no y such that (x,y) is an edge in G and (y,x) is an edge
>     %   in G*.
> +    %
>     % - Remove those edges from the reflexive transitive closure
>     %   computed above.
> +    %
> +    % XXX Despite being "easier to debug", digraph.rtc was buggy for a long
> +    % time, so implementing digraph.tc in terms of digraph.rtc was of no
> +    % benefit. We should implement TC using a known efficient algorithm,
> +    % then RTC can be implemented trivially on top of TC.

That's fine.

Julien.