[Caml-list] Looking for Graph Operations-library

["Mattias Waldau" <mattias.waldau@tacton.com>]

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