This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

ocamlgraph predecessors
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: -- (:) From: Benjamin Ylvisaker Subject: Re: [Caml-list] ocamlgraph predecessors
```
On Aug 25, 2009, at 10:22 AM, Julien Signoles wrote:

> Benjamin Ylvisaker a écrit :
>> 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|)).
>
> Actually, looking at the current implementation, accessing
> predecessors is worse that O(|V|): that is max(O(|V|,O(|E|)).
>
> If you use concrete (imperative directional) graphs, the simpler
> work-around  is to use Imperative.Digraph.ConcreteBidirectional as
> suggested by Kevin Cheung. It uses more memory space (at worse the
> double) that standard concrete directional graphs. But accessing
> predecessors is in O(1) amortized instead of max(O(|V|,O(|E|)) and
> removing a vertex is in O(D*ln(D)) where D is the maximal degree of
> the graph instead of O(|V|*ln(|V|)).
>
> If you don't use this functor, other work-arounds have been
> suggested in other posts.
>
> By the way contributing to ocamlgraph by adding
> Imperative.Digraph.AbstractBidirectional (for instance) is still
> possible and welcome :o).

ConcreteBidirectional module, but it looks like it wouldn't be a drop-
in replacement for me, because it's unlabeled and I need labels.

If anyone is curious, here is the wrapper logic that I ended up adding:

When the user wants an edge from v1 to v2 with label X, two "internal"
edges get created: one from v1 to v2 with label EdgeForward (X) and
one from v2 to v1 with label EdgeBackward (X).  These two edges are
removal faster, I added a table that maps an edge to its "pair".  All
edge-related wrapper functions can take either of the pair of wrapper
edges, and will use the source or destination vertex of the edge,
depending on the Forward/Backward label.  The edge removal wrapper
function gets the mate of the passed in edge by looking it up in the
table, and removes them both.

To make vertex removal faster, I added a Boolean "removed" field to
vertex labels that is set to false on vertex creation.  When the
wrapper vertex removal function is called, it removes all the incident
edges and then just sets the vertex's removed flag to true.  Vertex
scanning functions clearly need to check the flag to determine whether
an "internal" vertex should actually be considered part of the graph
or not.

If there is a lot of vertex creation and removal in an application,
clearly a lot of "garbage" vertices will end up polluting the graph.
When the amount of garbage gets too large, a new copy of a graph can
be constructed with only the "real" vertices copied over.  This is not
a totally transparent operation, because if there are any tables keyed
on vertices or edges, external to the graph itself, they'll get
confused by the copying.

This set of wrapper logic clearly adds a non-trivial amount of memory
overhead:  1) The edge and vertex labels are a little bit bigger.  2)
There are two edges for every externally visible edge.  3) The edge-
pair table adds another O(|E|) chunk of memory.  4) An application-
dependent number of garbage vertices will be floating around.  I'm
pretty sure all the wrapper operations are asymptotically as fast as
they reasonably can be, though.  If an implementation like this were
done in the library itself (notice the strategic use of the passive
voice) instead of as a wrapper, I'm pretty sure vertex removal could
be handled more cleanly.

Ben

```