Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

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                                   
Austrian Research Institute
for Artificial Intelligence        
Bug reports:  FAQ:
To unsubscribe, mail  Archives: