[Caml-list] OCamlgraph Strongly Connected components

[Caml-list] OCamlgraph Strongly Connected components

[Kenneth Adam Miller]

[-- 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 --]

Re: [Caml-list] OCamlgraph Strongly Connected components

[Kenneth Adam Miller]

[-- 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 --]

Re: [Caml-list] OCamlgraph Strongly Connected components

[Ben Millwood]

[-- 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 --]

Re: [Caml-list] OCamlgraph Strongly Connected components

[Kenneth Adam Miller]

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

I actually just meant that I did not want single node sized components, and
that I would operate over the others, dropping those.

What I was getting effectively included all nodes of a graph at some point
in what was returned, and I was executing an analyses that looked within
the components to remove other nodes. It was failing to remove the nodes
because of that.

On Mar 13, 2017 5:46 AM, "Ben Millwood" <bmillwood@janestreet.com> wrote:

> 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: 3765 bytes --]