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=1.8 required=5.0 tests=AWL,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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id AE515BBAF for ; Tue, 25 Aug 2009 16:22:28 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AnUCAKSQk0qEqOABmWdsb2JhbACbDgEBAQEBCAsKBxO8OoQaBYpM X-IronPort-AV: E=Sophos;i="4.44,272,1249250400"; d="scan'208";a="34902079" Received: from oxalide-out.extra.cea.fr ([132.168.224.1]) by mail1-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-SHA; 25 Aug 2009 16:22:28 +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 n7PEMJHC006236 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NOT); Tue, 25 Aug 2009 16:22:19 +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 n7PEMJfp032712; Tue, 25 Aug 2009 16:22:19 +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 n7PEMINo027680; Tue, 25 Aug 2009 16:22:19 +0200 Message-ID: <4A93F39A.7090704@cea.fr> Date: Tue, 25 Aug 2009 16:22:18 +0200 From: Julien Signoles User-Agent: Thunderbird 2.0.0.23 (X11/20090817) 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> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 8bit X-Spam: no; 0.00; signoles:01 signoles:01 moderately:01 work-around:01 work-around:01 amortized:01 functor:01 directional:98 cheung:98 directional:98 graph:01 graph:01 caml-list:01 cea:01 imperative:01 Benjamin Ylvisaker a écrit : > 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|)). Actually, looking at the current implementation, accessing predecessors is worse that O(|V|): that is max(O(|V|,O(|E|)). If you use concrete (imperative directional) graphs, the simpler work-around is to use Imperative.Digraph.ConcreteBidirectional as suggested by Kevin Cheung. It uses more memory space (at worse the double) that standard concrete directional graphs. But accessing predecessors is in O(1) amortized instead of max(O(|V|,O(|E|)) and removing a vertex is in O(D*ln(D)) where D is the maximal degree of the graph instead of O(|V|*ln(|V|)). If you don't use this functor, other work-arounds have been suggested in other posts. By the way contributing to ocamlgraph by adding Imperative.Digraph.AbstractBidirectional (for instance) is still possible and welcome :o). -- Julien Signoles