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

[brogoff@speakeasy.net]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=X-UNKNOWN, Size: 2938 bytes --]

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

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