From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id XAA04600; Thu, 29 Jan 2004 23:19:09 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA05006 for ; Thu, 29 Jan 2004 23:19:08 +0100 (MET) Received: from mwinf0304.wanadoo.fr (smtp3.wanadoo.fr [193.252.22.28]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id i0TMJ7P01888 for ; Thu, 29 Jan 2004 23:19:08 +0100 (MET) Received: from oops (ARennes-303-1-12-224.w81-49.abo.wanadoo.fr [81.49.95.224]) by mwinf0304.wanadoo.fr (SMTP Server) with ESMTP id 72823A804114; Thu, 29 Jan 2004 23:19:07 +0100 (CET) Received: from david by oops with local (Exim 3.35 #1 (Debian)) id 1AmKV8-0000za-00; Thu, 29 Jan 2004 23:19:06 +0100 To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) Cc: Thomas Fischbacher , signoles@pc8-123.lri.fr, conchon@pc8-123.lri.fr, caml-list@inria.fr Subject: Re: [Caml-list] poll for a graph library References: <16408.64997.828000.931868@gargle.gargle.HOWL> <16409.2937.135897.374276@gargle.gargle.HOWL> From: David MENTRE Organization: none Date: Thu, 29 Jan 2004 23:19:04 +0100 In-Reply-To: <16409.2937.135897.374276@gargle.gargle.HOWL> (Jean-Christophe Filliatre's message of "Thu, 29 Jan 2004 14:32:41 +0100") Message-ID: <878yjqtn3b.fsf@linux-france.org> User-Agent: Gnus/5.1006 (Gnus v5.10.6) Emacs/21.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 dmentre:01 filliatre:01 filliatre:01 lri:01 vertices:01 hash:01 vertices:01 functors:01 re-use:01 transitive:01 bfs:99 graphviz:01 recognized:99 dmentre:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Hello Jean-Christophe, I'm using a specific graph in one of my program, hence the following questions. Jean-Christophe Filliatre 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é ------------------- 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