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=0.7 required=5.0 tests=AWL,RCVD_IN_BL_SPAMCOP_NET autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by yquem.inria.fr (Postfix) with ESMTP id AC9F1BBAF for ; Wed, 26 Aug 2009 08:54:32 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: ApAEAGN5lEqBrw8EgWdsb2JhbACbEAEBFiS8Q4QaBYpM X-IronPort-AV: E=Sophos;i="4.44,278,1249250400"; d="scan'208";a="33213495" Received: from ext.lri.fr ([129.175.15.4]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/ADH-AES256-SHA; 26 Aug 2009 08:54:32 +0200 Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id ECD0EA4418; Wed, 26 Aug 2009 08:54:31 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at lri.fr Received: from ext.lri.fr ([127.0.0.1]) by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id HTbPLy-zoJ+j; Wed, 26 Aug 2009 08:54:31 +0200 (CEST) Received: from [129.175.4.132] (lri4-132 [129.175.4.132]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ext.lri.fr (Postfix) with ESMTP id D391CA4407; Wed, 26 Aug 2009 08:54:31 +0200 (CEST) Message-ID: <4A94DC3D.9060000@lri.fr> Date: Wed, 26 Aug 2009 08:54:53 +0200 From: =?ISO-8859-1?Q?Jean-Christophe_Filli=E2tre?= User-Agent: Thunderbird 1.5.0.14ubu (X11/20080306) MIME-Version: 1.0 To: Benjamin Ylvisaker Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] ocamlgraph predecessors References: <4EC4528F-4993-482F-8ECB-ED6848C3FC4D@cs.washington.edu> In-Reply-To: <4EC4528F-4993-482F-8ECB-ED6848C3FC4D@cs.washington.edu> X-Enigmail-Version: 0.94.2.0 OpenPGP: url=http://www.lri.fr/~filliatr/mykey.asc Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 moderately:01 work-around:01 workarounds:01 memoize:01 externally:01 deliberate:98 wrote:01 graph:01 graph:01 caml-list:01 imperative:01 benjamin:01 Hi, Benjamin Ylvisaker wrote: > I have been using ocamlgraph for a while, and have been generally happy > with it. I experienced some poor performance with moderately large > graphs (10-100k vertices) recently, which led me to look through the > source code a little. It seems that doing anything with the > predecessors of a vertex, even just getting a list of them, requires > scanning through all the vertices in a graph. This seems a little crazy > to me. Am I missing something? Is there some kind of work-around that > gives reasonable performance for predecessor operations (i.e. not O(|V|)). Not providing predecessors in constant time was a deliberate choice in Ocamlgraph. (A graph is basically a map which binds any vertex to the set of its successors, and that's it.) If you need efficient access to the predecessors, you have several workarounds: - implement your own graph data structure; after all, ocamlgraph was designed to clearly separate data structures and algorithms, so that you will still be able to use graph algorithms on your own graphs. - use the graph data structure Imperative.Digraph.ConcreteBidirectional, which is the only graph data structure in Ocamlgraph providing predecessors in constant time; it is actually the contribution of a user (Ted Kremenek) who experienced the same need as yourself. - memoize the results of the predecessors function (either in a modified version of the data structure or externally if your algorithm allows it). Hope this helps, -- Jean-Christophe