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.8 required=5.0 tests=DNS_FROM_RFC_POST,SPF_NEUTRAL autolearn=disabled version=3.1.3 X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by yquem.inria.fr (Postfix) with ESMTP id 4E104BC37 for ; Sat, 8 Aug 2009 15:35:50 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtkCAJwcfUrRVdndimdsb2JhbACaCz8BAQEICwwHEQWhPYEij34BAwIEhBMFigs X-IronPort-AV: E=Sophos;i="4.43,346,1246831200"; d="scan'208";a="30930222" Received: from mail-gx0-f221.google.com ([209.85.217.221]) by mail2-smtp-roc.national.inria.fr with ESMTP; 08 Aug 2009 15:35:31 +0200 Received: by gxk21 with SMTP id 21so2822293gxk.3 for ; Sat, 08 Aug 2009 06:35:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from :user-agent:mime-version:to:cc:subject:references:in-reply-to :content-type:content-transfer-encoding; bh=FV5sRqwf6yw1XJrl8Fjyp9csX8oXrwuYY7/fXQj5xW4=; b=ZrfP6SE4s4r/AHBmLe6RAcQyjHABT+l5W14UW3Zk7pYQd7KvWwoOazS2FcSAsWutUK tJ+T9NcN11WgMzrV/v/mSBPu4/nIBVNq7YX83iqGOtPv8uUrkGMGlQKB05wraXg3bXMo yXYkt2lPmD+p33wVE69fKcNQ7xH911n4g5hg8= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; b=Egg9QHS9vLnj9qW3nb+Nv5YtdHB6bytc17VJwuPsWBHsMTNdn5/OXYr14EwwvCKq26 3gD6P/o/zqLTNJl9BQ7eWDZc2OV4lqCccMOCHpPW2eZ66vMvp94vN2YHSxgNet/ef05V ys/YxJH291fxHBZZL8vDat2e6fmeRS50cX7e8= Received: by 10.90.32.9 with SMTP id f9mr1941329agf.102.1249738530539; Sat, 08 Aug 2009 06:35:30 -0700 (PDT) Received: from ?192.168.1.100? ([72.44.99.175]) by mx.google.com with ESMTPS id 5sm1863453agc.7.2009.08.08.06.35.29 (version=TLSv1/SSLv3 cipher=RC4-MD5); Sat, 08 Aug 2009 06:35:29 -0700 (PDT) Message-ID: <4A7D7F1F.8040006@gmail.com> Date: Sat, 08 Aug 2009 09:35:27 -0400 From: Edgar Friendly User-Agent: Thunderbird 2.0.0.22 (X11/20090608) 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=UTF-8 Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; moderately:01 work-around:01 node:01 nodes:01 node:01 caching:01 edgar:98 wrote:01 graph:01 graph:01 caml-list:01 edges:01 benjamin:01 arbitrary:02 data:02 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|)). > > Thanks, > Ben > What you're asking is similar to the problem of finding the predecessor of an arbitrary node in a singly-linked-list. You have no option but to scan the whole list to find its predecessor. If you had a doubly-linked-list, predecessor lookups would work easily, but that's a different data structure, with much more overhead. When you talk about "predecessors", I assume you're using a directed graph, and want to know which nodes have edges to a given node. if your graph is static, you could build lookup tables, pregenerating this information and caching it. Even with a dynamic graph, maintaining lookup tables on this info shouldn't be too hard. Does that help? E