Re: [Caml-list] Graphmanipulation in Ocaml

[Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@etu.upmc.fr>]

    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