Re: [Caml-list] ocamlgraph predecessors

[Edgar Friendly <thelema314@gmail.com>]

Benjamin Ylvisaker wrote:
> 
> On Aug 8, 2009, at 6:35 AM, Edgar Friendly wrote:
> 
>> 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
> 
> The list analogy seems like a little bit of a stretch to me.  I
> understand the point, but I think most programmers would expect
> predecessor and successor operations in a generic mutable directed graph
> library to be symmetric in every way, including performance.
> 
If you'd like to call this a weakness in the current implementation, you
may.

> I'm thinking about making a thin wrapper around ocamlgraph that makes
> "internal" edges in both directions with tags to distinguish them
> whenever the user creates an "external" edge.  All the wrapper graph
> traversal functions would only use ocamlgraph's successor functions, and
> then use the tags to distinguish which edges are really supposed to
> point in which direction.  It's a bit of a hassle, and will roughly
> double the amount of storage required for edges, but I need predecessor
> access in my application, and the O(|V|) performance is really painful
> for big graphs.
> 
> Ben
> 
This is another solution to the slow predecessor performance, and will
have different performance characteristics than predecessor
lookup-tables.  Note that the lookup table solution is isomorphic to
building a second graph with all the arrows reversed, and using the
efficient successor operations on it.  Maybe this'll be easier than
keeping a merged graph.  Maybe not.

E