Re: [Caml-list] OCamlgraph Strongly Connected components

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

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