Re: [Caml-list] Looking for Graph Operations-library

[Markus Mottl <markus@mail4.ai.univie.ac.at>]

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