From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id D02CC800DB for ; Wed, 8 Mar 2017 19:16:06 +0100 (CET) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=kennethadammiller@gmail.com; spf=Pass smtp.mailfrom=kennethadammiller@gmail.com; spf=None smtp.helo=postmaster@mail-ot0-f177.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of kennethadammiller@gmail.com) identity=pra; client-ip=74.125.82.177; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="kennethadammiller@gmail.com"; x-sender="kennethadammiller@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of kennethadammiller@gmail.com designates 74.125.82.177 as permitted sender) identity=mailfrom; client-ip=74.125.82.177; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="kennethadammiller@gmail.com"; x-sender="kennethadammiller@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ot0-f177.google.com) identity=helo; client-ip=74.125.82.177; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="kennethadammiller@gmail.com"; x-sender="postmaster@mail-ot0-f177.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0CQAQCJScBYf7FSfUpeHQEFAQsBhTwHg?= =?us-ascii?q?1mBBJpVl0WGIgKCOQdCFQECAQEBAQEBARMBAQkLCwgmMYUWAQICASMdARseAwE?= =?us-ascii?q?LBgUEBzcCAiEBAREBBQEcBhOJZgEDDQikCT+MA4IEBQEcgwkFg18KGScNVYJjA?= =?us-ascii?q?QEIAQEBARwCBhKLK4JRhQmCXwWQV4slOooeg2+EK5EgilSHIxQegRU1gSUiFR9?= =?us-ascii?q?UF4Qugi0iNYoTAQEB?= X-IPAS-Result: =?us-ascii?q?A0CQAQCJScBYf7FSfUpeHQEFAQsBhTwHg1mBBJpVl0WGIgK?= =?us-ascii?q?COQdCFQECAQEBAQEBARMBAQkLCwgmMYUWAQICASMdARseAwELBgUEBzcCAiEBA?= =?us-ascii?q?REBBQEcBhOJZgEDDQikCT+MA4IEBQEcgwkFg18KGScNVYJjAQEIAQEBARwCBhK?= =?us-ascii?q?LK4JRhQmCXwWQV4slOooeg2+EK5EgilSHIxQegRU1gSUiFR9UF4Qugi0iNYoTA?= =?us-ascii?q?QEB?= X-IronPort-AV: E=Sophos;i="5.36,265,1486422000"; d="scan'208,217";a="263738079" Received: from mail-ot0-f177.google.com ([74.125.82.177]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 08 Mar 2017 19:15:08 +0100 Received: by mail-ot0-f177.google.com with SMTP id x37so38383582ota.2 for ; Wed, 08 Mar 2017 10:15:08 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=s2z7qxILg/knWMUuhdUwWvtUBvr1oZ+pW4LaN5AD9Ho=; b=Z4Dc6xMU/oV4kAKahc7d2Z0JzuHZzzdnZCe+kCOu7+oLJBJIbd/ccdmnSiYR+vMjdI nXYf6Qiohixxcb/e9jtbK3nCAPY7DqYOBJHuV6z9ly87wSzKPp6V4SyYmvQZvZJ/eyk2 fI32LkDF3OzN5xmO7R8Lqs0csOBe4a3fIwUG3bCa7pcthTdcgKQlSeth34uuKqqb5Ujf PXUmXD/2v01f2qX3YImI9ATZx7ZeTnVl9/kLESAqmj5iBSzLKOyX3DDIf0S/Ct/HTg20 CBXJYdSUCPjchNyX12vi71+AAql/L/IJKKfVbIyeN7VIVLGxjnbxySMhjUuwkRguQHs1 +iWw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=s2z7qxILg/knWMUuhdUwWvtUBvr1oZ+pW4LaN5AD9Ho=; b=UMn0XzHxyU4oVa+BwhLQxV2c/fHVo7kONXTQqPKSEe/vZ6q2jZyuGkigq5Q6zWMN1J jOVkVXvIuDQbK6S2kA2Vnjdg7VPCQUd9QZQ7lM3LVZHoXlJgVsIbsNB6BemCfl1C30ie NLFZ7DBX2pEXOZLM4fDv7gCqyfanb7gtug9sVtPFX2J9MgG4lyXMhEaSVfFeTyEgtNpi TM0Gm0JBDzjgna0mT8B+PSNyGtKZ8kpi11GrTlo9SRSCwxDX1Kad/8nG/qGxStF4IAEf Eja6rulqR0R4L8h42dSvTkxzcu83jNecacy4lf547LzgJl6OHBmilkQ22pW0ZdTHSA2o u4Wg== X-Gm-Message-State: AMke39mNsmMTj6Aqmmv5+m695QCYoHLRCgMwLU1VK/dGNqpxq1cIw/3i+LfTjqzrbh1o6S1FKEUMKAWLvJuJsA== X-Received: by 10.37.36.86 with SMTP id k83mr2182157ybk.130.1488996906698; Wed, 08 Mar 2017 10:15:06 -0800 (PST) MIME-Version: 1.0 Received: by 10.13.213.144 with HTTP; Wed, 8 Mar 2017 10:15:06 -0800 (PST) In-Reply-To: References: From: Kenneth Adam Miller Date: Wed, 8 Mar 2017 13:15:06 -0500 Message-ID: To: caml users Content-Type: multipart/alternative; boundary=001a113d46ecb211ef054a3c1b54 Subject: Re: [Caml-list] OCamlgraph Strongly Connected components --001a113d46ecb211ef054a3c1b54 Content-Type: text/plain; charset=UTF-8 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? > --001a113d46ecb211ef054a3c1b54 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I found what I was looking for, sorry.

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

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 thin= k that it should:

module G =3D Imperative.Digraph.ConcreteBidir= ectional(struct=C2=A0
...
end)

m= odule StrongComponents =3D Components.Make(G)

= let cfg =3D G.create () in
Insn_cfg.G.add_edge insn_cfg zero one;= =C2=A0
(* just any two nodes above; that's all you need t= o know *)
let components =3D Insn_cfg.StrongComponents.scc_l= ist cfg in
assert_equal [] components

(* Failure above= ! Why?? *)

The way I understand strongly connected components to wor= k is that, for any node to be in a component, there must be a path from its= elf to itself. The following should yield [zero ; one] ---

let = cfg =3D G.create () in
Insn_cfg.G.add_edge insn_cfg zero one;=C2= =A0
Insn_cfg.G.add_edge insn_cfg one zero;=C2=A0
(*= just any two nodes above; that's all you need to know *)
let= components =3D Insn_cfg.StrongComponents.scc_list cfg in
assert_equal [zero; one] components (* don't care about order here se= riously *)


Is there a module or utility function that I could us= e 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?

--001a113d46ecb211ef054a3c1b54--