[Caml-list] poll for a graph library

[Caml-list] poll for a graph library

[Jean-Christophe Filliatre]

Dear ocaml users,

Sylvain  Conchon, Julien  Signoles  and myself  have  started a  graph
library for ocaml. Before going further and releasing this library, we
would like to get some  feedback from people currently using graphs in
ocaml applications or willing to  do so. More precisely, we would like
to  know what  kind of  operations on  the graph  structure  and graph
algorithms are commonly used by such users.

Could you please tell us if you  are the author of a graph library not
already mentioned in the ocaml hump?

Please answer privately.

-- 
Jean-Christophe Filliâtre

-------------------
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] poll for a graph library

[Jean-Christophe Filliatre]

Thomas Fischbacher writes:
 > 
 > What do you mean by "graph library"?
 > 
 > A library of graph algorithms (highly desirable - right now I am working 
 > at a problem where efficient generation of planar graphs is THE main 
 > issue, and I do it in lisp/ocaml), a graph layout library in the sense 
 > of a re-implementation of graphviz in ocaml (would also be very nice to 
 > have), or a plotting library in the sense of gnuplot?
 > 
 > I think you should clarify this a bit more on the list...

You're right, I  should have been clearer. We didn't  want to give too
many details  before the first release,  but let's go.  Our library is
currently providing

 1. Several  data  structures for  graphs  (persistent or  imperative,
    directed  or not,  with labeled  edges  or not,  etc.), sharing  a
    common minimal signature (iterators over vertices, edges, etc.)

 2. Several  algorithms  over graphs,  written  as  functors and  thus
    independently of the graph  implementation (it means you can build
    your own data structure for graphs and still re-use the algorithms
    code). Currently we have  the following algorithms coded: Tarjan's
    strongly   connected   components,   Dijkstra's   shortest   path,
    Ford-Fulkerson's maximal flow,  Warshall's transitive closure, DFS
    and BFS traversal, cycle detection.

    We  are  currently  adding   random  graph  generations  based  on
    algorithms   from  Knuth's   Stanford  GraphBase,   including  the
    generation of random planar graphs.  (This at least seems to be in
    connection with what you're doing.)

 3. Utilities, such  as a graphviz output  --- an ascii  output in the
    DOT format  to be precise (So  we are not  re-implementing a graph
    layout library).

-- 
Jean-Christophe Filliâtre

-------------------
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] poll for a graph library

[Jacques Carette]

Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> wrote:
>   2. Several  algorithms  over graphs,  written  as  functors and  thus
>      independently of the graph  implementation 

Sounds very useful.  One item I would very much like to see: when one is merely interested in using some (efficient!) 
graph algorithm, there is often a choice of data structures to be made.  Figuring out the asymptotics of each 
algorithm over each data structure is feasible, but should be quite unnecessary: it would be quite convenient if there 
were information functions [as part of the functor modules] which would output the asymptotic behaviour of the 
instantiations.

This would be especially useful as some data structure-algorithm pairs are woefully inefficient, especially when it 
comes to graphs!  

Jacques

-------------------
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] poll for a graph library

[Andrew Bagdanov]

Hi,

I'm about to begin a research project that concentrates on graph
representations and algorithmics in computer vision applications.  I
am wrapping up some work formalizing low-level image processing
patterns in OCaml, and was planning on continuing with OCaml for
higher-level analysis.

The library you describe sounds like an excellent starting point for
me.  A few things I think are important (from my perspective):

 1. Lightweight.  LEDA is, in my opinion, a mess.  Perhaps only an
    expression of my own personal syntactic prejudice, but reading my
    own LEDA code gives me a headache.

 2. Serialization.  Processing pipelines in computer vision
    applications (particularly in reseach environments) are stopped
    and started frequently to allow for tinkering in isolation.

 3. Choice of internal representation.  Despite obvious,
    problem/algorithm performance considerations, some techniques
    might call for adjacency representation (spectral methods, for
    example).

Anyway, it sounds great, and I can't wait to get my hands on it!

Cheers,

-Andy

