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 (05:24)
From: Benjamin Ylvisaker <ben8@c...>
Subject: ocamlgraph predecessors
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|)).