[Caml-list] Graphmanipulation in Ocaml

[Caml-list] Graphmanipulation in Ocaml

[Arne Koewing]

Hi!

I am looking for an library for graph-manipulation/handling.
Do you know any implementations for ocaml?

thx,
Arne

-------------------
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

Re: [Caml-list] Graphmanipulation in Ocaml

[Matt Gushee]

On Mon, Sep 01, 2003 at 08:46:05PM +0200, Arne Koewing wrote:
> 
> I am looking for an library for graph-manipulation/handling.
> Do you know any implementations for ocaml?

Do you mean 'graph' in the abstract, mathematical sense, or in the sense
of data visualization?


-- 
Matt Gushee                 When a nation follows the Way,
Englewood, Colorado, USA    Horses bear manure through
mgushee@havenrock.com           its fields;
http://www.havenrock.com/   When a nation ignores the Way,
                            Horses bear soldiers through
                                its streets.
                                
                            --Lao Tzu (Peter Merel, trans.)

-------------------
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

[Caml-list] Re: Graphmanipulation in Ocaml

[Arne Koewing]

Matt Gushee <matt@gushee.net> writes:

> On Mon, Sep 01, 2003 at 08:46:05PM +0200, Arne Koewing wrote:
>> 
>> I am looking for an library for graph-manipulation/handling.
>> Do you know any implementations for ocaml?
>
> Do you mean 'graph' in the abstract, mathematical sense, or in the sense
> of data visualization?

I mean the mathematical one.
I want to implement some rule-based graphtransformation,
so I need a data structure that allows subgraph-matching for example...

any links or ideas are welcome ;-)

thx,
Arne


-------------------
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

Re: [Caml-list] Re: Graphmanipulation in Ocaml

[Matt Gushee]

On Mon, Sep 01, 2003 at 10:27:46PM +0200, Arne Koewing wrote:
> 
> >> I am looking for an library for graph-manipulation/handling.
> >> Do you know any implementations for ocaml?
> >
> > Do you mean 'graph' in the abstract, mathematical sense, or in the sense
> > of data visualization?
> 
> I mean the mathematical one.
> I want to implement some rule-based graphtransformation,
> so I need a data structure that allows subgraph-matching for example...

Sorry, then ... I might have had some useful suggestions about the other
type of graph, but not what you're looking for. But perhaps others on
the list can help.

-- 
Matt Gushee                 When a nation follows the Way,
Englewood, Colorado, USA    Horses bear manure through
mgushee@havenrock.com           its fields;
http://www.havenrock.com/   When a nation ignores the Way,
                            Horses bear soldiers through
                                its streets.
                                
                            --Lao Tzu (Peter Merel, trans.)

-------------------
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

Re: [Caml-list] Re: Graphmanipulation in Ocaml

[Martin Jambon]

On Mon, 1 Sep 2003, Arne Koewing wrote:

> Matt Gushee <matt@gushee.net> writes:
>
> > On Mon, Sep 01, 2003 at 08:46:05PM +0200, Arne Koewing wrote:
> >>
> >> I am looking for an library for graph-manipulation/handling.
> >> Do you know any implementations for ocaml?
> >
> > Do you mean 'graph' in the abstract, mathematical sense, or in the sense
> > of data visualization?
>
> I mean the mathematical one.
> I want to implement some rule-based graphtransformation,
> so I need a data structure that allows subgraph-matching for example...

My feeling is that OCaml is very convenient for writing graph libraries,
so that you will very easily write your own data structure together with
the functions that manipulate it.

I know very few things about graph theory. However, even for trivial
algorithm, you will probably need to choose a very specific representation
for your data structure (How do I store neighbors? Do I have to iterate
over edges? Is my graph dynamic? ...).
The problem is that you will probably store some internal information in
every vertex or edge depending on the specific algorithms you will use,
and this is why it is difficult to write a general purpose library for
graph manipulation. You can still write a fully mutable
('vertex_contents, 'edge_contents) graph type using hash tables for
representing any sets of edges and sets of vertices, but is it useful?


Regards,

Martin





-------------------
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

Re: [Caml-list] Graphmanipulation in Ocaml

[Francisco J. Valverde Albacete]

Arne Koewing wrote:

>Hi!
>
>I am looking for an library for graph-manipulation/handling.
>Do you know any implementations for ocaml?
>
>thx,
>Arne
>  
>
I have found useful constructs in:

- the pomap (partial order) Library for maintaining partially ordered 
maps, by Markus Mottl: 
http://www.ai.univie.ac.at/~markus/home/ocaml_sources.html)

- the Bitv library A bit vectors library, by Jean-Christophe Filliâtre 
to encode graphs by means of the incidence relation.

I've used these for encoding very particular relations interpreted as 
their order graphs.

Hope you have luck with it and, please, give us notice of your progress.

Regards,

    Francisco Valverde
    Univ. Carlos III de Madrid


-------------------
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

Re: [Caml-list] Graphmanipulation in Ocaml

[Gleb N. Semenov]

Arne Koewing wrote:
> 
> Hi!
> 
> I am looking for an library for graph-manipulation/handling.
> Do you know any implementations for ocaml?
> 
> thx,
> Arne
> 

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' :)),
but it is written in SML. It is not very hard to rewrite it in OCaml
language.
If this project will start, You may consider me as a participant. But I
have not much
time for such work(for me this work will be the 'fun-project').
Let You look at MLRISC graph library and give Your opinion about the
library
and about the possibility of using it in Your tasks :)

The second variant. You may search caml-list for 'graph'. Some times ago
it was
small discussion there about exactly the same problem. You may find some
links to less powerfull and universal graph libraries but written in
ocaml.

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

Re: [Caml-list] Graphmanipulation in Ocaml

[henridf]

judging by the interface and docs, it looks pretty nice.
i would be glad to have this in caml.

i still would like to browse the code before deciding, but i am quite 
tempted to take this on as a little project.

does anyone have experience porting sml code to caml? i would expect 
everything is fairly mechanic, or can there be differences which require 
non-trivial effort to resolve?

thanks
henri


> Arne Koewing wrote:
> > 
> > Hi!
> > 
> > I am looking for an library for graph-manipulation/handling.
> > Do you know any implementations for ocaml?
> > 
> > thx,
> > Arne
> > 
> 
> 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' :)),
> but it is written in SML. It is not very hard to rewrite it in OCaml
> language.
> If this project will start, You may consider me as a participant. But I
> have not much
> time for such work(for me this work will be the 'fun-project').
> Let You look at MLRISC graph library and give Your opinion about the
> library
> and about the possibility of using it in Your tasks :)
> 
> The second variant. You may search caml-list for 'graph'. Some times ago
> it was
> small discussion there about exactly the same problem. You may find some
> links to less powerfull and universal graph libraries but written in
> ocaml.
> 
> Regards!
> GNS
> 
> 

-------------------
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

Re: [Caml-list] Graphmanipulation in Ocaml

[Diego Olivier Fernandez Pons]

    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

Re: [Caml-list] Graphmanipulation in Ocaml

[Eray Ozkural]

On Wednesday 17 September 2003 11:29, Diego Olivier Fernandez Pons wrote:
> 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.

Ouch. *That* would be a problem.

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C

-------------------
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

Re: [Caml-list] Graphmanipulation in Ocaml

[Diego Olivier Fernandez Pons]

    Bonjour,

> Does anyone have experience porting Sml code to Caml ? I would
> expect everything is fairly mechanic, or can there be differences
> which require non-trivial effort to resolve ?

I have some experience porting from Haskell (Edison, Parsec), SML
(parts of SML/NJ standard library, parts of MLKit standard library,
some code from Erwig FGL and some code from Nikolaj Bjorner which
seems to have been used in the stanford temporal prover).

Porting is easy and fast. Redesigning is hard and slow.

example : SML has (or had) two kind of polymorphic variables 'a and
''a because of the polymorphic comparison problem. The first time you
port SML code you just don't care since the resulting Caml code seems
to be working fine (the first time I didn't even notice it since I
never type-checked the SML code).

The problem is that not having a correct polymorphic comparison will
lead to several work around according to who wrote the SML code :
functors, functions with a comparison function argument, records
saving a generic comparison function, etc. And this will give to the
whole library a specific 'style' (even if the original problem -
whatever it may be - was solved in a next version of the language)

There is a very old discussion on the Caml list when the first Set
module was released by Xavier Leroy
(http://caml.inria.fr/caml-list-ar/0096.html) which gives you an idea
of the problems one can face :
- 'a ->'a -> int comparison or Smaller | Equal | Greater
- functors, polymorphic data structures, objects or records ?
- generic or specific ?
- public or private constructors ?
- dirty imperative but fast tricks or pure and beautiful functional ?

And since you are working in Caml you will want your library to have
more caracteristic Caml style. There begins the hard part.

Conclusion : no really difficult points from SML to Caml (most of the
time you just guess what is happening and what to do). You may look at
SML vs. Caml (http://www.ps.uni-sb.de/~rossberg/SMLvsOcaml.html) which
is a bit out of date with respect to the Caml part (I have asked
Andreas Rossberg several times to update it but he does not seem to
want to).

        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

Re: [Caml-list] Graphmanipulation in Ocaml

[Gleb N. Semenov]

henridf@lcavsun1.epfl.ch wrote:

>judging by the interface and docs, it looks pretty nice.
>i would be glad to have this in caml.
>
>i still would like to browse the code before deciding, but i am quite 
>tempted to take this on as a little project.
>
>does anyone have experience porting sml code to caml? i would expect 
>everything is fairly mechanic, or can there be differences which require 
>non-trivial effort to resolve?
>

The main problem will be to 'translate' code structure from SMLNJ module 
system to Ocaml'
modules and classes. The library as You can see is written in OO-style 
but whithout classes
(due to the absense of classes in SML :)) ).  So the main problem  is 
usual -- code stucture
and the general design.  The rest -- is mechanical coding:)

Somewere in documentation for SMLNJ(if my mind does non fail me) I have 
founded the
description of the differences between SML and OCaml.The most of them 
are concerning
the syntax.

>
>thanks
>henri
>
>
>  
>
>>Arne Koewing wrote:
>>    
>>
>>>Hi!
>>>
>>>I am looking for an library for graph-manipulation/handling.
>>>Do you know any implementations for ocaml?
>>>
>>>thx,
>>>Arne
>>>
>>>      
>>>
>>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' :)),
>>but it is written in SML. It is not very hard to rewrite it in OCaml
>>language.
>>If this project will start, You may consider me as a participant. But I
>>have not much
>>time for such work(for me this work will be the 'fun-project').
>>Let You look at MLRISC graph library and give Your opinion about the
>>library
>>and about the possibility of using it in Your tasks :)
>>
>>The second variant. You may search caml-list for 'graph'. Some times ago
>>it was
>>small discussion there about exactly the same problem. You may find some
>>links to less powerfull and universal graph libraries but written in
>>ocaml.
>>

Regards!
GNS

-- 
Gleb N. Semenov     | 127015, Bol.Novodmitrovskaya St 14-1, Moscow, Russia
Security Specialist | Phone: +7(095)411-7601   Fax: +7(095)411-7602
Jet Infosystems     | E-mail: semenov@jet.msk.su



-------------------
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

Re: [Caml-list] Graphmanipulation in Ocaml

[Andreas Rossberg]

Diego Olivier Fernandez Pons wrote:
> 
> Conclusion : no really difficult points from SML to Caml (most of the
> time you just guess what is happening and what to do). You may look at
> SML vs. Caml (http://www.ps.uni-sb.de/~rossberg/SMLvsOcaml.html) which
> is a bit out of date with respect to the Caml part (I have asked
> Andreas Rossberg several times to update it but he does not seem to
> want to).

Well, actually, I recall only one such occasion. I have since 
incorparated some of your comments and explained why I didn't do so for 
  some others. Of course, I may have overlooked something, so I am 
always open to further suggestions. Which part of the page you think is 
no longer up-to-date, or what is missing, particularly with respect to 
the SML->OCaml direction in question?

(But please always bear in mind that the page intentionally makes no 
attempt to cover constructs that cannot be mapped reasonably between 
languages, e.g. objects, poly variants, user-defined fixity, advanced 
library issues, etc.)

In the light of this thread I may add a section about comparisons and 
eqtypes. I hesitate because the simplistic tabular form of the page 
seems a bit unsuited to cope with the respective subtleties properly. 
Any ideas welcome.

	- Andreas

-- 
Andreas Rossberg, rossberg@ps.uni-sb.de

"Computer games don't affect kids; I mean if Pac Man affected us
  as kids, we would all be running around in darkened rooms, munching
  magic pills, and listening to repetitive electronic music."
  - Kristian Wilson, Nintendo Inc.

-------------------
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

Re: [Caml-list] Graphmanipulation in Ocaml

[Gleb N. Semenov]

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