ocamlgraph predecessors
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Edgar Friendly <thelema314@g...> 
Subject:  Re: [Camllist] ocamlgraph predecessors 
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 (10100k 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 workaround 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 singlylinkedlist. You have no option but to >> scan the whole list to find its predecessor. If you had a >> doublylinkedlist, 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 lookuptables. 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