This makes sense if you permit paths to be length 0, and thus every node automatically has a path to itself. This is conceptually nice because it means that "in the same strongly connected component" is an equivalence relation / partition of the graph. 

On 9 March 2017 at 02:15, Kenneth Adam Miller <kennethadammiller@gmail.com> wrote:

I found what I was looking for, sorry.

I can just filter the components that are of size one out quickly. 

On Wed, Mar 8, 2017 at 1:09 PM, Kenneth Adam Miller <kennethadammiller@gmail.com> wrote:

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?