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 7F8367FA32 for ; Mon, 13 Mar 2017 10:46:04 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=bmillwood@janestreet.com; spf=Pass smtp.mailfrom=bmillwood@janestreet.com; spf=None smtp.helo=postmaster@mxout1.mail.janestreet.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of bmillwood@janestreet.com) identity=pra; client-ip=38.105.200.78; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="bmillwood@janestreet.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of bmillwood@janestreet.com designates 38.105.200.78 as permitted sender) identity=mailfrom; client-ip=38.105.200.78; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="bmillwood@janestreet.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@mxout1.mail.janestreet.com) identity=helo; client-ip=38.105.200.78; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="bmillwood@janestreet.com"; x-sender="postmaster@mxout1.mail.janestreet.com"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3A3lZuCRFkEtCSC29y6qelB51GYnF86YWxBRYc798d?= =?us-ascii?q?s5kLTJ7zpcWwAkXT6L1XgUPTWs2DsrQf2reQ7vyrATJIyK3CmUhKSIZLWR4BhJ?= =?us-ascii?q?detC0bK+nBN3fGKuX3ZTcxBsVIWQwt1Xi6NU9IBJS2PAWK8TW94jEIBxrwKxd+?= =?us-ascii?q?KPjrFY7OlcS30P2594HObwlSijewZbN/IA+2oAjeucUanYpvIbstxxXUpXdFZ/?= =?us-ascii?q?5Yzn5yK1KJmBb86Maw/Jp9/ClVpvks6c1OX7jkcqohVbBXAygoPG4z5M3wqBnM?= =?us-ascii?q?VhCP6WcGUmUXiRVHHQ7I5wznU5jrsyv6su192DSGPcDzULs5Vyiu47ttRRT1ky?= =?us-ascii?q?oMKSI3/3/LhcxxlKJboQyupxpjw47PfYqZMONycr7Bcd8GQGZMWNtaWS5cDYOm?= =?us-ascii?q?d4YADeQBM+ZWoYf+ulUAswexCBK2C+/z0DJFnGP60bE43uknDArI3BYgH9ULsH?= =?us-ascii?q?nMsdj6KqESWv2ywqnJyTXDa/1X2TD66IfVbxsspuqDXbdxccrVzUkuGQTFjlKN?= =?us-ascii?q?poH+PTOazOINvHaA7+p8T+KglXAoqx1rrjezwccsj5DEi4QIwV7H7SV02Ig4KN?= =?us-ascii?q?6iREJmfdKpEIFcuz+GO4dqWM8vQWJltD4kxrEavZO3ZisHxZQ9yxLBdvCKcJKE?= =?us-ascii?q?7xD+WOuXPDx2nmhqeKiliBa36UWgyvPzVs2z0FtSqypEnd7Mtm0R1xDO8MSHT+?= =?us-ascii?q?Fy/kal2TqV1QDc8OdELl4vlarHMZ4u3KA/loYJvUvfGS/2nV36jK6Qdko65uil?= =?us-ascii?q?8+rqb7b8qpOBK4N5ihvyProylsCjG+g1MAsDU3Ce+eum1b3j+UP5QK9Njv0ziq?= =?us-ascii?q?TWq5XaJcUfpq69DQ5V1YEj5AukAjekytsYm2cILElZeBKdkYfmJU3OLOrkAve4?= =?us-ascii?q?hlSgiC1ryOzePr39HpXNKWDOn6v7crZ4705Q0Q4zzdFE55JIEbwBO/LyWkrptN?= =?us-ascii?q?PCFBM5Mgq0w/zmCNpnzI8eV3iPUeelN/bxvFmO6/4va8CAbYpdnTf5L/U/r6rt?= =?us-ascii?q?gHk/lEMddKWg2J4WbHS1BNxpJkyYZTznhdJXQkkQuQ9rZuHswHiDVTpMYHG+F/?= =?us-ascii?q?Y24zA/DJ2hCovrRImrjaedxiq2AttdYWUQWQPEKmvha4jRA6REUymVOMI012Vc?= =?us-ascii?q?DbU=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BqAACBacZYl07IaSZdGgEBAQECAQEBA?= =?us-ascii?q?QgBAQEBFgEBAQMBAQEJAQEBhREHg1mBBIkKc5BdiA6IAIUtgg6GIgKCQgc/GAE?= =?us-ascii?q?BAQEBAQEBAQEBEgEBAQEBCBYGV4IzIgGCPwEBAQECASMdAQEwBwEECwsEBw0qA?= =?us-ascii?q?gIhARIBBQEcBhMIiWADDQgDomY/ixtogiaDCAEBBYQbDYMfAQEBAQEBBAEBAQE?= =?us-ascii?q?BAQEBGAgShjyEb4JRhQmCX5Beiy46ih6Db4QskSWKVYcmFB+BFR+BPDkfVhcFh?= =?us-ascii?q?CwggXxoiVMBAQE?= X-IPAS-Result: =?us-ascii?q?A0BqAACBacZYl07IaSZdGgEBAQECAQEBAQgBAQEBFgEBAQM?= =?us-ascii?q?BAQEJAQEBhREHg1mBBIkKc5BdiA6IAIUtgg6GIgKCQgc/GAEBAQEBAQEBAQEBE?= =?us-ascii?q?gEBAQEBCBYGV4IzIgGCPwEBAQECASMdAQEwBwEECwsEBw0qAgIhARIBBQEcBhM?= =?us-ascii?q?IiWADDQgDomY/ixtogiaDCAEBBYQbDYMfAQEBAQEBBAEBAQEBAQEBGAgShjyEb?= =?us-ascii?q?4JRhQmCX5Beiy46ih6Db4QskSWKVYcmFB+BFR+BPDkfVhcFhCwggXxoiVMBAQE?= X-IronPort-AV: E=Sophos;i="5.36,158,1486422000"; d="scan'208,217";a="216515658" Received: from mxout1.mail.janestreet.com ([38.105.200.78]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 13 Mar 2017 10:46:03 +0100 Received: from tot-qpr-mailcore2.delacy.com ([172.27.56.106] helo=tot-qpr-mailcore2) by mxout1.mail.janestreet.com with esmtps (TLSv1.2:DHE-RSA-AES256-GCM-SHA384:256) (Exim 4.84_2) (envelope-from ) id 1cnMYE-0005lb-1P for caml-list@inria.fr; Mon, 13 Mar 2017 05:46:02 -0400 X-JS-Flow: external X-JS-Scanner-attachment: (ok) No attachments Received: by tot-qpr-mailcore2 with JS-mailcore (0.1) (envelope-from ) id BYxmpa-AAADFr-BA; 2017-03-13 05:46:02.033697-04:00 Received: from mail-oi0-f71.google.com ([209.85.218.71]) by mxgoog1.mail.janestreet.com with esmtps (TLSv1.2:AES128-GCM-SHA256:128) (Exim 4.84_2) (envelope-from ) id 1cnMYD-0004KN-VR for caml-list@inria.fr; Mon, 13 Mar 2017 05:46:02 -0400 Received: by mail-oi0-f71.google.com with SMTP id 62so224401301oih.5 for ; Mon, 13 Mar 2017 02:46:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=janestreet.com; s=google; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=eu6Tr0JaG63aW+xLkFBTNBHoufULw+TlZ4F/TNxoZMQ=; b=yjoIDXulCXJDQqmu6cWhlGAkq2wkGuLxZN6TcYkJ+OjFaNZU6glQVQP/dYOPc6qv0P XjTGflmuWmlKuLgK/ICeZaFo5NJ1EW9/0DmRqWpXybilnPrCetKFuHuykrNRr4M0dH4i TJdBx1YY1jAOCnxsnwoPIlPcqrNDz0eJTt/tY= 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=eu6Tr0JaG63aW+xLkFBTNBHoufULw+TlZ4F/TNxoZMQ=; b=oX3K7wWtAqdPe47V7Seq2pjUAaM0ukaoGVKuB6pfl/tkwqwgj14gBHOR1cGKElE6U8 1WcXQKZvXNha7nsD3u+5//mKKSxJvryyVFLmzZyyFImLmIrYqjlkvLHZ8s1tnRBd6tjg 5D1h419nG6/PA2iJycH4OaUtNHBaWMBGciR/SPf0p6jbI3X2gPSUgn3UI6QGzaTPAsF+ yf5kOi7jIH1ofPf8eK67U4KgcpjegHSP5VmSBTlBHc/7d569dK0FbCe6VogvAzqWQhx4 5K7LXbLZbsA7tTBU+JybIsL9PGgfCP/wEYeKsKoKDMAJqtV+s7JRmnVqcl4kTJqEPCv9 l8jQ== X-Gm-Message-State: AMke39kDQ2xe0kiqnRqHP3TkkYfEWh98+jTQMn2e3swRxwJ7wrtcBO8JH6e8HfHvgSBF2hDfNpzsdRFPD/gbKoD3ECuXLKgrk+MV/dKxDnJlIE0fNIM57fkQK9E+46y5Q5QMB0ytnFxGIHVmL980 X-Received: by 10.157.61.164 with SMTP id l33mr18455968otc.274.1489398361547; Mon, 13 Mar 2017 02:46:01 -0700 (PDT) X-Received: by 10.157.61.164 with SMTP id l33mr18455955otc.274.1489398361387; Mon, 13 Mar 2017 02:46:01 -0700 (PDT) MIME-Version: 1.0 Received: by 10.157.42.22 with HTTP; Mon, 13 Mar 2017 02:45:41 -0700 (PDT) In-Reply-To: References: From:Ben Millwood Date: Mon, 13 Mar 2017 17:45:41 +0800 Message-ID: To:Kenneth Adam Miller Cc:caml users Content-Type: multipart/alternative; boundary=001a114708b2429f7b054a9994c0 X-JS-Processed-by: mailcore X-Sender-Copy: hkg-copy Subject: Re: [Caml-list] OCamlgraph Strongly Connected components --001a114708b2429f7b054a9994c0 Content-Type: text/plain; charset=UTF-8 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? >> > > --001a114708b2429f7b054a9994c0 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
This makes sense if you permit paths to be length 0, and t= hus every node automatically has a path to itself. This is conceptually nic= e because it means that "in the same strongly connected component"= ; is an equivalence relation / partition of the graph.=C2=A0

On 9 March 2017 at 02:15, Kennet= h Adam Miller <kennethadammiller@gmail.com> wrote:=
I found what I was look= ing for, sorry.

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

On Wed, Mar 8, 2017 at 1:09 PM, Kenneth= Adam Miller <kennethadammiller@gmail.com> wrote:<= br>
The following code produ= ces a non-empty list, and I don't think that it should:

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

module StrongComponents =3D Compon= ents.Make(G)

let cfg =3D G.create () in
<= div>Insn_cfg.G.add_edge insn_cfg zero one;=C2=A0
(* just any = two nodes above; that's all you need to know *)
let component= s =3D Insn_cfg.StrongComponents.scc_list cfg in
assert_e= qual [] components

(* Failure above! Why?? *)

The way I under= stand 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 shou= ld yield [zero ; one] ---

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


Is there a m= odule or utility function that I could use as I would expect the above exam= ple to behave, or do I need to filter the lists returned by components usin= g something like a dominator, to check to see that every node dominates its= elf or some such? Also, why does strongly connected components behave unexp= ectedly here? Is it my understanding that's off, or that the implementa= tion is one among several definitions of strongly connected component?


--001a114708b2429f7b054a9994c0--