From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 8177CBC57 for ; Tue, 14 Dec 2010 12:02:46 +0100 (CET) X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: AtkAAO/dBk3RVaC0k2dsb2JhbACVMoYvAYghCBYBAQEJCQoJEQQlpxmJcIIYhSUuiFYBAQMFhUUEinqGBw X-IronPort-AV: E=Sophos;i="4.59,341,1288566000"; d="scan'208";a="70464389" Received: from mail-gy0-f180.google.com ([209.85.160.180]) by mail3-smtp-sop.national.inria.fr with ESMTP; 14 Dec 2010 12:02:45 +0100 Received: by gya6 with SMTP id 6so223365gya.39 for ; Tue, 14 Dec 2010 03:02:45 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:received:received:in-reply-to :references:date:message-id:subject:from:to:cc:content-type; bh=nvpPGGMGqxj9rw6f3wqoCQvPhDEODaIlnosGGeoqoew=; b=vbQaMPzcZOQKZmFcAtUrYm+Q0INGiwClokdeD6i6tJ94mYkJ/QsNKT8pjqiHCY749Q s5JvrQHpsbFB6H56Kn/H0b6jKQXo7nPCCI7qOh4maDcdna3Gbyq9vEP1y1pkbHwz/0LG eOyi25eti0/q+W5wz4C9RgiAgTWr1LaI3OlJQ= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; b=bsHoHoackjWpvw0LE5qrI+4xqjBpmkc+oHd85l7P3uTb5RK7GrIeNfpl5mvdigLoox RgHTBSDj/eo1oibKUeBBymyKD9tjIARWr4wL6qpdXb5NlSE67fKIlrxQ58qZaOEGvcsO QsJtDsw7Hf8uEklhqOePUYwiQUzWgsBofH7Zw= MIME-Version: 1.0 Received: by 10.90.63.1 with SMTP id l1mr1502622aga.123.1292324565009; Tue, 14 Dec 2010 03:02:45 -0800 (PST) Received: by 10.90.211.10 with HTTP; Tue, 14 Dec 2010 03:02:44 -0800 (PST) In-Reply-To: References: <4D0631FD.6000106@elehack.net> Date: Tue, 14 Dec 2010 13:02:44 +0200 Message-ID: Subject: Re: [Caml-list] performance of ocamlgraph and ocaml batteries From: Eray Ozkural To: Julien Signoles Cc: Michael Ekstrand , caml-list@yquem.inria.fr Content-Type: multipart/alternative; boundary=0016e64f483aa1c64104975cc213 X-Spam: no; 0.00; ocaml:01 eray:01 ozkural:01 signoles:01 signoles:01 eray:01 ozkural:01 hash:01 hash:01 arrays:01 bitvectors:01 functor:01 functor:01 ocaml:01 higher-order:01 --0016e64f483aa1c64104975cc213 Content-Type: text/plain; charset=ISO-8859-1 On Mon, Dec 13, 2010 at 5:51 PM, Julien Signoles wrote: > Hello, > > 2010/12/13 Eray Ozkural > > Oww, is the imperative implementation using hash tables or maps then? >> > > Imperative implementations use hash tables (except the ones called Matrix > which use arrays of bitvectors) while persistent implementations use maps. > Yes, I noticed, the incidence matrix is pretty good for dense unlabeled graphs, that's probably better than the one boost provides. > > >> Shouldn't be too hard to plug your own in ocamlgraph if needed. >> > > OcamlGraph is designed for such an use : each algorithm provided by the > library is a functor parameterized by the required graph operations > (iterators over vertices and edges, ...). Thus you can provide your own in > an easy way. > > Hope this helps, > Sure it does. I've used ocamlgraph in a number of projects and I'm very glad with the functor interface. It feels right! One of the big reasons I'm using ocaml is the higher-order module feature, it's great for writing truly extensible and re-usable software. Regarding the above discussion, hash table is actually appropriate for a very large number of use-cases and I've seen it recommended it in a software engineering journal. That's true especially if you need to query individual edges, although many classical graph algorithms work best with an adjacency list representation, which can be easily implemented as you suggest. Best, -- Eray Ozkural, PhD candidate. Comp. Sci. Dept., Bilkent University, Ankara http://groups.yahoo.com/group/ai-philosophy http://myspace.com/arizanesil http://myspace.com/malfunct --0016e64f483aa1c64104975cc213 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable On Mon, Dec 13, 2010 at 5:51 PM, Julien Signoles <julien.signoles@gmail.com><= /span> wrote:
Hello,

2010/12/13 Eray Ozkural <exam= achine@gmail.com>

Oww, is the imperative implementation using hash tables or maps then? =

Imperative implementations use hash table= s (except the ones called Matrix which use arrays of bitvectors) while pers= istent implementations use maps.

Yes, I noticed, the incidence = matrix is pretty good for dense unlabeled graphs, that's probably bette= r than the one boost provides.
=A0
=A0
Shouldn't be too hard to plug = your own in ocamlgraph if needed.

OcamlGraph is designed for such an use : each algorithm prov= ided by the library is a functor parameterized by the required graph operat= ions (iterators over vertices and edges, ...). Thus you can provide your ow= n in an easy way.

Hope this helps,=A0

Sure it= does. I've used ocamlgraph in a number of projects and I'm very gl= ad with the functor interface. It feels right! One of the big reasons I'= ;m using ocaml is the higher-order module feature, it's great for writi= ng truly extensible and re-usable software.

Regarding the above discussion, hash table is actually = appropriate for a very large number of use-cases and I've seen it recom= mended it in a software engineering journal. That's true especially if = you need to query individual edges, although many classical graph algorithm= s work best with an adjacency list representation, which can be easily impl= emented as you suggest.

Best,=A0

--
Eray Ozkural, PhD candid= ate.=A0 Comp. Sci. Dept., Bilkent University, Ankara
http://groups.yahoo.com/group/ai-philo= sophy
http://myspace.com/arizanesil= http://myspace.com/malfunct
--0016e64f483aa1c64104975cc213--