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

RE: [Caml-list] Looking for Graph Operations-library
• Chris Tilt
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2001-09-27 (11:42) From: Chris Tilt Subject: RE: [Caml-list] Looking for Graph Operations-library
```Although I am not an accomplished functional programmer,
I would be happy to share a parameterized (functor-based)
graph module that provides basic directed graph data
structures and itterators. It allows arbitrary vertex
and edge types with the use of a functor interface. There
is also an accompanying algorithm module that currently
only implements shortest path and a skeleton function.
Let me know it sounds useful. I included the signature
below (sorry for the extra length). Performance is good
even though the vertex and edge maps are purely functional.
A pretty printer uses the graphviz "dot" format. Sorry
there is no parser :-(

Cheers, Chris
mailto:cet@webcriteria.com

(* Module [Pgraph]: graphs over ordered vertex identifiers with
parameterized vertex, and edge types *)

module type ParameterizedGraphType =
sig
type t
(* type of the vertex identifier *)
type edge
(* edge attributes *)
type vertex
(* vertex attributes *)
val compare: t -> t -> int
(* compare is used to order vid *)
val formatEdge: t -> t -> edge -> string
val formatVertex: t -> vertex -> string
end

module type S =
sig
type vid
type pVertex
type pEdge
type vertex = Vertex of vid * pVertex
type edge = Edge of vid * vid * pEdge
type t
type graph = t

module GraphAttributes : ParameterizedGraphType
module VertexMap : Map.S with type key = vid

val empty: t
val isEmpty: t -> bool
val numVertices: t -> int
val numEdges: t -> int
val vidOf: vertex -> vid
(* find a vertex by name, throws Not_found if vid not in graph *)
val vertexOf: vid -> t -> vertex
val numEdgeDuplicates: vid -> vid -> t -> int
val firstChildOf: vid -> t -> vid
val vertexAttributeOf: vid -> t -> pVertex
val hasVertex: vid -> t -> bool
val removeAllEdges: t -> t
val hasEdge: vid -> vid -> t -> bool
val addVertex: vertex -> t -> t
val addEdge: edge -> t -> t
is the result of applying the supplied accumulator function
to the old edge value and supplied edge value *)
val addEdgeAccumulate: edge -> (edge -> edge -> edge) -> t -> t
val edges: t -> edge list
val vertices: t -> vertex list
val edgesFrom: vid -> t -> edge list
val edgesTo: vid -> t -> edge list
val mapVertices: (vertex -> vertex) -> t -> t
(* applies a mapping function to all vertices in the graph,
replacing each vertex in the graph with the result of the
function application. Careful if you change the vid *)
val iterVertices: (vertex -> unit) -> t -> unit
val iterEdges: (edge -> unit) -> t -> unit
val formatEdge: edge -> string
val formatVertex: vertex -> string
val printDotGraph: string -> out_channel -> t -> unit

end
-------------------
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
-------------------
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

```