Transitive reduction is incorrect

[benedictleejh]

There seems to be a bug in the transitive reduction computation.

Given the following graph:

a - b - c - d - e
    \__________/

The expected transitive reduction is:

a - b - c - d - e

However, running the transitive_reduction function on it results in an unchanged graph.

The code I used for the above graph is:

open Graph.Pack.Digraph
let g1 = create ()
let v1 = V.create 1
let v2 = V.create 2
let v3 = V.create 3
let v4 = V.create 4
let v5 = V.create 5
let () = add_vertex g1 v1
let () = add_vertex g1 v2
let () = add_vertex g1 v3
let () = add_vertex g1 v4
let () = add_vertex g1 v5
let () = add_edge g1 v1 v2
let () = add_edge g1 v2 v3
let () = add_edge g1 v3 v4
let () = add_edge g1 v4 v5
let () = add_edge g1 v2 v5

I'm also attaching the dot output for the initial graph, and the supposed transitively reduced graph. The tred program in graphviz computes the expected transitive reduction.

raw-dot.txt
reduced-dot.txt

[backtracking]

Indeed the reduction is not minimal on this example (though we have the expected property that the transitive closure of the output is the same as the transitive closure of the input).
I agree that, on DAGs at least, the reduction could be made minimal (and unique), with some extra effort.

[backtracking]

I tentatively fixed transitive_reduction in commit 69fd491.
Please have a look and let me know if this is fine with you.

[benedictleejh]

I ran some quick and dirty tests on my end, and the fixed transitive_reduction performs as expected. It looks fine to me, so feel free to close this issue. (I could close it, but maybe you'd like to keep it around until you have more comprehensive tests for the fix?)