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 TAA06887; Wed, 26 Sep 2001 19:08:51 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA06884 for ; Wed, 26 Sep 2001 19:08:50 +0200 (MET DST) Received: from chopin.ai.univie.ac.at (chopin.ai.univie.ac.at [131.130.174.170]) by nez-perce.inria.fr (8.11.1/8.10.0) with ESMTP id f8QH8nf04441 for ; Wed, 26 Sep 2001 19:08:49 +0200 (MET DST) Received: (from markus@localhost) by chopin.ai.univie.ac.at (8.9.3/8.9.3/Debian 8.9.3-21) id TAA27723; Wed, 26 Sep 2001 19:08:44 +0200 Date: Wed, 26 Sep 2001 19:08:44 +0200 From: Markus Mottl To: Mattias Waldau Cc: caml-list@inria.fr Subject: Re: [Caml-list] Looking for Graph Operations-library Message-ID: <20010926190844.A25799@chopin.ai.univie.ac.at> References: <93.10ca38c3.28e32ce0@aol.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2.5i In-Reply-To: ; from mattias.waldau@abc.se on Wed, Sep 26, 2001 at 18:47:50 +0200 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Wed, 26 Sep 2001, Mattias Waldau wrote: > I am converting some code from SICStus Prolog, and need a directed graph > library for Ocaml. Any pointers? > > I found Markus Mottl's POMAP, and I can probably redesign in order to use > that instead. Yes, this should be possible. The internal datastructure used to represent partially ordered maps is actually a (purely functional) directed graph. Maybe not optimal for all purposes, but fast enough for many and additionally allows persistent sharing of datastructures, which is also a nice feature. > transitive_closure(+Graph, -Closure) > Computes Closure as the transitive closure of Graph in O(N^3) time. > > symmetric_closure(+Graph, -Closure) > Computes Closure as the symmetric closure of Graph, i.e. for each edge (u,v) > in Graph, add its symmetric edge (v,u). Takes O(N^2) time. This is useful > for making a directed graph undirected. Should be straightforward. > top_sort(+Graph, -Sorted) > Finds a topological ordering of a Graph and returns the ordering as a list > of Sorted vertices. Fails iff no ordering exists, i.e. iff the graph > contains cycles. Takes O(N^2) time. A similar function is already implemented (topo_fold). Because the partially ordered map represents a Hasse-diagram, this function is really fast. Of course, you are likely to spend the O(N^2) computation time elsewhere, namely during the creation of the Hasse-diagram. Regards, Markus Mottl -- Markus Mottl markus@oefai.at Austrian Research Institute for Artificial Intelligence http://www.oefai.at/~markus ------------------- 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