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

[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 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 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

```