English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

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

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2009-08-08 (13:35)
From: Edgar Friendly <thelema314@g...>
Subject: Re: [Caml-list] ocamlgraph predecessors
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?