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 2EA5FBC6B for ; Wed, 10 Oct 2007 21:36:43 +0200 (CEST) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AgAAAGDGDEeBrw8Eh2dsb2JhbACOSgEBAQgKKQ X-IronPort-AV: E=Sophos;i="4.21,255,1188770400"; d="scan'208";a="4328614" Received: from ext.lri.fr ([129.175.15.4]) by mail3-smtp-sop.national.inria.fr with ESMTP; 10 Oct 2007 21:36:42 +0200 Received: from localhost (localhost [127.0.0.1]) by ext.lri.fr (Postfix) with ESMTP id B616EA4360; Wed, 10 Oct 2007 21:36:42 +0200 (CEST) X-Virus-Scanned: Debian amavisd-new at lri.fr Received: from ext.lri.fr ([127.0.0.1]) by localhost (ext.lri.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5p+Mb1rYC8+k; Wed, 10 Oct 2007 21:36:42 +0200 (CEST) Received: from smtp.lri.fr (vhost3-23 [129.175.3.23]) by ext.lri.fr (Postfix) with ESMTP id 9D08AA4287; Wed, 10 Oct 2007 21:36:42 +0200 (CEST) Received: from serveur9-10.lri.fr (serveur9-10 [129.175.9.10]) by smtp.lri.fr (Postfix) with ESMTP id A475EE04BA; Wed, 10 Oct 2007 21:36:42 +0200 (CEST) Received: from filliatr by serveur9-10.lri.fr with local (Exim 3.36 #1 (Debian)) id 1IfhMI-0004aj-00; Wed, 10 Oct 2007 21:36:42 +0200 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <18189.10698.543413.96648@serveur9-10.lri.fr> Date: Wed, 10 Oct 2007 21:36:42 +0200 From: Jean-Christophe Filliatre To: "Orlin Grigorov" Cc: caml-list@yquem.inria.fr Subject: Re: [Caml-list] Data structure for a directed bipartite graph In-Reply-To: References: X-Mailer: VM 7.19 under Emacs 21.4.1 X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 ocaml:01 nodes:01 ocaml:01 lri:01 nodes:01 node:01 logarithmic:01 genericity:01 integers:01 hash:01 functors:01 faq:01 Hi, Orlin Grigorov writes: > A bipartite graph is a graph [...] > So, I was thinking about a data structure in OCaml, in which I want to store > such graph, and also to allow me easy access to elements, as well as adding > new nodes and edges (therefore, the structure would be imperative, that is, > will have a state). So, how about this: As already mentionned by somebody else, there exists at least one graph library for ocaml at http://ocamlgraph.lri.fr/ It provides several data structures for graph, including matrix representations as the one you are mentioning, but also others more suitable for sparse graphs. Note that the ability to add new nodes and new edges does not enforce the use of an imperative data structure. A persistent one is equally fine; you simply get a new graph when you add a node or an edge, the previous one being unchanged (with a logarithmic time and space overhead, typically). Ocamlgraph makes heavy use of ocaml module system to provide great genericity and thus may appear as somewhat heavy for a newcomer. You should start by having a look at module Pack, which provides an easy access to the library (imperative data structure with nodes and edges labeled with integers; see http://ocamlgraph.lri.fr/doc/Pack.html Regarding the ability to attach information to nodes (or edges) you may indeed use an additional data structure for that purpose (a hash table, typically) but you may also use ocamlgraph to define your own graph data structure with any kind of information associated to nodes and edges. That is precisely why ocamlgraph was designed in a highly generic way. See ocamlgraph's FAQ for an example of such instantiation. Note that Ocamlgraph's documentation includes an article "Designing a Generic Graph Library using ML Functors" which can be seen as an introduction to ocamlgraph's design. Hope this helps, -- Jean-Christophe