[Caml-list] Dynamic array and directed graph code

[Caml-list] Dynamic array and directed graph code

[Eray Ozkural]

[-- Attachment #1: clearsigned data --]
[-- Type: Text/Plain, Size: 1818 bytes --]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Greetings ocaml hackers!

In order to be granted the status of discriminating hacker, I'm posting the 
code for a dynamic array module and a directed graph module. I have seen such 
structures for ocaml requested on the list and elsewhere. While doing a 
project I needed the code that would give me the exact running time bounds so 
I should thank our computational geometry instructor :) Although I'm not 
providing for a general library interface including such things as walks, 
iterators, etc. in detail these should be sufficient to start writing 
algorithms with. I tried to make it look like an ordinary library module. The 
code is, naturally, an incomplete preliminary version and not tested widely 
at all, so be wary.

Without further ado, I've attached the small files. This is almost my first 
piece of ocaml programming and therefore it is likely to contain gross style 
errors or annoyances. In particular, I've used ocaml lists for storing 
individual adjacencies of vertices. I thought this should work due to value 
sharing as employed by the functional structure but I'm aware I might be 
wrong and this probably calls for a benchmark to see if standard algorithms 
such as topological sort does work within the bounds.

Comments welcome,

- -- 
Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>
Comp. Sci. Dept., Bilkent University, Ankara  KDE Project: http://www.kde.org
www: http://www.cs.bilkent.edu.tr/~erayo  Malfunction: http://mp3.com/ariza
GPG public key fingerprint: 360C 852F 88B0 A745 F31B  EA0F 7C07 AE16 874D 539C
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQE+oEqTfAeuFodNU5wRAsvwAJ9t/dZJL/qwB2Kj9Bso//qvnqdp+QCgo/Me
ilUOF3By9YFtOR4gOAB7IN4=
=nD3R
-----END PGP SIGNATURE-----

[-- Attachment #2: dynarray.mli --]
[-- Type: text/plain, Size: 647 bytes --]

(*
**
** ocaml module Dynarray
**
** Description: Array with dynamic size
**
** Author: Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>, (C) 2003
**
** Copyright: See COPYING file that comes with this distribution
**
*)

type 'a dynarray = { mutable vec: 'a array; mutable size: int;
		     f: (int -> 'a) }

val make : 'a -> 'a dynarray

val length : 'a dynarray -> int

val get : 'a dynarray -> int -> 'a

val set : 'a dynarray -> int -> 'a -> unit

val vec : 'a dynarray -> 'a array

val mapa : ('a -> 'b) -> 'a dynarray -> 'b array

val mapai : (int -> 'a -> 'b) -> 'a dynarray -> 'b array

val iteri : (int -> 'a -> unit) -> 'a dynarray -> unit

[-- Attachment #3: dynarray.ml --]
[-- Type: text/plain, Size: 989 bytes --]

(*
**
** ocaml module Dynarray
**
** Description: Array with dynamic size
**
** Author: Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>, (C) 2003
**
** Copyright: See COPYING file that comes with this distribution
**
*)

type 'a dynarray = { mutable vec: 'a array; mutable size: int;
		     f: (int -> 'a) }

let make x = { vec = Array.make 1 x;
	       size = 0;
	       f = function _ -> x }

let length a = a.size

let adjust_size a ix =
  if ix+1 > a.size then a.size <- ix+1 else ();
  if ix >= Array.length a.vec then
    let new_size = max (ix+1) (Array.length a.vec * 2) in
    let new_vec = Array.init new_size a.f in
      begin
	Array.blit a.vec 0 new_vec 0 (Array.length a.vec);
	a.vec <- new_vec;
      end
  else
    ()

let get a ix =
  adjust_size a ix;
  a.vec.(ix)

let set a ix v =
  adjust_size a ix;
  a.vec.(ix) <- v

let vec a = Array.sub a.vec 0 a.size

let mapa f a = Array.map f (vec a)

let mapai f a = Array.mapi f (vec a)

let iteri f a = Array.iteri f (vec a)



[-- Attachment #4: digraph.mli --]
[-- Type: text/plain, Size: 1074 bytes --]

(*
**
** ocaml module interface Digraph
**
** Description: Directed graph ADT
** implementing adjacency list representation
**
** Author: Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>, (C) 2003
**
** Copyright: See COPYING file that comes with this distribution
**
*)

type edge = int * int
(* an edge is an ordered pair of vertices *)

type digraph

val make : unit -> digraph

val adj : digraph -> int -> int list
(* adjacency of a vertex *)

val set_adj : digraph -> int -> int list -> unit
(* set adjacency of a vertex *)

val degree : digraph -> int -> int
(* query degree of a vertex *)

val add : digraph -> edge -> unit
(* add edge with given weight *)

val remove : digraph -> edge -> unit
(* remove an edge *)

val edge_in : digraph -> edge -> bool
(* query edge *)

val vertex_in : digraph -> int -> bool
(* query vertex *)

val num_edges : digraph -> int
(* query number of edges *)

val num_vertices : digraph -> int
(* query number of vertices *)

val to_string : digraph -> string

val dot_graph : digraph -> string
(* graphviz representation of the graph *)


[-- Attachment #5: digraph.ml --]
[-- Type: text/plain, Size: 1623 bytes --]

(*
**
** ocaml module implementation Digraph
**
** Description: Directed graph ADT
** implementing adjacency list representation
**
** Author: Eray Ozkural (exa) <erayo@cs.bilkent.edu.tr>, (C) 2003
**
** Copyright: See COPYING file that comes with this distribution
**
*)

open Printf

type edge = int * int
(* an edge is an ordered pair of vertices *)

type digraph = {
  adj : (int list) Dynarray.dynarray;
}
(* adjacency list representation for directed graph *)

let make () = {
  adj = Dynarray.make [];
}

(* get neighborhood of vertex u *)

let n g u = Dynarray.get g.adj u

let adj g u = n g u

let set_adj g u a= Dynarray.set g.adj u a

let degree g u = List.length (n g u)

let add g (u,v) =
  let n = n g u in
    if not (List.exists ((=) v) n) then
      Dynarray.set g.adj u (v :: n)
    else
      ()

let remove g (u,v) =
  let n = n g u in
    Dynarray.set g.adj u (List.filter ((<>) v) n)
    
let edge_in g (u,v) =
  let n = n g u in
    List.exists ((=) v) n
  
(*let vertex_in g u = u < Dynarray.length g.adj*)

let vertex_in g u = degree g u > 0

let num_edges g =
  Array.fold_left (+) 0 (Dynarray.mapa (function x -> List.length x) g.adj)

let num_vertices g = Dynarray.length g.adj

let list_to_string el lst = "[" ^ String.concat ";" (List.map el lst)
			    ^  "]"

let edges_to_string el lst = String.concat "," (List.map el lst)

let to_string g =
  let prne i u = "(" ^ string_of_int i ^ "," ^
		 string_of_int u ^ ")" in
    "{" ^ String.concat ","
    (Array.to_list (Dynarray.mapai (fun i x -> list_to_string (prne i)
				      x) g.adj))
    ^ "}"

let dot_graph g = "TODO: dot graph here"

[-- Attachment #6: test-graph.ml --]
[-- Type: text/plain, Size: 1016 bytes --]


type graph = Digraph.digraph

let g : graph = Digraph.make ()

let main () =
  print_string "test-graph\n";
  Digraph.add g (1,3);
  Digraph.add g (0,2);
  Digraph.add g (0,1);
  Printf.printf "E=%s \n" (Digraph.to_string g);
  Digraph.add g (2,4);
  Digraph.add g (0,4);
  Digraph.add g (2,6);
  Digraph.add g (4,0);
  Digraph.add g (6,5);
  Digraph.add g (5,4);
  Digraph.add g (5,1);
  Digraph.add g (3,5);
  Printf.printf "E=%s \n" (Digraph.to_string g);
  Printf.printf "number of vertices %d \n" (Digraph.num_vertices g);
  Printf.printf "number of edges %d \n" (Digraph.num_edges g);
  Printf.printf "is (2,6) in? %b \n" (Digraph.edge_in g (2,6));
  Digraph.remove g (2,6);
  Digraph.remove g (4,0);
  Digraph.remove g (5,0); (*no such edge*)
  Printf.printf "E=%s \n" (Digraph.to_string g);
  Printf.printf "is (2,6) in? %b \n" (Digraph.edge_in g (2,6));
  Printf.printf "number of vertices %d \n" (Digraph.num_vertices g);
  Printf.printf "number of edges %d \n" (Digraph.num_edges g);
  exit 0;;

main();