Re: [Caml-list] ocamlgraph predecessors

[Benjamin Ylvisaker <ben8@cs.washington.edu>]

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.

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