Re: [Caml-list] ocamlgraph predecessors

["Jean-Christophe Filliâtre" <Jean-Christophe.Filliatre@lri.fr>]

Hi,

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
workarounds:

- 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,
-- 
Jean-Christophe