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 QAA18383; Tue, 28 Sep 2004 16:43:55 +0200 (MET DST) 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 QAA17677 for ; Tue, 28 Sep 2004 16:43:53 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id i8SEhqD7014304 for ; Tue, 28 Sep 2004 16:43:52 +0200 Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.11/jtpda-5.4) with ESMTP id i8SEhk6C081416 ; Tue, 28 Sep 2004 16:43:46 +0200 (CEST) X-Ids: 164 Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id QAA18232 ; Tue, 28 Sep 2004 16:41:27 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id QAA573582 ; Tue, 28 Sep 2004 16:41:15 +0200 X-Authentication-Warning: ibm1.cicrp.jussieu.fr: fernande owned process doing -bs Date: Tue, 28 Sep 2004 16:41:15 +0200 (DST) From: Diego Olivier Fernandez Pons X-X-Sender: fernande@ibm1 To: Richard Jones cc: caml-list@inria.fr Subject: Re: [Caml-list] OCaml code/algorithms for displaying directed graphs In-Reply-To: <20040928124015.GA587@annexia.org> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at nez-perce with ID 415978A8.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at shiva.jussieu.fr with ID 415978A2.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Antivirus: scanned by sophie at shiva.jussieu.fr X-Loop: caml-list@inria.fr X-Spam: no; 0.00; pons:01 pons:01 etu:99 caml-list:01 agd:99 leda:01 agd:99 fernandez:01 fernandez:01 ocaml:01 ocaml:01 olivier:02 olivier:02 ads:97 explicit:03 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, > I have a directed graph (actually, links between web-pages). I'd like > to display it "as planar as possible". Are there any OCaml tools or > libraries which I can use? The nearest I've found is ocamlgraph which > looks nice but doesn't seem to deal with the display side of things. Graph drawing is an open and active research topic which makes a heavy usage of state-of-the-art optimization tools and algorithms. Displaying a graph "as planar as possible" is (of course) an NP-hard problem and even a very hard one because constraints are not totally explicit (most of the time you would like an interactive tool that allows you to add and remove constraints while looking for a satisfactory answer). Try AGD (it is built over LEDA) http://www.ads.tuwien.ac.at/AGD/ Diego Olivier ------------------- 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