Jean-Christophe Filliatre writes:
 > 
 > Thomas Fischbacher writes:
 >  > 
 >  > What do you mean by "graph library"?
 >  > 
 >  > A library of graph algorithms (highly desirable - right now I am working 
 >  > at a problem where efficient generation of planar graphs is THE main 
 >  > issue, and I do it in lisp/ocaml), a graph layout library in the sense 
 >  > of a re-implementation of graphviz in ocaml (would also be very nice to 
 >  > have), or a plotting library in the sense of gnuplot?
 >  > 
 >  > I think you should clarify this a bit more on the list...
 > 
 > You're right, I  should have been clearer. We didn't  want to give too
 > many details  before the first release,  but let's go.  Our library is
 > currently providing
 > 
 >  1. Several  data  structures for  graphs  (persistent or  imperative,
 >     directed  or not,  with labeled  edges  or not,  etc.), sharing  a
 >     common minimal signature (iterators over vertices, edges, etc.)
 > 
 >  2. Several  algorithms  over graphs,  written  as  functors and  thus
 >     independently of the graph  implementation (it means you can build
 >     your own data structure for graphs and still re-use the algorithms
 >     code). Currently we have  the following algorithms coded: Tarjan's
 >     strongly   connected   components,   Dijkstra's   shortest   path,
 >     Ford-Fulkerson's maximal flow,  Warshall's transitive closure, DFS
 >     and BFS traversal, cycle detection.
 > 
 >     We  are  currently  adding   random  graph  generations  based  on
 >     algorithms   from  Knuth's   Stanford  GraphBase,   including  the
 >     generation of random planar graphs.  (This at least seems to be in
 >     connection with what you're doing.)
 > 
 >  3. Utilities, such  as a graphviz output  --- an ascii  output in the
 >     DOT format  to be precise (So  we are not  re-implementing a graph
 >     layout library).
 > 
 > -- 
 > Jean-Christophe Filliâtre
 > 
 > -------------------
 > 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

-------------------
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] poll for a graph library

[Eray Ozkural]

On Thursday 29 January 2004 16:31, Andrew Bagdanov wrote:
>  1. Lightweight.  LEDA is, in my opinion, a mess.  Perhaps only an
>     expression of my own personal syntactic prejudice, but reading my
>     own LEDA code gives me a headache.

LEDA sucks quite a bit. It's a Microsoft MFC style library (read: not general 
purpose)

-- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://malfunct.iuma.com
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

Plotting library (was: Re: [Caml-list] poll for a graph library)

[Richard Jones]

On Thu, Jan 29, 2004 at 02:32:41PM +0100, Jean-Christophe Filliatre wrote:
>  > have), or a plotting library in the sense of gnuplot?

A plotting library would also be bloody useful.  So far I've written
two such libraries[1], one on top of the Gtk/lablgtk2 drawing area and
the other over OCamlGD/GD4O.  Is there a good solution to this which
I've been missing?

Rich.

[1] Not really very extensive or well-enough thought out to really
call them "libraries".

-- 
Richard Jones. http://www.annexia.org/ http://www.j-london.com/
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
http://www.winwinsales.co.uk/ - CRM improvement consultancy

-------------------
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] poll for a graph library

[Jocelyn Sérot]

Le 29 janv. 04, à 14:32, Jean-Christophe Filliatre a écrit :

>
>  3. Utilities, such  as a graphviz output  --- an ascii  output in the
>     DOT format  to be precise (So  we are not  re-implementing a graph
>     layout library).
>
Also a way of _reading_ DOT file formats ?

JS
--
E-mail: Jocelyn.Serot@l_a_s_m_e_a.u_n_i_v-bpclermont.fr
S-mail: LASMEA - UMR 6602 CNRS, Universite Blaise Pascal, 63177 Aubiere 
cedex
Tel: +33.(0)4.73.40.73.30 - Fax: +33.(0)4.73.40.72.62
http://wwwlasmea.univ-bpclermont.fr/Personnel/Jocelyn.Serot/Welcome.html
Valid e-mail: remove underscores (sorry, this is prevention against 
junk mail)

-------------------
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] poll for a graph library

[David MENTRE]

Hello Jean-Christophe,

I'm using a specific graph in one of my program, hence the following
questions.

Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr> writes:

>  1. Several  data  structures for  graphs  (persistent or  imperative,
>     directed  or not,  with labeled  edges  or not,  etc.), sharing  a
>     common minimal signature (iterators over vertices, edges, etc.)

Would your library allow to store graphs as somethink like hash table of
vertices (to able each all edges of a vertex in constant time)?

Would your library allow to store graphs with valuated edges
(i.e. storing data structure on edges)?

Would you allow several kind of edges in the same graph?


