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 PAA05551; Thu, 29 Jan 2004 15:31:58 +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 PAA04928 for ; Thu, 29 Jan 2004 15:31:56 +0100 (MET) Received: from imap.science.uva.nl (imap.science.uva.nl [146.50.4.51]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id i0TEVuv27428 for ; Thu, 29 Jan 2004 15:31:56 +0100 (MET) Received: from vegas.science.uva.nl [146.50.1.150] by imap.science.uva.nl with ESMTP (sendmail 8.11.6p2/config 11.34). id i0TEVuH24878; Thu, 29 Jan 2004 15:31:56 +0100 Received: from localhost by vegas.science.uva.nl (sendmail 8.11.6/config 11.34). id i0TEVte13726; Thu, 29 Jan 2004 15:31:55 +0100 X-Organisation: Faculty of Science, University of Amsterdam, The Netherlands X-URL: http://www.science.uva.nl/ From: Andrew Bagdanov MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable Message-ID: <16409.6491.566548.388388@vegas.science.uva.nl> Date: Thu, 29 Jan 2004 15:31:55 +0100 To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Cc: caml-list@inria.fr Subject: Re: [Caml-list] poll for a graph library In-Reply-To: <16409.2937.135897.374276@gargle.gargle.HOWL> References: <16408.64997.828000.931868@gargle.gargle.HOWL> <16409.2937.135897.374276@gargle.gargle.HOWL> X-Mailer: VM 7.07 under Emacs 21.1.1 X-Virus-Scanned: by amavisd-new X-Loop: caml-list@inria.fr X-Spam: no; 0.00; uva:99 caml-list:01 low-level:01 higher-level:01 leda:01 leda:01 pipelines:01 tinkering:01 spectral:01 filliatre:01 graphviz:01 plotting:01 gnuplot:01 vertices:01 functors:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hi, I'm about to begin a research project that concentrates on graph representations and algorithmics in computer vision applications. I am wrapping up some work formalizing low-level image processing patterns in OCaml, and was planning on continuing with OCaml for higher-level analysis. The library you describe sounds like an excellent starting point for me. A few things I think are important (from my perspective): 1. Lightweight. LEDA is, in my opinion, a mess. Perhaps only an expression of my own personal syntactic prejudice, but reading my own LEDA code gives me a headache. 2. Serialization. Processing pipelines in computer vision applications (particularly in reseach environments) are stopped and started frequently to allow for tinkering in isolation. 3. Choice of internal representation. Despite obvious, problem/algorithm performance considerations, some techniques might call for adjacency representation (spectral methods, for example). Anyway, it sounds great, and I can't wait to get my hands on it! Cheers, -Andy Jean-Christophe Filliatre writes: >=20 > Thomas Fischbacher writes: > >=20 > > What do you mean by "graph library"? > >=20 > > A library of graph algorithms (highly desirable - right now I am = working=20 > > at a problem where efficient generation of planar graphs is THE m= ain=20 > > issue, and I do it in lisp/ocaml), a graph layout library in the = sense=20 > > of a re-implementation of graphviz in ocaml (would also be very n= ice to=20 > > have), or a plotting library in the sense of gnuplot? > >=20 > > I think you should clarify this a bit more on the list... >=20 > You're right, I should have been clearer. We didn't want to give t= oo > many details before the first release, but let's go. Our library = is > currently providing >=20 > 1. Several data structures for graphs (persistent or imperativ= e, > directed or not, with labeled edges or not, etc.), sharing = a > common minimal signature (iterators over vertices, edges, etc.) >=20 > 2. Several algorithms over graphs, written as functors and th= us > independently of the graph implementation (it means you can bui= ld > your own data structure for graphs and still re-use the algorith= ms > code). Currently we have the following algorithms coded: Tarjan= 's > strongly connected components, Dijkstra's shortest pat= h, > Ford-Fulkerson's maximal flow, Warshall's transitive closure, D= FS > and BFS traversal, cycle detection. >=20 > We are currently adding random graph generations based = on > algorithms from Knuth's Stanford GraphBase, including t= he > generation of random planar graphs. (This at least seems to be = in > connection with what you're doing.) >=20 > 3. Utilities, such as a graphviz output --- an ascii output in t= he > DOT format to be precise (So we are not re-implementing a gra= ph > layout library). >=20 > --=20 > Jean-Christophe Filli=E2tre >=20 > ------------------- > To unsubscribe, mail caml-list-request@inria.fr Archives: http://cam= l.inria.fr > Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inr= ia.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