English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
ocamlgraph predecessors
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2009-08-26 (06:54)
From: Jean-Christophe_Filliâtre <Jean-Christophe.Filliatre@l...>
Subject: Re: [Caml-list] ocamlgraph predecessors

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

Not providing predecessors in constant time was a deliberate choice in
Ocamlgraph. (A graph is basically a map which binds any vertex to the
set of its successors, and that's it.)

If you need efficient access to the predecessors, you have several

- implement your own graph data structure; after all, ocamlgraph was
designed to clearly separate data structures and algorithms, so that you
will still be able to use graph algorithms on your own graphs.

- use the graph data structure Imperative.Digraph.ConcreteBidirectional,
which is the only graph data structure in Ocamlgraph providing
predecessors in constant time; it is actually the contribution of a user
(Ted Kremenek) who experienced the same need as yourself.

- memoize the results of the predecessors function (either in a modified
version of the data structure or externally if your algorithm allows it).

Hope this helps,