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 MAA28361; Mon, 1 Oct 2001 12:00:38 +0200 (MET DST) 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 MAA28345 for ; Mon, 1 Oct 2001 12:00:38 +0200 (MET DST) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f91A06r12826; Mon, 1 Oct 2001 12:00:06 +0200 (MET DST) Received: (from fpottier@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA28319; Mon, 1 Oct 2001 12:00:06 +0200 (MET DST) Date: Mon, 1 Oct 2001 12:00:06 +0200 From: Francois Pottier To: Mattias Waldau Cc: caml-list@inria.fr Subject: Re: [Caml-list] Looking for Graph Operations-library Message-ID: <20011001120006.A27895@pauillac.inria.fr> Reply-To: Francois.Pottier@inria.fr References: <93.10ca38c3.28e32ce0@aol.com> Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="xHFwDpU9dbj6ez1V" Content-Transfer-Encoding: 8bit X-Mailer: Mutt 1.0i In-Reply-To: ; from mattias.waldau@abc.se on Wed, Sep 26, 2001 at 06:47:50PM +0200 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk --xHFwDpU9dbj6ez1V Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit > I am converting some code from SICStus Prolog, and need a directed graph > library for Ocaml. Any pointers? It is difficult to design a `universal' graph library, i.e. one that will suit most users' needs, because different applications often require different concrete representations of graphs. Perhaps (as suggested by Chris Tilt in an earlier message) the best route is to write a functorized library of graph algorithms, where each algorithm is written independently of the actual data structure used to represent the graph. Yet, even then, it is not easy to determine which set of basic operations should be supported by the structure. For instance, some algorithms are easily expressed if graph nodes are numbered sequentially, but this is a rather undesirable requirement if nodes are to be dynamically added and deleted. As another example, some algorithms can be written more efficiently if they are allowed to store data directly within every graph node, but this causes them to be non-reentrant and can also be a problem in some applications. As an example of this functorized style of programming, attached is an abstract implementation of a topological-order iterator for graphs. -- François Pottier Francois.Pottier@inria.fr http://pauillac.inria.fr/~fpottier/ --xHFwDpU9dbj6ez1V Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="topological.mli" (* $Header: /home/pauillac/formel1/fpottier/cvs/typo/topological.mli,v 1.1 2001/08/17 17:04:35 fpottier Exp $ *) module type Graph = sig type node (* The client must allow associating an integer degree with every graph node. *) val get: node -> int val set: int -> node -> unit (* The client must allow enumerating all nodes. *) val iter: (node -> unit) -> unit (* The client must allow enumerating all successors of a given node. *) val successors: (node -> unit) -> node -> unit end (* Given an acyclic graph $G$, this functor provides functions which allow iterating over the graph in topological order. Each graph traversal has complexity $O(V+E)$, where $V$ is the number of vertices in the graph, and $E$ is the number of its edges. The graph must be acyclic; otherwise, [Cycle] will be raised at some point during every traversal. *) module Sort (G : Graph) : sig exception Cycle val iter: (G.node -> unit) -> unit val fold: (G.node -> 'a -> 'a) -> 'a -> 'a end --xHFwDpU9dbj6ez1V Content-Type: text/plain; charset=us-ascii Content-Disposition: attachment; filename="topological.ml" (* $Header: /home/pauillac/formel1/fpottier/cvs/typo/topological.ml,v 1.1 2001/08/17 17:04:35 fpottier Exp $ *) module type Graph = sig type node (* The client must allow associating an integer degree with every graph node. *) val get: node -> int val set: int -> node -> unit (* The client must allow enumerating all nodes. *) val iter: (node -> unit) -> unit (* The client must allow enumerating all successors of a given node. *) val successors: (node -> unit) -> node -> unit end (* Given an acyclic graph $G$, this functor provides functions which allow iterating over the graph in topological order. Each graph traversal has complexity $O(V+E)$, where $V$ is the number of vertices in the graph, and $E$ is the number of its edges. The graph must be acyclic; otherwise, [Cycle] will be raised at some point during every traversal. *) module Sort (G : Graph) = struct (* Auxiliary function. *) let increment node = G.set (G.get node + 1) node (* The main iterator. *) exception Cycle let fold action accu = (* Compute each node's in degree. *) G.iter (G.set 0); G.iter (G.successors increment); (* Create a queue and fill it with all nodes of in-degree 0. At the same time, count all nodes in the graph. *) let count = ref 0 in let queue = Queue.create() in G.iter (fun node -> incr count; if G.get node = 0 then Queue.add node queue ); (* Walk the graph, in topological order. *) let rec walk accu = if Queue.length queue = 0 then if !count > 0 then raise Cycle else accu else let node = Queue.take queue in let accu = action node accu in decr count; G.successors (fun successor -> let degree = G.get successor - 1 in G.set degree successor; if degree = 0 then Queue.add successor queue ) node; walk accu in walk accu let iter action = fold (fun node () -> action node) () end --xHFwDpU9dbj6ez1V-- ------------------- Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr