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:  Mattias Waldau <mattias.waldau@a...> 
Subject:  [Camllist] Looking for Graph Operationslibrary 
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 (vertexneighbors) 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/camlbugs FAQ: http://caml.inria.fr/FAQ/ To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr