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 mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105]) by yquem.inria.fr (Postfix) with ESMTP id 98637BC37 for ; Sat, 8 Aug 2009 07:24:57 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: Am4BAM+ofEpCbwQZkGdsb2JhbACaRAEBAQEJCQwHEwSkTIcaiE6EFgU X-IronPort-AV: E=Sophos;i="4.43,345,1246831200"; d="scan'208";a="44462575" Received: from out1.smtp.messagingengine.com ([66.111.4.25]) by mail4-smtp-sop.national.inria.fr with ESMTP; 08 Aug 2009 07:24:56 +0200 Received: from compute1.internal (compute1.internal [10.202.2.41]) by gateway1.messagingengine.com (Postfix) with ESMTP id BD624FC06 for ; Sat, 8 Aug 2009 01:24:54 -0400 (EDT) Received: from heartbeat2.messagingengine.com ([10.202.2.161]) by compute1.internal (MEProxy); Sat, 08 Aug 2009 01:24:54 -0400 X-Sasl-enc: XDAEBRix69KKGfuC/084yjNYAsbwt/VUPJgKl9y9LGWo 1249709094 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 4A35B47CC for ; Sat, 8 Aug 2009 01:24:54 -0400 (EDT) Message-Id: <4EC4528F-4993-482F-8ECB-ED6848C3FC4D@cs.washington.edu> From: Benjamin Ylvisaker To: caml-list@yquem.inria.fr 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: ocamlgraph predecessors Date: Fri, 7 Aug 2009 22:24:50 -0700 X-Mailer: Apple Mail (2.935.3) X-Spam: no; 0.00; moderately:01 work-:98 graph:01 benjamin:01 seems:03 seems:03 generally:04 vertex:05 vertices:06 vertices:06 missing:07 graphs:11 reasonable:12 source:12 predecessor:13 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