>  2. Several  algorithms  over graphs,  written  as  functors and  thus
>     independently of the graph  implementation (it means you can build
>     your own data structure for graphs and still re-use the algorithms
>     code). Currently we have  the following algorithms coded: Tarjan's
>     strongly   connected   components,   Dijkstra's   shortest   path,
>     Ford-Fulkerson's maximal flow,  Warshall's transitive closure, DFS
>     and BFS traversal, cycle detection.

Would you allow to use your algorithms with user defined functions? For
example, for cycle detection, I need to traverse the graph according to
stored values on edges and vertices, as well as accumulated values
during graph traversal.

>  3. Utilities, such  as a graphviz output  --- an ascii  output in the
>     DOT format  to be precise (So  we are not  re-implementing a graph
>     layout library).

It would have been nice to have graph display library. But I recognized
it is a difficult and very specific topic.


What would be the (approximate) size of your library? My current
graph-related code is about 475 lines, including code documentation and
autotests. I'm sure that your code is more complete and robust that
mine, and bigger also. However, it is not so easy to use external
code. :)

Yours,
d.
-- 
 David Mentré <dmentre@linux-france.org>

-------------------
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] poll for a graph library

[brogoff]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=X-UNKNOWN, Size: 2938 bytes --]

It is interesting that the authors of the C++ Boost Graph Library wrote a
paper comparing languages for their ability to support generic programming by
using the development of a graph library as an example, and one of the languages
they look at is SML. It's in the OOPSLA '03  proceedings I think.

Selfishness forces me to put in a plea for including a graph isomorphism
algorithm in your library. The application I have in mind is netlist comparison.

-- Brian



On Thu, 29 Jan 2004, Jean-Christophe Filliatre wrote:

>
> Thomas Fischbacher writes:
>  >
>  > What do you mean by "graph library"?
>  >
>  > A library of graph algorithms (highly desirable - right now I am working
>  > at a problem where efficient generation of planar graphs is THE main
>  > issue, and I do it in lisp/ocaml), a graph layout library in the sense
>  > of a re-implementation of graphviz in ocaml (would also be very nice to
>  > have), or a plotting library in the sense of gnuplot?
>  >
>  > I think you should clarify this a bit more on the list...
>
> You're right, I  should have been clearer. We didn't  want to give too
> many details  before the first release,  but let's go.  Our library is
> currently providing
>
>  1. Several  data  structures for  graphs  (persistent or  imperative,
>     directed  or not,  with labeled  edges  or not,  etc.), sharing  a
>     common minimal signature (iterators over vertices, edges, etc.)
>
>  2. Several  algorithms  over graphs,  written  as  functors and  thus
>     independently of the graph  implementation (it means you can build
>     your own data structure for graphs and still re-use the algorithms
>     code). Currently we have  the following algorithms coded: Tarjan's
>     strongly   connected   components,   Dijkstra's   shortest   path,
>     Ford-Fulkerson's maximal flow,  Warshall's transitive closure, DFS
>     and BFS traversal, cycle detection.
>
>     We  are  currently  adding   random  graph  generations  based  on
>     algorithms   from  Knuth's   Stanford  GraphBase,   including  the
>     generation of random planar graphs.  (This at least seems to be in
>     connection with what you're doing.)
>
>  3. Utilities, such  as a graphviz output  --- an ascii  output in the
>     DOT format  to be precise (So  we are not  re-implementing a graph
>     layout library).
>
> --
> Jean-Christophe Filliâtre
>
> -------------------
> 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
>

-------------------
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] poll for a graph library

[fva]

HI there

I've been using heavily annotated graphs for unfolding searches in 
artificial intelligence. I need annotations in both nodes and edges, the 
type of edges being a sum of several informations among them costs.
So incremental building and a control structure for traversal (queues, 
stacks, priority stacks) is a must. Lazy expansion of graphs would also 
be a boon, but I guess this can be coded into the functional recursion 
traversal.

Regards and thank you very much for asking. Please count me as one 
looking eagerly forwards to seeing your code working,

    F. Valverde

Jean-Christophe Filliatre wrote:

>Dear ocaml users,
>
>Sylvain  Conchon, Julien  Signoles  and myself  have  started a  graph
>library for ocaml. Before going further and releasing this library, we
>would like to get some  feedback from people currently using graphs in
>ocaml applications or willing to  do so. More precisely, we would like
>to  know what  kind of  operations on  the graph  structure  and graph
>algorithms are commonly used by such users.
>
>Could you please tell us if you  are the author of a graph library not
>already mentioned in the ocaml hump?
>
>Please answer privately.
>
>  
>

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