Transitive reduction disconnects graph

[sim642]

For example, given this graph:

flowchart LR
  1 --> 2
  2 --> 1
  3 --> 1
  3 --> 2

The transitive reduction algorithm yields this one:

flowchart LR
  1 --> 2
  2 --> 1
  3

This is incorrect because reachability (from node 3) has been changed.

I suspect the fix for #91 in 69fd491f0685b32f14410c33db74b0807be29e53 is too aggressive at removing edges.

Code

module G = Graph.Pack.Digraph

let g = G.create ()
let v1 = G.V.create 1
let v2 = G.V.create 2
let v3 = G.V.create 3
let () =
  G.add_edge g v1 v2;
  G.add_edge g v2 v1;
  G.add_edge g v3 v1;
  G.add_edge g v3 v2

let (_: G.t) =
  G.replace_by_transitive_reduction g

let () =
  G.print_gml Format.std_formatter g

[backtracking]

Hi @sim642 , Thanks for reporting this. This is indeed wrong. I should do my homework more carefully before implementing in OCamlGraph :grimacing: (I just checkout out "The transitive reduction of a directed graph", Aho, Garey, Ullman, 1972, and the case of directed graphs with cycles is considered, yet tricky.)

[backtracking]

If you really need a transitive reduction on graphs with cycles, I suggest you use tred (from Graphviz) in the meantime, which correctly handles the case of cycles:

jc / ~ $ tred
digraph {
  3->1;
  1->2;
  2->1;
  3->2;
}
warning: %1 has cycle(s), transitive reduction not unique
cycle involves edge 2 -> 1
digraph {
    3 -> 1;
    1 -> 2;
    2 -> 1;
}

Note that OCamlGraph has printer and parser for the DOT format so a temporary workaround to the buggy transitive reduction would be an external call to tred (though this is not convenient and not efficient, I agree).

[sim642]

I was about to suggest the tred algorithm: https://gitlab.com/graphviz/graphviz/-/blob/fb242ae33b809d87f46fe3a20bb95a6fc70f51d5/lib/cgraph/tred.c. It's obviously more optimized with a special-purpose DFS, but the important difference might be that it doesn't run all DFS-s at the beginning (when no edges have been removed) but it runs DFS-s after some edges might already be removed (so the reachability information is up to date).

[backtracking]

I'm already reading this code :grin: but thanks!

[backtracking]

Note: it seems that tred does not return a graph with a minimal number of edges when there are cycles, and thus differs from what is described in Aho/Garey/Ullman. On this graph

digraph {
a->b;
b->c;
c->b;
b->a;
}

tred returns the same graph, while there is a 3-edge graph solution (a->b; b->c; c->a), as explained in the paper. This solution is not a subgraph, but such non-subgraph solutions only occur when there are cycles.

That being said, I'll implement the tred solution, as it is simpler.

[backtracking]

This is now fixed (hopefully). Thanks once again for reporting this issue. For the record, I made a mistake in the code testing the result of the transitive reduction (otherwise I would have spotted the error immediately) :facepalm: