From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA25183; Thu, 27 Sep 2001 13:42:05 +0200 (MET DST)
X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id NAA25090 for caml-list@pauillac.inria.fr; Thu, 27 Sep 2001 13:42:04 +0200 (MET DST)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id XAA11758 for <caml-list@pauillac.inria.fr>; Wed, 26 Sep 2001 23:48:50 +0200 (MET DST)
Received: from ugly.gaggle ([12.18.157.162])
	by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id f8QLmnn09453
	for <caml-list@inria.fr>; Wed, 26 Sep 2001 23:48:49 +0200 (MET DST)
Received: from kenny.gaggle (kenny.gaggle [192.168.168.230])
	by ugly.gaggle (8.9.3/8.9.3) with ESMTP id OAA26321
	for <caml-list@inria.fr>; Wed, 26 Sep 2001 14:48:42 -0700
Received: by kenny.gaggle with Internet Mail Service (5.5.2653.19)
	id <T38K5F4G>; Wed, 26 Sep 2001 14:50:19 -0700
Message-ID: <6B2758E78474D411958F00D0B78906006A6BD8@kenny.gaggle>
From: Chris Tilt <cet@webcriteria.com>
To: caml-list@inria.fr
Subject: RE: [Caml-list] Looking for Graph Operations-library
Date: Wed, 26 Sep 2001 14:50:14 -0700
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2653.19)
Content-Type: text/plain;
	charset="iso-8859-1"
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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