From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id TAA08934; Fri, 30 Jan 2004 19:24:29 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA17117 for ; Fri, 30 Jan 2004 19:24:28 +0100 (MET) From: brogoff@speakeasy.net Received: from mail1.speakeasy.net (mail1.speakeasy.net [216.254.0.201]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id i0UIOQv16639 for ; Fri, 30 Jan 2004 19:24:27 +0100 (MET) Received: (qmail 31003 invoked from network); 30 Jan 2004 18:24:25 -0000 Received: from grace.speakeasy.net ([216.254.0.22]) (envelope-sender ) by mail1.speakeasy.net (qmail-ldap-1.03) with AES256-SHA encrypted SMTP for ; 30 Jan 2004 18:24:25 -0000 Date: Fri, 30 Jan 2004 10:24:17 -0800 (PST) To: Jean-Christophe Filliatre cc: Thomas Fischbacher , , , Subject: Re: [Caml-list] poll for a graph library In-Reply-To: <16409.2937.135897.374276@gargle.gargle.HOWL> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=X-UNKNOWN Content-Transfer-Encoding: QUOTED-PRINTABLE X-Loop: caml-list@inria.fr X-Spam: no; 0.00; brogoff:01 caml-list:01 generic:01 oopsla:01 plea:01 isomorphism:01 filliatre:01 graphviz:01 plotting:01 gnuplot:01 vertices:01 functors:01 re-use:01 transitive:01 bfs:99 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 lang= uages 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 compar= ison. -- 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 worki= ng > > 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 t= o > > 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=E2tre > > ------------------- > To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inr= ia.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