Re: [Caml-list] poll for a graph library

[Andrew Bagdanov <andrew@science.uva.nl>]

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