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

[Peter Wang]

On Tue, 17 Jan 2023 17:34:19 +1100 Peter Wang <novalazy at gmail.com> wrote:
> +:- pred simple_tc(key_set_map(T)::in, digraph_key(T)::in,
> +    simple_tc_visit(T)::in, simple_tc_visit(T)::out,
> +    simple_tc_state(T)::in, simple_tc_state(T)::out) is det.
> +
> +simple_tc(OrigEdges, V, !Visit, !State) :-
> +    some [!RootMap, !Stack] (
> +        !:RootMap = !.State ^ root_map,
> +        !:Stack = !.State ^ stack,
> +
> +        map.det_insert(V, V, !RootMap),
> +        !:Stack = [V | !.Stack],
> +
> +        !State ^ root_map := !.RootMap,
> +        !State ^ stack := !.Stack
> +    ),
> +
> +    get_successors(OrigEdges, V, OrigSuccV),
> +    sparse_bitset.foldl2(simple_tc_for_v_w(OrigEdges, V), OrigSuccV,
> +        !Visit, !State),
> +
> +    RootMap = !.State ^ root_map,
> +    ( if map.search(RootMap, V, V) then
> +        some [!Stack, !Comp, !SuccMap, !PredMap] (
> +            !:Stack = !.State ^ stack,
> +            !:Comp = !.State ^ comp,
> +            !:SuccMap = !.State ^ succ_map,
> +            !:PredMap = !.State ^ pred_map,
> +
> +            % V is the root of a component that also contains Ws.
> +            pop_component(V, Ws, !Stack),
> +            sparse_bitset.insert(V, !Comp),
> +            sparse_bitset.insert_list(Ws, !Comp),
> +
> +            % Distribute successors from the root V to other vertices in the
> +            % component.
> +            get_successors(!.SuccMap, V, SuccV),
> +            list.foldl(add_successors(SuccV), Ws, !SuccMap),
> +
> +            % Maintain the predecessor map from the (new) successors back to
> +            % each vertex in the component. This ends up dominating the time
> +            % spent computing the transitive closure, even though the user may
> +            % not make use of the precessor map at all.
> +            add_predecessors(SuccV, V, !PredMap),
> +            list.foldl(add_predecessors(SuccV), Ws, !PredMap),

We can update the precessor maps more efficiently. With the following
change, benchmarks on some randomly generated graphs ran from 2.33 to 93
times as fast as the old algorithm.

Peter

diff --git a/library/digraph.m b/library/digraph.m
index fb831e84e..b54788929 100644
--- a/library/digraph.m
+++ b/library/digraph.m
@@ -444,6 +444,17 @@ key_set_map_add(XI, Y, Map0, Map) :-
         map.det_insert(XI, SuccXs, Map0, Map)
     ).

+:- pred key_set_map_union(uint::in, digraph_key_set(T)::in,
+    key_set_map(T)::in, key_set_map(T)::out) is det.
+
+key_set_map_union(XI, Ys, Map0, Map) :-
+    ( if map.search(Map0, XI, SuccXs0) then
+        sparse_bitset.union(Ys, SuccXs0, SuccXs),
+        map.det_update(XI, SuccXs, Map0, Map)
+    else
+        map.det_insert(XI, Ys, Map0, Map)
+    ).
+
 :- pred key_set_map_delete(uint::in, digraph_key(T)::in,
     key_set_map(T)::in, key_set_map(T)::out) is det.

@@ -1189,8 +1200,14 @@ simple_tc(OrigEdges, V, !Visit, !State) :-
             % each vertex in the component. This ends up dominating the time
             % spent computing the transitive closure, even though the user may
             % not make use of the precessor map at all.
-            add_predecessors(SuccV, V, !PredMap),
-            list.foldl(add_predecessors(SuccV), Ws, !PredMap),
+            (
+                Ws = [],
+                sparse_bitset.foldl(add_predecessor(V), SuccV, !PredMap)
+            ;
+                Ws = [_ | _],
+                sparse_bitset.list_to_set([V | Ws], VWs),
+                sparse_bitset.foldl(add_predecessors(VWs), SuccV, !PredMap)
+            ),

             !State ^ stack := !.Stack,
             !State ^ comp := !.Comp,
@@ -1281,28 +1298,23 @@ get_successors(SuccMap, V, SuccV) :-
 :- pred add_successors(digraph_key_set(T)::in, digraph_key(T)::in,
     key_set_map(T)::in, key_set_map(T)::out) is det.

-add_successors(Successors, V, !SuccMap) :-
-    V = digraph_key(VI),
-    ( if map.search(!.SuccMap, VI, SuccV0) then
-        sparse_bitset.union(Successors, SuccV0, SuccV),
-        map.det_update(VI, SuccV, !SuccMap)
-    else
-        SuccV = Successors,
-        map.det_insert(VI, SuccV, !SuccMap)
-    ).
+add_successors(Ys, X, !Map) :-
+    X = digraph_key(XI),
+    key_set_map_union(XI, Ys, !Map).

 :- pred add_predecessors(digraph_key_set(T)::in, digraph_key(T)::in,
     key_set_map(T)::in, key_set_map(T)::out) is det.

-add_predecessors(Successors, V, !PredMap) :-
-    sparse_bitset.foldl(add_predecessor(V), Successors, !PredMap).
+add_predecessors(Ys, X, !Map) :-
+    X = digraph_key(XI),
+    key_set_map_union(XI, Ys, !Map).

 :- pred add_predecessor(digraph_key(T)::in, digraph_key(T)::in,
     key_set_map(T)::in, key_set_map(T)::out) is det.

-add_predecessor(V, Successor, !PredMap) :-
-    Successor = digraph_key(SuccessorI),
-    key_set_map_add(SuccessorI, V, !PredMap).
+add_predecessor(Y, X, !Map) :-
+    X = digraph_key(XI),
+    key_set_map_add(XI, Y, !Map).

 %---------------------------------------------------------------------------%