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.0 required=5.0 tests=none 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 99B3BBC37 for ; Sat, 8 Aug 2009 22:16:32 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AmcCAHF5fUpCbwQZkGdsb2JhbACaSgEBAQEJCQwHEwSkPoZmiE6EFwU X-IronPort-AV: E=Sophos;i="4.43,347,1246831200"; d="scan'208";a="32224871" Received: from out1.smtp.messagingengine.com ([66.111.4.25]) by mail3-smtp-sop.national.inria.fr with ESMTP; 08 Aug 2009 22:16:31 +0200 Received: from compute2.internal (compute2.internal [10.202.2.42]) by gateway1.messagingengine.com (Postfix) with ESMTP id 3961B1861; Sat, 8 Aug 2009 16:16:30 -0400 (EDT) Received: from heartbeat1.messagingengine.com ([10.202.2.160]) by compute2.internal (MEProxy); Sat, 08 Aug 2009 16:16:30 -0400 X-Sasl-enc: RsB/8cs3VOsxCj3VCV/Hy1Kz3Td78iafAzAw5q2Q6gfm 1249762589 Received: from eplet-2.dyn.cs.washington.edu (eplet-2.dyn.cs.washington.edu [128.208.3.25]) by mail.messagingengine.com (Postfix) with ESMTPSA id 94397274BB; Sat, 8 Aug 2009 16:16:29 -0400 (EDT) Cc: caml-list@inria.fr Message-Id: <2877D20A-1008-4CD0-B1B6-F2EA444B2A88@cs.washington.edu> From: Benjamin Ylvisaker To: Edgar Friendly In-Reply-To: <4A7D7F1F.8040006@gmail.com> Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit Mime-Version: 1.0 (Apple Message framework v935.3) Subject: Re: [Caml-list] ocamlgraph predecessors Date: Sat, 8 Aug 2009 13:16:28 -0700 References: <4EC4528F-4993-482F-8ECB-ED6848C3FC4D@cs.washington.edu> <4A7D7F1F.8040006@gmail.com> X-Mailer: Apple Mail (2.935.3) X-Spam: no; 0.00; moderately:01 work-around:01 node:01 nodes:01 node:01 caching:01 mutable:01 symmetric:01 edgar:98 wrote:01 wrote:01 graph:01 graph:01 caml-list:01 functions:01 On Aug 8, 2009, at 6:35 AM, Edgar Friendly wrote: > 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 The list analogy seems like a little bit of a stretch to me. I understand the point, but I think most programmers would expect predecessor and successor operations in a generic mutable directed graph library to be symmetric in every way, including performance. I'm thinking about making a thin wrapper around ocamlgraph that makes "internal" edges in both directions with tags to distinguish them whenever the user creates an "external" edge. All the wrapper graph traversal functions would only use ocamlgraph's successor functions, and then use the tags to distinguish which edges are really supposed to point in which direction. It's a bit of a hassle, and will roughly double the amount of storage required for edges, but I need predecessor access in my application, and the O(|V|) performance is really painful for big graphs. Ben