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 KAA16538; Wed, 17 Sep 2003 10:30:03 +0200 (MET DST) 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 KAA14255 for ; Wed, 17 Sep 2003 10:30:02 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h8H8U2T13952 for ; Wed, 17 Sep 2003 10:30:02 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.9/jtpda-5.4) with ESMTP id h8H8U1gR053929 for ; Wed, 17 Sep 2003 10:30:01 +0200 (CEST) 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 KAA33064 for ; Wed, 17 Sep 2003 10:29:12 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with ESMTP id KAA1949828 for ; Wed, 17 Sep 2003 10:29:11 +0200 Date: Wed, 17 Sep 2003 10:29:11 +0200 (DST) From: Diego Olivier Fernandez Pons To: caml-list@inria.fr Subject: Re: [Caml-list] Graphmanipulation in Ocaml In-Reply-To: <3F676CF3.E13A9AF4@ahome.ru> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 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 powerfull:01 smlnj:01 arne:01 koewing:01 erwig's:01 haskell:01 degenerate:01 erwig:01 implemented:01 polynomial:01 implemented:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, > I have seen the very powerfull graph library in MLRISC package which > is included to New Jersey SML distribution (SMLNJ). MLRISC is a big > and quite universal set of libraries for building SML compilers for > RISC architectures. > For the first look, the graph library is quite usefull and > clear('understandable' :)), MLRISC is written in an 'object oriented' style (which I don't find understandable at all but that may just be a matter of taste) : records with functions inside the records to simulate the member functions. I answered some time ago (in private) to Arne Koewing. The main problem is not the graph data structure library but the fact that he seems to need pattern matching on graphs. This is a research problem and as far as I know none of the graph data structure libraries available provides this feature. Martin Erwig's FGL (Functional Graph Library) available in SML (old version) or Haskell (new version) uses a degenerate version of pattern matching on nodes (called context), because of the inductive way it manipulates graphs. ex : G = (0, 1) (0, 2) (2, 1) (1, 3) (2, 3) (1, 4) (4, 3) You can match 1 which gives you ((0, 1), (2, 1)), ((1, 3), (1, 4)) and the rest of the graph (0, 2) (2, 3) (4, 3). Many functions over graphs are written with this matching operator. Since this way of handling graphs is very (very) slow, Erwig also provides specialized versions. If this restricted pattern matching is enough, it can be implemented with a zipper over ternary trees. The general case of matching must be NP-hard (not a formal demonstration but just imagine you could match against all cliques of a graph in polynomial time !) and I really don't know how it could be implemented even for a restricted set of graphs to match. 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