Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Graphmanipulation in Ocaml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Diego Olivier Fernandez Pons <Diego.FERNANDEZ_PONS@e...>
Subject: Re: [Caml-list] Graphmanipulation in Ocaml

> 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

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 Archives:
Bug reports: FAQ:
Beginner's list: