Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
performance of ocamlgraph and ocaml batteries
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2010-12-14 (11:02)
From: Eray Ozkural <examachine@g...>
Subject: Re: [Caml-list] performance of ocamlgraph and ocaml batteries
On Mon, Dec 13, 2010 at 5:51 PM, Julien Signoles

> 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.


Eray Ozkural, PhD candidate.  Comp. Sci. Dept., Bilkent University, Ankara