Version française
Home     About     Download     Resources     Contact us    

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

Browse thread
[Caml-list] poll for a graph library
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2004-01-29 (14:31)
From: Andrew Bagdanov <andrew@s...>
Subject: Re: [Caml-list] poll for a graph library

I'm about to begin a research project that concentrates on graph
representations and algorithmics in computer vision applications.  I
am wrapping up some work formalizing low-level image processing
patterns in OCaml, and was planning on continuing with OCaml for
higher-level analysis.

The library you describe sounds like an excellent starting point for
me.  A few things I think are important (from my perspective):

 1. Lightweight.  LEDA is, in my opinion, a mess.  Perhaps only an
    expression of my own personal syntactic prejudice, but reading my
    own LEDA code gives me a headache.

 2. Serialization.  Processing pipelines in computer vision
    applications (particularly in reseach environments) are stopped
    and started frequently to allow for tinkering in isolation.

 3. Choice of internal representation.  Despite obvious,
    problem/algorithm performance considerations, some techniques
    might call for adjacency representation (spectral methods, for

Anyway, it sounds great, and I can't wait to get my hands on it!



Jean-Christophe Filliatre writes:
 > Thomas Fischbacher writes:
 >  > 
 >  > What do you mean by "graph library"?
 >  > 
 >  > A library of graph algorithms (highly desirable - right now I am working 
 >  > at a problem where efficient generation of planar graphs is THE main 
 >  > issue, and I do it in lisp/ocaml), a graph layout library in the sense 
 >  > of a re-implementation of graphviz in ocaml (would also be very nice to 
 >  > have), or a plotting library in the sense of gnuplot?
 >  > 
 >  > I think you should clarify this a bit more on the list...
 > You're right, I  should have been clearer. We didn't  want to give too
 > many details  before the first release,  but let's go.  Our library is
 > currently providing
 >  1. Several  data  structures for  graphs  (persistent or  imperative,
 >     directed  or not,  with labeled  edges  or not,  etc.), sharing  a
 >     common minimal signature (iterators over vertices, edges, etc.)
 >  2. Several  algorithms  over graphs,  written  as  functors and  thus
 >     independently of the graph  implementation (it means you can build
 >     your own data structure for graphs and still re-use the algorithms
 >     code). Currently we have  the following algorithms coded: Tarjan's
 >     strongly   connected   components,   Dijkstra's   shortest   path,
 >     Ford-Fulkerson's maximal flow,  Warshall's transitive closure, DFS
 >     and BFS traversal, cycle detection.
 >     We  are  currently  adding   random  graph  generations  based  on
 >     algorithms   from  Knuth's   Stanford  GraphBase,   including  the
 >     generation of random planar graphs.  (This at least seems to be in
 >     connection with what you're doing.)
 >  3. Utilities, such  as a graphviz output  --- an ascii  output in the
 >     DOT format  to be precise (So  we are not  re-implementing a graph
 >     layout library).
 > -- 
 > Jean-Christophe Filliâtre
 > -------------------
 > To unsubscribe, mail Archives:
 > Bug reports: FAQ:
 > Beginner's list:

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: