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 UAA32256; Fri, 18 Apr 2003 20:57:59 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA32584 for ; Fri, 18 Apr 2003 20:57:57 +0200 (MET DST) Received: from eposta.kablonet.com.tr ([62.248.102.66]) by nez-perce.inria.fr (8.11.1/8.11.1) with SMTP id h3IIvr907264 for ; Fri, 18 Apr 2003 20:57:54 +0200 (MET DST) Received: (qmail 47638 invoked by uid 0); 18 Apr 2003 19:05:17 -0000 Received: from unknown (HELO 195.174.169.185) (exa@195.174.169.185) by 0 with SMTP; 18 Apr 2003 19:05:17 -0000 From: Eray Ozkural Reply-To: erayo@cs.bilkent.edu.tr Organization: Bilkent University CS Dept. To: caml-list@inria.fr Subject: [Caml-list] Dynamic array and directed graph code Date: Fri, 18 Apr 2003 21:57:19 +0300 User-Agent: KMail/1.5.9 MIME-Version: 1.0 Content-Disposition: inline Content-Type: Multipart/Mixed; boundary="Boundary-00=_PqEo+XEUtxU0oQj" Message-Id: <200304182157.28979.exa@kablonet.com.tr> X-Spam: no; 0.00; eray:01 ozkural:01 hash:01 instructor:01 annoyances:01 vertices:01 topological:01 erayo:01 bilkent:01 ankara:01 kde:01 malfunction:01 ariza:01 1.2.1:01 qwb:99 X-Attachments: name="dynarray.mli" name="dynarray.mli" name="dynarray.ml" name="dynarray.ml" name="digraph.mli" name="digraph.mli" name="digraph.ml" name="digraph.ml" name="test-graph.ml" name="test-graph.ml" Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk --Boundary-00=_PqEo+XEUtxU0oQj Content-Type: Text/Plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Content-Description: clearsigned data Content-Disposition: inline =2D----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Greetings ocaml hackers! In order to be granted the status of discriminating hacker, I'm posting the= =20 code for a dynamic array module and a directed graph module. I have seen su= ch=20 structures for ocaml requested on the list and elsewhere. While doing a=20 project I needed the code that would give me the exact running time bounds = so=20 I should thank our computational geometry instructor :) Although I'm not=20 providing for a general library interface including such things as walks,=20 iterators, etc. in detail these should be sufficient to start writing=20 algorithms with. I tried to make it look like an ordinary library module. T= he=20 code is, naturally, an incomplete preliminary version and not tested widely= =20 at all, so be wary. Without further ado, I've attached the small files. This is almost my first= =20 piece of ocaml programming and therefore it is likely to contain gross styl= e=20 errors or annoyances. In particular, I've used ocaml lists for storing=20 individual adjacencies of vertices. I thought this should work due to value= =20 sharing as employed by the functional structure but I'm aware I might be=20 wrong and this probably calls for a benchmark to see if standard algorithms= =20 such as topological sort does work within the bounds. Comments welcome, =2D --=20 Eray Ozkural (exa) Comp. Sci. Dept., Bilkent University, Ankara KDE Project: http://www.kde.o= rg 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 5= 39C =2D----BEGIN PGP SIGNATURE----- Version: GnuPG v1.2.1 (GNU/Linux) iD8DBQE+oEqTfAeuFodNU5wRAsvwAJ9t/dZJL/qwB2Kj9Bso//qvnqdp+QCgo/Me ilUOF3By9YFtOR4gOAB7IN4=3D =3DnD3R =2D----END PGP SIGNATURE----- --Boundary-00=_PqEo+XEUtxU0oQj Content-Type: text/plain; charset="us-ascii"; name="dynarray.mli" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="dynarray.mli" (* ** ** ocaml module Dynarray ** ** Description: Array with dynamic size ** ** Author: Eray Ozkural (exa) , (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 --Boundary-00=_PqEo+XEUtxU0oQj Content-Type: text/plain; charset="us-ascii"; name="dynarray.ml" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="dynarray.ml" (* ** ** ocaml module Dynarray ** ** Description: Array with dynamic size ** ** Author: Eray Ozkural (exa) , (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) --Boundary-00=_PqEo+XEUtxU0oQj Content-Type: text/plain; charset="us-ascii"; name="digraph.mli" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="digraph.mli" (* ** ** ocaml module interface Digraph ** ** Description: Directed graph ADT ** implementing adjacency list representation ** ** Author: Eray Ozkural (exa) , (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 *) --Boundary-00=_PqEo+XEUtxU0oQj Content-Type: text/plain; charset="us-ascii"; name="digraph.ml" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="digraph.ml" (* ** ** ocaml module implementation Digraph ** ** Description: Directed graph ADT ** implementing adjacency list representation ** ** Author: Eray Ozkural (exa) , (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" --Boundary-00=_PqEo+XEUtxU0oQj Content-Type: text/plain; charset="us-ascii"; name="test-graph.ml" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="test-graph.ml" 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(); --Boundary-00=_PqEo+XEUtxU0oQj-- ------------------- 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/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners