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 OAA01011; Thu, 29 Jan 2004 14:33:03 +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 OAA01084 for ; Thu, 29 Jan 2004 14:33:02 +0100 (MET) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id i0TDX2v18641 for ; Thu, 29 Jan 2004 14:33:02 +0100 (MET) Received: from pc8-123 (pc8-123 [129.175.8.123]) by lri.lri.fr (8.12.10/jtpda-5.4) with ESMTP id i0TDWfUV008035 ; Thu, 29 Jan 2004 14:32:41 +0100 (MET) Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian)) id 1AmCHh-0007O0-00; Thu, 29 Jan 2004 14:32:41 +0100 From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <16409.2937.135897.374276@gargle.gargle.HOWL> Date: Thu, 29 Jan 2004 14:32:41 +0100 To: Thomas Fischbacher CC: signoles@pc8-123.lri.fr, conchon@pc8-123.lri.fr, caml-list@inria.fr Subject: Re: [Caml-list] poll for a graph library In-Reply-To: References: <16408.64997.828000.931868@gargle.gargle.HOWL> X-Mailer: VM 7.03 under Emacs 20.7.2 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) X-MailScanner: Found to be clean X-Loop: caml-list@inria.fr X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 caml-list:01 graphviz:01 plotting:01 gnuplot:01 vertices:01 functors:01 re-use:01 transitive:01 bfs:99 knuth's:01 graphviz:01 ocaml:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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