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 UAA01006; Wed, 17 Sep 2003 20:12:08 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA03991 for ; Wed, 17 Sep 2003 20:12:06 +0200 (MET DST) Received: from ns.sunet.ru (ns.sunet.ru [217.174.96.14]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h8HIC4j08125 for ; Wed, 17 Sep 2003 20:12:05 +0200 (MET DST) Received: from ahome.ru (217-174-98-36.dial.sunet.ru [217.174.98.36] (may be forged)) (authenticated) by ns.sunet.ru (8.11.7/8.11.7) with ESMTP id h8HI7WG07542; Wed, 17 Sep 2003 22:07:32 +0400 (MSD) Message-ID: <3F68A3ED.7BCCCA4@ahome.ru> Date: Wed, 17 Sep 2003 22:11:57 +0400 From: "Gleb N. Semenov" Reply-To: gleb@ahome.ru, semenov@jet.msk.su Organization: @Home X-Mailer: Mozilla 4.79 [en] (X11; U; Linux 2.4.2 i386) X-Accept-Language: ru, en, fr MIME-Version: 1.0 To: caml-list@inria.fr CC: anton_bondarenko@yahoo.com Subject: Re: [Caml-list] Graphmanipulation in Ocaml References: Content-Type: text/plain; charset=koi8-r Content-Transfer-Encoding: 7bit X-Loop: caml-list@inria.fr X-Spam: no; 0.00; gleb:01 gleb:01 caml-list:01 bonsoir:99 pons:01 powerfull:01 smlnj:01 programmer's:01 arne:01 koewing:01 erwig's:01 haskell:01 degenerate:01 erwig:01 implemented:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonsoir, Diego Olivier Fernandez Pons wrote: > > 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) : Two year ago my opinoin about OO-style was the same. But the severe programmer's life force me to change it :)))) > 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. Sorry, but what do You mean? Does Your statement means that pattern matching routines are _not_ included in MLRISC graph library or included routines can not handle particular graph instanses correctly? Or does it mean that(as You wrote later in this message) we have not enough matching criteria for due to algoritmic problems? Also, after Your conclusion one can think that the _only_ way to use this library is to write pattern matching routines. Please, give the precise meaning :). > > 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. May be this problem not in pattern-matching approach but algoritmic? The using of MLRISC graph library and pattern matching technics for restricted set of aplications is fine. The possibility to find and add some algorithms to solve new(or unsolved) problems to existing library is great! > > Diego Olivier Regards! GNS -- Gleb N. Semenov 111621, Muromskaya St. 21, apt. 2, Moscow, Russia gleb@ahome.ru phone: +7(095)700.0172 ------------------- 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