Re: [Caml-list] ocamlgraph predecessors

[Julien Signoles <Julien.Signoles@cea.fr>]

Benjamin Ylvisaker a écrit :
> 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|)).

Actually, looking at the current implementation, accessing predecessors 
is worse that O(|V|): that is max(O(|V|,O(|E|)).

If you use concrete (imperative directional) graphs, the simpler 
work-around  is to use Imperative.Digraph.ConcreteBidirectional as 
suggested by Kevin Cheung. It uses more memory space (at worse the 
double) that standard concrete directional graphs. But accessing 
predecessors is in O(1) amortized instead of max(O(|V|,O(|E|)) and 
removing a vertex is in O(D*ln(D)) where D is the maximal degree of the 
graph instead of O(|V|*ln(|V|)).

If you don't use this functor, other work-arounds have been suggested in 
other posts.

By the way contributing to ocamlgraph by adding 
Imperative.Digraph.AbstractBidirectional (for instance) is still 
possible and welcome :o).

--
Julien Signoles