RE: [Caml-list] Looking for Graph Operations-library

[Chris Tilt <cet@webcriteria.com>]

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
	(* addEdgeAccumulate adds/updates an edge where the edge value
	   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