Re: [Caml-list] ocamlgraph predecessors

[Edgar Friendly <thelema314@gmail.com>]

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|)).
> 
> Thanks,
> Ben
> 

What you're asking is similar to the problem of finding the predecessor
of an arbitrary node in a singly-linked-list.  You have no option but to
scan the whole list to find its predecessor.  If you had a
doubly-linked-list, predecessor lookups would work easily, but that's a
different data structure, with much more overhead.

When you talk about "predecessors", I assume you're using a directed
graph, and want to know which nodes have edges to a given node.  if your
graph is static, you could build lookup tables, pregenerating this
information and caching it.  Even with a dynamic graph, maintaining
lookup tables on this info shouldn't be too hard.

Does that help?
E