English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
Re: [Caml-list] Initial port of ocaml for mingw (long)
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2001-09-26 (17:08)
From: Markus Mottl <markus@m...>
Subject: Re: [Caml-list] Looking for Graph Operations-library
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.

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