[Caml-list] OCamlgraph Strongly Connected components

[Kenneth Adam Miller <kennethadammiller@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1385 bytes --]

The following code produces a non-empty list, and I don't think that it
should:

module G = Imperative.Digraph.ConcreteBidirectional(struct
...
end)

module StrongComponents = Components.Make(G)

let cfg = G.create () in
Insn_cfg.G.add_edge insn_cfg zero one;
(* just any two nodes above; that's all you need to know *)
let components = Insn_cfg.StrongComponents.scc_list cfg in
assert_equal [] components

(* Failure above! Why?? *)

The way I understand strongly connected components to work is that, for any
node to be in a component, there must be a path from itself to itself. The
following should yield [zero ; one] ---

let cfg = G.create () in
Insn_cfg.G.add_edge insn_cfg zero one;
Insn_cfg.G.add_edge insn_cfg one zero;
(* just any two nodes above; that's all you need to know *)
let components = Insn_cfg.StrongComponents.scc_list cfg in
assert_equal [zero; one] components (* don't care about order here
seriously *)


Is there a module or utility function that I could use as I would expect
the above example to behave, or do I need to filter the lists returned by
components using something like a dominator, to check to see that every
node dominates itself or some such? Also, why does strongly connected
components behave unexpectedly here? Is it my understanding that's off, or
that the implementation is one among several definitions of strongly
connected component?

[-- Attachment #2: Type: text/html, Size: 1661 bytes --]