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 mail1-relais-roc.national.inria.fr (mail1-relais-roc.national.inria.fr [192.134.164.82]) by yquem.inria.fr (Postfix) with ESMTP id 6E94DBBAF for ; Sun, 9 Aug 2009 16:56:33 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AoYCAJqAfkrRVdnUkGdsb2JhbACaCz8BAQEBCQkMBxMDoQOBIo5aAQMCBIQUBYoO X-IronPort-AV: E=Sophos;i="4.43,349,1246831200"; d="scan'208";a="34204455" Received: from mail-gx0-f212.google.com ([209.85.217.212]) by mail1-smtp-roc.national.inria.fr with ESMTP; 09 Aug 2009 16:56:32 +0200 Received: by gxk8 with SMTP id 8so2872170gxk.9 for ; Sun, 09 Aug 2009 07:56:32 -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=xr0z8uOF8BB5Gv3liAN8wT81bKtSzhlrEXoYfwRheQY=; b=Y6TcY3BDTo+KY1fqHTjfD8QDRAeJVE86Z11Ht/gqYQeMMbSK7EWsy+ufLlhybxW+fH q0GFIFOd7xRs5rdJPHgKbCMeQDwg2XDarJ1/CpLrkeSFunF7T1vJlvOmHCZF6tpkJIDD k72tH83y3s82x7TgmoRaW7q7uhIqwmV5av2Kg= 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=rEajYOM0xjp/I08l3ve8DqH+Ivvcy09z56FbMyDH/UmVorxgbEbOjGIki9i++0oUIX y88ipbjWLWhqvJKLvNBzI64Gjxv13M/prCYZ9ARiO/MbGj0bMkI+F5FvLRpSsxGI2wdP /Fm1i6OQDMBCs8+qvlEBxi1GM7arsmEb/JEss= Received: by 10.90.88.16 with SMTP id l16mr3102600agb.54.1249829791970; Sun, 09 Aug 2009 07:56:31 -0700 (PDT) Received: from ?192.168.1.100? ([72.44.99.175]) by mx.google.com with ESMTPS id 30sm8507281agc.19.2009.08.09.07.56.30 (version=TLSv1/SSLv3 cipher=RC4-MD5); Sun, 09 Aug 2009 07:56:31 -0700 (PDT) Message-ID: <4A7EE39C.1030803@gmail.com> Date: Sun, 09 Aug 2009 10:56:28 -0400 From: Edgar Friendly User-Agent: Thunderbird 2.0.0.22 (X11/20090608) MIME-Version: 1.0 To: Benjamin Ylvisaker Cc: caml-list@inria.fr 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> In-Reply-To: <2877D20A-1008-4CD0-B1B6-F2EA444B2A88@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 mutable:01 symmetric:01 edgar:98 edgar:98 wrote:01 wrote:01 graph:01 graph:01 caml-list:01 Benjamin Ylvisaker wrote: > > 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. > If you'd like to call this a weakness in the current implementation, you may. > 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 > 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. E