Reachability by Fixpoint is not working as expected.

[camlspotter]

I wrote a reachability test using the same code explained in fixpoint.mli, but the result is puzzling.

Here is a simple reproducible example. I create here a small graph 1 -> 2 -> 3 and see which vertices are reachable from 1, then from 2. I expect 2 and 3 are reported as reachable from 2, but the code linked with ocamlgraph.1.8.8 does not:

(* ocamlfind ocamlc -o g.exe -package ocamlgraph g.ml -linkpkg *)

module G = Graph.Persistent.Digraph.Concrete(struct
    type t = int
    let compare = compare
    let hash x = x
    let equal = (=)
  end)
    
module Reachability = Graph.Fixpoint.Make(G)
    (struct
      include G
      type g = G.t
      type data = bool
      let direction = Graph.Fixpoint.Forward
      let equal = (=)
      let join = (||)
      let analyze _ = (fun x -> x)
    end)

let test g root =
  let is_root_vertex x = x = root in
  let reachable = Reachability.analyze is_root_vertex g in
  G.iter_vertex (fun n ->
      if reachable n then Format.eprintf "%d is reachable from %d@." n root)
    g

let () =
  (* 1 -> 2 -> 3 *)
  let g =
    let g = G.empty in
    let g = G.add_edge g 1 2 in
    let g = G.add_edge g 2 3 in
    g
  in
  test g 1; (* 1, 2, 3 are reachable from 1 *)

  test g 2  (* 2, 3 are reachable from 2, but it does not report them at all *)

Expected result is:

1 is reachable from 1
2 is reachable from 1
3 is reachable from 1
2 is reachable from 2
3 is reachable from 2

but the actual output is:

1 is reachable from 1
2 is reachable from 1
3 is reachable from 1

Is it a bug of Fixpoint or I misunderstand something?

[yakobowski]

This is another instance of #58, that we furthermore forgot to document in the current Changes. We should probably do a release that ships a fixed version.

[yakobowski]

@backtracking ?

[denismerigoux]

@backtracking, I stumbled across this exact unexpected behavior in a project that is trying to make sense of the French income tax code : https://framagit.org/dgfip/ir-calcul. I am a fan of this graph library, and would be grateful if you could release a new version of the opam package so that we can benefit from @johanneskloos' changes in #69.