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 (13:33)
From: Jean-Christophe Filliatre <Jean-Christophe.Filliatre@l...>
Subject: Re: [Caml-list] poll for a graph library

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: