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 _______________________________________________ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs
