Re: [Caml-list] OCamlgraph Strongly Connected components

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

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

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?
>

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