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 4788D800DB for ; Wed, 8 Mar 2017 19:09:34 +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-f178.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.178; 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.178 as permitted sender) identity=mailfrom; client-ip=74.125.82.178; 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-f178.google.com) identity=helo; client-ip=74.125.82.178; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="kennethadammiller@gmail.com"; x-sender="postmaster@mail-ot0-f178.google.com"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3ACup/GRwAQS4HYYnXCy+O+j09IxM/srCxBDY+r6Qd?= =?us-ascii?q?0eoWIJqq85mqBkHD//Il1AaPBtSGra4YwLOO7uigATVGusnR9ihaMdRlbFwst4?= =?us-ascii?q?Y/p0QYGsmLCEn2frbBThcRO4B8bmJj5GyxKkNPGczzNBX4q3y26iMOSF2kbVIm?= =?us-ascii?q?bre9JomHhM2y06iv4JDJeE0cjzO4ZfZ2LQ6qhQTXrMgfx4V4fPUf0BzM91hFfe?= =?us-ascii?q?Jb2WMgDF6aml7Z58O08YQrpyddvfQs685JXaz/eqU8SbFCJDsjOmExosbssE+Q?= =?us-ascii?q?HkO0+nIAXzBOwVJzCA/f4USiUw=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BRAgBkSMBYf7JSfUpeHQEFAQsBGAEFA?= =?us-ascii?q?QsBhREHg1mBBKNQjD2CDQyIUQdBFgEBAQEBAQEBAQEBEgEBCQsLCCYxgjMggmw?= =?us-ascii?q?dARseAxIJBzcCJAERAQUBIol5AQMVoEGDQz+MA4IEBQEcgwkFg2AKGScNVYMNA?= =?us-ascii?q?gYSkksMLoJfBZBXi1+KHogakSCRdxQegRUmCoEqIhUfVBeELoItIjWKEwEBAQ?= X-IPAS-Result: =?us-ascii?q?A0BRAgBkSMBYf7JSfUpeHQEFAQsBGAEFAQsBhREHg1mBBKN?= =?us-ascii?q?QjD2CDQyIUQdBFgEBAQEBAQEBAQEBEgEBCQsLCCYxgjMggmwdARseAxIJBzcCJ?= =?us-ascii?q?AERAQUBIol5AQMVoEGDQz+MA4IEBQEcgwkFg2AKGScNVYMNAgYSkksMLoJfBZB?= =?us-ascii?q?Xi1+KHogakSCRdxQegRUmCoEqIhUfVBeELoItIjWKEwEBAQ?= X-IronPort-AV: E=Sophos;i="5.36,265,1486422000"; d="scan'208,217";a="263737347" Received: from mail-ot0-f178.google.com ([74.125.82.178]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 08 Mar 2017 19:09:33 +0100 Received: by mail-ot0-f178.google.com with SMTP id i1so38069671ota.3 for ; Wed, 08 Mar 2017 10:09:33 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=X7qIEAHaQN55xFEPXAw8IQb149FaeHeilcn4riu4cIQ=; b=Gynr1cDSRgh25slyYVVtrTm7IEcs0wimrWYE5h4BK/O15HksIXbJUl6cinY1Kp6rxw dBW/uzaBZQxfjXR5TgYdEmufsEHWcBNPP3T7fwZcJ2CxfsXvNj4r31pIEYinmPVQdk+a T4jP+f+rv+W/cCj5lx2vDjIof8FjElJj670vKvbWgIChaxDaopiydpPljfPF2s5L6mIq QqsyXvBLovHg/UBF3qxCTRDWcFzHTD6mdXcWaBrimFxo0JMhTXduqa0MNYLafXsw7P+E 4n0r27YXMMZGIW4vq/OnuERGp03xl5YhfpQWI+GbIZ4Y47OgPJKCcyEn2KezSsxp61L0 72zg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=X7qIEAHaQN55xFEPXAw8IQb149FaeHeilcn4riu4cIQ=; b=QoTFzDvx0Ii0COS0bpnWZmjas7tgCMJAkxImR+lBjQOtME1DBuGB4daBbKPtbT9Ak8 7T9NxOOoBnHjYKOq4mZqAcBym/+YGZZo4+yAJr24Zat7pleGv6V9WXS124KoH1+q8Dzk 7tn1zStPmhHfmQQh9BDSoq7DNOt4sTa3BVPC5roZO8iZ65nNYq0t5WC6gr9NIlXi1ktB uTgq+lSVSiCg1st8wY/UFNsnCU+apRljNlXRNfYYK+738gJoJlkrs5OWUgViVyAt4G5K cEP5VbA4EwC++Kp55FDbflLduTbizrm5k4yaBP5BCsrtzMOBmq4YQD5FbbvWgy64sZ85 0rMA== X-Gm-Message-State: AMke39n3XKYPPK5xrwUoqnu2uqe94WlAprujV3hhltALXEp5W0pE0WhrOux+xpwKbYB6HXWOROegmbg04KiPYg== X-Received: by 10.37.85.70 with SMTP id j67mr2134126ybb.192.1488996571865; Wed, 08 Mar 2017 10:09:31 -0800 (PST) MIME-Version: 1.0 Received: by 10.13.213.144 with HTTP; Wed, 8 Mar 2017 10:09:31 -0800 (PST) From: Kenneth Adam Miller Date: Wed, 8 Mar 2017 13:09:31 -0500 Message-ID: To: caml users Content-Type: multipart/alternative; boundary=001a113ff858bd35c9054a3c07de Subject: [Caml-list] OCamlgraph Strongly Connected components --001a113ff858bd35c9054a3c07de Content-Type: text/plain; charset=UTF-8 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? --001a113ff858bd35c9054a3c07de Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
The following code produces a non-empty list, and I don= 9;t think that it should:

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

module StrongComponents =3D Components.Make(G)

let cfg =3D G.create () in
Insn_cfg.G.add_edge insn_cfg zero o= ne;=C2=A0
(* just any two nodes above; that's all you nee= d to know *)
let components =3D Insn_cfg.StrongComponents.scc_lis= t 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 itsel= f to itself. The following should yield [zero ; one] ---

let cf= g =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
(* ju= st any two nodes above; that's all you need to know *)
let co= mponents =3D 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 w= ould expect the above example to behave, or do I need to filter the lists r= eturned by components using something like a dominator, to check to see tha= t every node dominates itself or some such? Also, why does strongly connect= ed components behave unexpectedly here? Is it my understanding that's o= ff, or that the implementation is one among several definitions of strongly= connected component?
--001a113ff858bd35c9054a3c07de--