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 mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id EDB847FA32 for ; Mon, 13 Mar 2017 13:19:20 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=kennethadammiller@gmail.com; spf=Pass smtp.mailfrom=kennethadammiller@gmail.com; spf=None smtp.helo=postmaster@mail-yw0-f179.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of kennethadammiller@gmail.com) identity=pra; client-ip=209.85.161.179; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="kennethadammiller@gmail.com"; x-sender="kennethadammiller@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of kennethadammiller@gmail.com designates 209.85.161.179 as permitted sender) identity=mailfrom; client-ip=209.85.161.179; receiver=mail3-smtp-sop.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 (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-yw0-f179.google.com) identity=helo; client-ip=209.85.161.179; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="kennethadammiller@gmail.com"; x-sender="postmaster@mail-yw0-f179.google.com"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3AYZ/K1xxhR2Ue8o/XCy+O+j09IxM/srCxBDY+r6Qd?= =?us-ascii?q?2+gRIJqq85mqBkHD//Il1AaPBtSGra8YwLGJ+4nbGkU4qa6bt34DdJEeHzQksu?= =?us-ascii?q?4x2zIaPcieFEfgJ+TrZSFpVO5LVVti4m3peRMNQJW2aFLduGC94iAPERvjKwV1?= =?us-ascii?q?Ov71GonPhMiryuy+4ZPebgFIiTanYb5/Ixq6oAvTu8ILnYZsN6E9xwfTrHBVYe?= =?us-ascii?q?pW32RoJVySnxb4+Mi9+YNo/jpTtfw86cNOSL32cKskQ7NWCjQmKH0169bwtRbf?= =?us-ascii?q?VwuP52ATXXsQnxFVHgXK9hD6XpP2sivnqupw3TSRMMPqQbwoXzmp8rxmQwH0hi?= =?us-ascii?q?gZKzE58XnXis1ug6JdvBKhvAF0z4rNbI2IKPZyYqbRcNUHTmRDQ8lRTTRMDYGy?= =?us-ascii?q?b4UPAeQPPvtWoZfhqFYVtxSyGROhCfnzxjNUhHL727Ax3eQ7EQHB2QwtB9cAv2?= =?us-ascii?q?rSrNXzKqgSTeC1x7TUwDredfxW3Cr25o/JchAlpfGDQ6hwetfWxEksCQzFiFOQ?= =?us-ascii?q?ppL5PzOVzOsCrnKU7+9lVeKuj24nrx9+oiK0y8cjj4nGnIMVylTe+Splx4Y1IM?= =?us-ascii?q?S1RUhmatCnCJtdrz+WO5dyT884QGxluDw2xqAHtJKmZiQG1ZYqyhrZZveaaYaH?= =?us-ascii?q?+AjjW/yUITpghHJqZra/hxGq/Eil0OL8V8203E9KrytLjtXAr34N2wHR58WDUP?= =?us-ascii?q?d98UCh2TGA1wDX9O5IO1w7la3eK5I5w74wkIQcsVjbEyPohEn7iLWae0Yk9+Sy?= =?us-ascii?q?9ujqY6jqqoWBO4J2jgzyKqEulda+AeQ8PAgORW+b+eGk2b3g40L5RrNKgeMqkq?= =?us-ascii?q?nZqp/VON4Upqu8Aw9U1oYj7wiwDy293dQXmHkINlNFeBadg4f1PFHOJej0De2j?= =?us-ascii?q?jFS0jDdr2/fGM6X9DZrXK3jDlK7tfbJ8605H1Ao+1stf5pJRCrEZOv3/QE7xtN?= =?us-ascii?q?rCDh84KQO42ejnCM8unr8ZDEiCBOe8MafWrliP6qp7KeyNYIsKvzHxA/os4fP1?= =?us-ascii?q?kWU0lENbdq6si8g5cne9S9drJUOUfXqkq9sIFC8vvw46Qfai3F6PVzhee3a7U6?= =?us-ascii?q?s54zA/DI+8JYjGT4GpxreG2XHoTdVtemlaBwXUQj/TfIKeVqJJMXrKLw=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0CKAAAUjsZYhrOhVdFdGgEBAQECAQEBA?= =?us-ascii?q?QgBAQEBFgEBAQMBAQEJAQEBhREHg1mBBIkKkU6VO4IOhiICgkkHPxgBAQEBAQE?= =?us-ascii?q?BAQEBARIBAQEICwsIKC+CMyIBgj8BAQEBAgEjHQEbFgcBAwELBgULAwoqAgIhA?= =?us-ascii?q?QERAQUBHAYTiWcBAw0Iogc/jAOCBAUBHIMJBYNPChknDVWCSgEBAQEBAQQBAQE?= =?us-ascii?q?BAQEaAgYSiyuCUYUJgl8FnAc6ih6Db4QskSWKVYcmFB+BFR+BPCMWH1YXhDEPE?= =?us-ascii?q?QyBfyQ1iVMBAQE?= X-IPAS-Result: =?us-ascii?q?A0CKAAAUjsZYhrOhVdFdGgEBAQECAQEBAQgBAQEBFgEBAQM?= =?us-ascii?q?BAQEJAQEBhREHg1mBBIkKkU6VO4IOhiICgkkHPxgBAQEBAQEBAQEBARIBAQEIC?= =?us-ascii?q?wsIKC+CMyIBgj8BAQEBAgEjHQEbFgcBAwELBgULAwoqAgIhAQERAQUBHAYTiWc?= =?us-ascii?q?BAw0Iogc/jAOCBAUBHIMJBYNPChknDVWCSgEBAQEBAQQBAQEBAQEaAgYSiyuCU?= =?us-ascii?q?YUJgl8FnAc6ih6Db4QskSWKVYcmFB+BFR+BPCMWH1YXhDEPEQyBfyQ1iVMBAQE?= X-IronPort-AV: E=Sophos;i="5.36,159,1486422000"; d="scan'208,217";a="216538850" Received: from mail-yw0-f179.google.com ([209.85.161.179]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 13 Mar 2017 13:18:47 +0100 Received: by mail-yw0-f179.google.com with SMTP id v198so57419889ywc.2 for ; Mon, 13 Mar 2017 05:18:47 -0700 (PDT) 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 :cc; bh=somLmc0KLrOEDOUugDeKZYOBL82QWVfQY81cihBI3KM=; b=A1iCAfbGOG2y7UUDQmCNbgZkPXC8AapPyxWQS6KHCVajdBxtLD2cDgMnzbYpREOXwX fETI9KU5IkXLNSNd6CMTsG5Iae5Qifb6WUdQSLMWLi5OfYVxxKTG+msgbiS7p8sVpHWo zuRqty2Bl8/6yDV53pnhA5AK3d6J219NYAFE4a5Inc6szju2JI3rZ8ZgC+Gb76qL2bMk W6Q63FRQ2m0lOX/O37qdB9ZKNLwqocOFJo2n7OPyHTnDKXa1cauGUOwRACVboCw8k1Ca 3zgJqhy2wmoq3Jj1IurAqa7D+U/Pj7RSLc8JdtRqwlOPoAbOdMqxYIBycKwXej9vvdsJ juCQ== 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:cc; bh=somLmc0KLrOEDOUugDeKZYOBL82QWVfQY81cihBI3KM=; b=ApVdqFvEHmvhWbvBY/5GP/c1E00kmbrfrWwKssIAaVxhJmp8gWah4/Au0pB41DEFXk 8aVoknTrmqViLUxhlQboUF4H4C3561TFee5/tkhDc13cu5YfgqVDLl/45K0L2cZoerHs 0ENSOpjqMoD28EqTOdJIzfRIMl2kWCcfuI9PjGptDj7zp3zau/qEJ5l3kFwK/9Yh6pL0 NsuRcVdr8QNEEtk3i6i/AHbXU8uE2/LRgnCCQ0l+Uub8c9YcpDtWGQ5TC7B+aOeqdhxM UceZMnyZ8y50FyaYrAn9DeZ7QYcS7FqXndQ7qBePUaDs0SFOI5qF2RgwOo7v9uQal3F4 Hbfw== X-Gm-Message-State: AMke39m0c3bBSaXx46bXURpevXAAjQSoAoZSJ0kNkqeg41x18aVXCdPHU0RXqt7lE4vUz+w+2hTfaTT46pqFdA== X-Received: by 10.129.132.73 with SMTP id u70mr16877951ywf.231.1489407526155; Mon, 13 Mar 2017 05:18:46 -0700 (PDT) MIME-Version: 1.0 Received: by 10.13.213.144 with HTTP; Mon, 13 Mar 2017 05:18:45 -0700 (PDT) Received: by 10.13.213.144 with HTTP; Mon, 13 Mar 2017 05:18:45 -0700 (PDT) In-Reply-To: References: From: Kenneth Adam Miller Date: Mon, 13 Mar 2017 08:18:45 -0400 Message-ID: To: Ben Millwood Cc: caml users Content-Type: multipart/alternative; boundary=94eb2c07ade485c1a5054a9bb6d9 Subject: Re: [Caml-list] OCamlgraph Strongly Connected components --94eb2c07ade485c1a5054a9bb6d9 Content-Type: text/plain; charset=UTF-8 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" 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 > 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? >>> >> >> > --94eb2c07ade485c1a5054a9bb6d9 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I actually just meant that I did not want single node siz= ed components, and that I would operate over the others, dropping those.
What I was getting effectively i= ncluded 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 nod= es. It was failing to remove the nodes because of that.

On Mar 13, 2017 5:46 AM, = "Ben Millwood" <bm= illwood@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 i= s conceptually nice because it means that "in the same strongly connec= ted component" is an equivalence relation / partition of the graph.=C2= =A0

On 9 March 201= 7 at 02:15, Kenneth Adam Miller <kennethadammiller@gmail.com= > wrote:
I fou= nd 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-emp= ty list, and I don't think that it should:

module G =3D Imperati= ve.Digraph.ConcreteBidirectional(struct=C2=A0
...
en= d)

module StrongComponents =3D Components.Make(G)<= br>

let cfg =3D G.create () in
Insn_cfg.= G.add_edge insn_cfg zero one;=C2=A0
(* just any two nodes abo= ve; that's all you need to know *)
let components =3D Insn_cf= g.StrongComponents.scc_list cfg in
assert_equal [] compo= nents

(* Failure above! Why?? *)

The way I understand strongl= y 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 [zer= o ; one] ---

let cfg =3D G.create () in
Insn_cfg.G.ad= d_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 n= eed to know *)
let components =3D Insn_cfg.StrongComponents.scc_<= wbr>list cfg in
assert_equal [zero; one] components (* don= 9;t care about order here seriously *)


Is there a module or util= ity 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 l= ike a dominator, to check to see that every node dominates itself or some s= uch? Also, why does strongly connected components behave unexpectedly here?= Is it my understanding that's off, or that the implementation is one a= mong several definitions of strongly connected component?


--94eb2c07ade485c1a5054a9bb6d9--