* Re: [Caml-list] poll for a graph library
2004-01-29 13:32 ` Jean-Christophe Filliatre
@ 2004-01-29 14:10 ` Jacques Carette
2004-01-29 14:31 ` Andrew Bagdanov
` (4 subsequent siblings)
5 siblings, 0 replies; 10+ messages in thread
From: Jacques Carette @ 2004-01-29 14:10 UTC (permalink / raw)
To: Jean-Christophe Filliatre, Thomas Fischbacher
Cc: signoles, conchon, caml-list
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] poll for a graph library
2004-01-29 13:32 ` Jean-Christophe Filliatre
2004-01-29 14:10 ` Jacques Carette
@ 2004-01-29 14:31 ` Andrew Bagdanov
2004-01-31 13:40 ` Eray Ozkural
2004-01-29 14:54 ` Plotting library (was: Re: [Caml-list] poll for a graph library) Richard Jones
` (3 subsequent siblings)
5 siblings, 1 reply; 10+ messages in thread
From: Andrew Bagdanov @ 2004-01-29 14:31 UTC (permalink / raw)
To: Jean-Christophe Filliatre; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Plotting library (was: Re: [Caml-list] poll for a graph library)
2004-01-29 13:32 ` Jean-Christophe Filliatre
2004-01-29 14:10 ` Jacques Carette
2004-01-29 14:31 ` Andrew Bagdanov
@ 2004-01-29 14:54 ` Richard Jones
2004-01-29 17:21 ` [Caml-list] poll for a graph library Jocelyn Sérot
` (2 subsequent siblings)
5 siblings, 0 replies; 10+ messages in thread
From: Richard Jones @ 2004-01-29 14:54 UTC (permalink / raw)
To: caml-list
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] poll for a graph library
2004-01-29 13:32 ` Jean-Christophe Filliatre
` (2 preceding siblings ...)
2004-01-29 14:54 ` Plotting library (was: Re: [Caml-list] poll for a graph library) Richard Jones
@ 2004-01-29 17:21 ` Jocelyn Sérot
2004-01-29 22:19 ` David MENTRE
2004-01-30 18:24 ` brogoff
5 siblings, 0 replies; 10+ messages in thread
From: Jocelyn Sérot @ 2004-01-29 17:21 UTC (permalink / raw)
To: Jean-Christophe Filliatre; +Cc: caml-list
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] poll for a graph library
2004-01-29 13:32 ` Jean-Christophe Filliatre
` (3 preceding siblings ...)
2004-01-29 17:21 ` [Caml-list] poll for a graph library Jocelyn Sérot
@ 2004-01-29 22:19 ` David MENTRE
2004-01-30 18:24 ` brogoff
5 siblings, 0 replies; 10+ messages in thread
From: David MENTRE @ 2004-01-29 22:19 UTC (permalink / raw)
To: Jean-Christophe Filliatre
Cc: Thomas Fischbacher, signoles, conchon, caml-list
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [Caml-list] poll for a graph library
2004-01-29 13:32 ` Jean-Christophe Filliatre
` (4 preceding siblings ...)
2004-01-29 22:19 ` David MENTRE
@ 2004-01-30 18:24 ` brogoff
5 siblings, 0 replies; 10+ messages in thread
From: brogoff @ 2004-01-30 18:24 UTC (permalink / raw)
To: Jean-Christophe Filliatre
Cc: Thomas Fischbacher, signoles, conchon, caml-list
[-- 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
^ permalink raw reply [flat|nested] 10+ messages in thread