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