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

[David MENTRE <dmentre@linux-france.org>]

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