[Camllist] poll for a graph library
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20040129 (22:19) 
From:  David MENTRE <dmentre@l...> 
Subject:  Re: [Camllist] poll for a graph library 
Hello JeanChristophe, I'm using a specific graph in one of my program, hence the following questions. JeanChristophe Filliatre <JeanChristophe.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 reuse the algorithms > code). Currently we have the following algorithms coded: Tarjan's > strongly connected components, Dijkstra's shortest path, > FordFulkerson'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 reimplementing 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 graphrelated 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@linuxfrance.org>  To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners