From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.1.3 (2006-06-01) on yquem.inria.fr X-Spam-Level: ** X-Spam-Status: No, score=2.5 required=5.0 tests=AWL,RCVD_IN_BL_SPAMCOP_NET, SPF_SOFTFAIL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 5239EBC54 for ; Tue, 25 Aug 2009 16:22:36 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnUCAO+Pk0qEqOABmWdsb2JhbACbDgEBAQEBCAsKBxO8UYQaBQ X-IronPort-AV: E=Sophos;i="4.44,272,1249250400"; d="scan'208";a="45334537" Received: from oxalide-out.extra.cea.fr ([132.168.224.1]) by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 25 Aug 2009 16:22:33 +0200 Received: from pisaure.intra.cea.fr (pisaure.intra.cea.fr [132.166.88.21]) by oxalide.extra.cea.fr (8.14.2/8.14.2/CEAnet-Internet-out-2.0) with ESMTP id n7PEMWS5006394 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Tue, 25 Aug 2009 16:22:32 +0200 Received: from muguet1.intra.cea.fr (muguet1.intra.cea.fr [132.166.192.6]) by pisaure.intra.cea.fr (8.14.2/8.14.2) with ESMTP id n7PEMW7E000392; Tue, 25 Aug 2009 16:22:32 +0200 (envelope-from Julien.Signoles@cea.fr) Received: from [132.166.132.51] (is010215.intra.cea.fr [132.166.132.51]) by muguet1.intra.cea.fr (8.13.8/8.13.8/CEAnet-Intranet-out-1.1) with ESMTP id n7PEMV27027867; Tue, 25 Aug 2009 16:22:31 +0200 Message-ID: <4A93F3A7.5050009@cea.fr> Date: Tue, 25 Aug 2009 16:22:31 +0200 From: Julien Signoles User-Agent: Thunderbird 2.0.0.23 (X11/20090817) MIME-Version: 1.0 To: Edgar Friendly Cc: caml list Subject: Re: [Caml-list] ocamlgraph predecessors References: <4EC4528F-4993-482F-8ECB-ED6848C3FC4D@cs.washington.edu> <4A7D7F1F.8040006@gmail.com> <2877D20A-1008-4CD0-B1B6-F2EA444B2A88@cs.washington.edu> <4A7EE39C.1030803@gmail.com> In-Reply-To: <4A7EE39C.1030803@gmail.com> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam: no; 0.00; signoles:01 signoles:01 lri:01 edgar:98 graph:01 graph:01 caml-list:01 cea:01 exists:05 implement:06 merged:06 table:93 oper:07 lookup:07 efficient:07 Edgar Friendly a écrit : > This is another solution to the slow predecessor performance, and will > have different performance characteristics than predecessor > lookup-tables. Note that the lookup table solution is isomorphic to > building a second graph with all the arrows reversed, and using the > efficient successor operations on it. Maybe this'll be easier than > keeping a merged graph. Maybe not. This solution should be easy to implement with ocamlgraph because this operation already exists in ocamlgraph : that's the "mirror" function. See here : http://ocamlgraph.lri.fr/doc/Oper.Make.html -- Julien Signoles