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-30 (18:24)
From: brogoff@s...
Subject: Re: [Caml-list] poll for a graph library
It is interesting that the authors of the C++ Boost Graph Library wrote a
paper comparing languages for their ability to support generic programming by
using the development of a graph library as an example, and one of the languages
they look at is SML. It's in the OOPSLA '03  proceedings I think.

Selfishness forces me to put in a plea for including a graph isomorphism
algorithm in your library. The application I have in mind is netlist comparison.

-- Brian

On Thu, 29 Jan 2004, Jean-Christophe Filliatre wrote:

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