Re: [Camllist] Initial port of ocaml for mingw (long)
[
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:   (:) 
From:  Markus Mottl <markus@m...> 
Subject:  Re: [Camllist] Looking for Graph Operationslibrary 
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 Hassediagram, 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 Hassediagram. 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/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr