From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>
To: caml-list@inria.fr
Subject: Re: [Caml-list] Graphmanipulation in Ocaml
Date: Wed, 17 Sep 2003 10:29:11 +0200 (DST) [thread overview]
Message-ID: <Pine.A41.4.44.0309170957500.1368288-100000@ibm1.cicrp.jussieu.fr> (raw)
In-Reply-To: <3F676CF3.E13A9AF4@ahome.ru>
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
next prev parent reply other threads:[~2003-09-17 8:30 UTC|newest]
Thread overview: 14+ messages / expand[flat|nested] mbox.gz Atom feed top
2003-09-01 18:46 Arne Koewing
2003-09-01 20:15 ` Matt Gushee
2003-09-01 20:27 ` [Caml-list] " Arne Koewing
2003-09-01 21:53 ` Matt Gushee
2003-09-02 9:09 ` Martin Jambon
2003-09-03 11:37 ` [Caml-list] " Francisco J. Valverde Albacete
2003-09-16 20:05 ` Gleb N. Semenov
2003-09-16 22:35 ` henridf
2003-09-17 10:52 ` Gleb N. Semenov
2003-09-17 8:29 ` Diego Olivier Fernandez Pons [this message]
2003-09-17 8:59 ` Eray Ozkural
2003-09-17 9:53 ` Diego Olivier Fernandez Pons
2003-09-17 12:18 ` Andreas Rossberg
2003-09-17 18:11 ` Gleb N. Semenov
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=Pine.A41.4.44.0309170957500.1368288-100000@ibm1.cicrp.jussieu.fr \
--to=diego.fernandez_pons@etu.upmc.fr \
--cc=caml-list@inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).