Re: [Caml-list] OCamlgraph Strongly Connected components

[Ben Millwood <bmillwood@janestreet.com>]

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

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

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