Re: [Caml-list] Graphmanipulation in Ocaml

["Gleb N. Semenov" <gleb@ahome.ru>]

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