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 WAA10806; Wed, 26 Sep 2001 22:50:50 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id WAA10736 for caml-list@pauillac.inria.fr; Wed, 26 Sep 2001 22:50:49 +0200 (MET DST) 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 SAA05813 for ; Wed, 26 Sep 2001 18:44:56 +0200 (MET DST) Received: from maild.telia.com (maild.telia.com [194.22.190.101]) by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f8QGitn03912 for ; Wed, 26 Sep 2001 18:44:55 +0200 (MET DST) Received: from d1o849.telia.com (d1o849.telia.com [213.66.248.241]) by maild.telia.com (8.11.6/8.11.6) with ESMTP id f8QGisQ09201 for ; Wed, 26 Sep 2001 18:44:54 +0200 (CEST) Received: from gateway (h40n2fls34o849.telia.com [217.208.235.40]) by d1o849.telia.com (8.10.2/8.10.1) with SMTP id f8QGisa06148 for ; Wed, 26 Sep 2001 18:44:54 +0200 (CEST) From: "Mattias Waldau" To: Subject: [Caml-list] Looking for Graph Operations-library Date: Wed, 26 Sep 2001 18:44:45 +0200 Message-ID: MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook IMO, Build 9.0.2416 (9.0.2911.0) In-Reply-To: <93.10ca38c3.28e32ce0@aol.com> X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2526.0000 Importance: Normal Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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. /mattias >>From the SICStus manual: Unweighted Graph Operations Directed and undirected graphs are fundamental data structures representing arbitrary relationships between data objects. This package provides a Prolog implementation of directed graphs, undirected graphs being a special case of directed graphs. An unweighted directed graph (ugraph) is represented as a list of (vertex-neighbors) pairs, where the pairs are in standard order (as produced by keysort with unique keys) and the neighbors of each vertex are also in standard order (as produced by sort), every neighbor appears as a vertex even if it has no neighbors itself, and no vertex is a neighbor to itself. An undirected graph is represented as a directed graph where for each edge (U,V) there is a symmetric edge (V,U). Some operations: ================ 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. 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. ------------------- 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