Re: [Caml-list] poll for a graph library

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

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 caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners