Joby Poriyath avatar Joby Poriyath committed fa5438c

Misc + Union Find algorithms for dynamic network connectivity

Comments (0)

Files changed (14)

+#directory "_build";;
+#load "util.cmo";;
+let a = Stk.create ()
+
+let main () =
+  for i = 0 to 10 
+  do
+    Stk.push i a
+  done;
+  Stk.iter (fun i -> print_string ((string_of_int i) ^ " ")) a;
+  print_newline ()
+
+let _ = main (); exit 0
+module type STACK =
+sig
+  type 'a t
+  exception Empty
+  val create : unit -> 'a t
+  val push : 'a -> 'a t -> unit
+  val pop : 'a t -> 'a
+  val clear : 'a t -> unit
+  val length : 'a t -> int
+  val iter : ('a -> unit) -> 'a t -> unit
+end
+
+let range n =
+  let rec range_aux n l =
+    if n < 0 
+    then l 
+    else range_aux (n - 1) (n :: l) in
+  range_aux (n - 1) []
+
+module MyStack : STACK =
+struct
+  type 'a t = {mutable sp : int; mutable c : 'a array}
+  exception Empty
+  let increase s e = 
+    let a = Array.make (Array.length s.c * 2 + 1) e in
+    Array.blit s.c 0 a 0 (Array.length s.c) ;
+    s.c <- a
+  let push e s = 
+    begin
+      if (s.sp = Array.length s.c) then increase s e else (); 
+      s.c.(s.sp) <- e; 
+      s.sp <- (s.sp + 1)
+    end
+  let pop s = 
+    if s.sp = 0 
+    then raise Empty 
+    else s.sp <- (s.sp - 1) ; s.c.(s.sp)
+  let clear s = 
+    s.sp <- 0; s.c <- [||]
+  let length s = s.sp
+  let create () = {sp = 0; c = [||]}
+  let iter f s =
+    let b = s.sp - 1 in
+    for i = 0 to b
+    do
+      f (s.c.(b - i))
+    done
+end    
+
+module type INT = 
+sig
+  type t
+  exception Isnul
+  val of_int : t -> t
+  val mult : t -> t -> t
+end
+
+module Int_star : INT =
+struct
+  type t = int
+  exception Isnul
+  let of_int = function 0 -> raise Isnul | n -> n
+  let mult = ( * )
+end
+
+module type S = 
+sig
+  type t
+  val create : unit -> t
+  val add : t -> unit
+  val get : t -> int
+end
+
+module M : S = 
+struct
+  type t = int ref
+  let create () = ref 0
+  let add x = incr x
+  let get x = if !x > 0 then (decr x; !x) else failwith "Empty"
+end
+
+module type S1 = 
+sig
+  type t
+  val create : unit -> t
+  val add : t -> unit
+end
+
+module type S2 = 
+sig 
+  type t
+  val get : t -> int
+end
+
+module M1 = (M : S1 with type t = M.t)
+module M2 = (M : S2 with type t = M.t)
+
+module OrderedInt : Set.OrderedType =
+struct
+  type t = int * int
+  let compare (x1, y1) (x2, y2) = 
+    if x1 > x2 then 1
+    else if x1 < x2 then -1
+    else if y1 > y2 then 1
+    else if y1 < y2 then -1
+    else 0
+end
+
+module Greet =
+struct
+  type how = Nicely | Badly
+      
+  let greet how who = 
+    match how with
+      | Nicely -> Printf.printf "Hello, %s!\n" who
+      | Badly -> Printf.printf "Oh, here is that %s again!\n" who
+end
+type how = Nicely | Badly
+      
+let greet how who = 
+  match how with
+    | Nicely -> Printf.printf "Hello, %s!\n" who
+    | Badly -> Printf.printf "Oh, here is that %s again!\n" who
+      
+(* Hello, World *)
+
+open Greet
+
+let _ = 
+  let name = (if Array.length Sys.argv > 1 then Sys.argv.(1) else "stranger") in
+  begin
+    if name = "Caesar" then greet Nicely name else greet Badly name;
+    Printf.printf "My name is %s\n" Sys.argv.(0)
+  end
+
+
+    
+  
+10
+union 9 6
+union 1 2
+union 8 4
+union 8 3
+union 1 6
+union 7 4
+union 8 2
+union 9 0
+union 9 5
+let _ = Uf.main ()
+type 'a t = {mutable c : 'a list}
+exception Stk_empty
+  
+let create () = {c = []}
+
+let push e st = st.c <- e :: st.c
+
+let pop st = match st.c with
+  | hd :: tl -> st.c <- tl; hd
+  | [] -> raise Stk_empty
+
+let iter f st = List.iter f st.c
+
+let length st = List.length st.c
+    
+let is_empty st = (st.c = [])
+type 'a t
+
+exception Stk_empty
+
+val create : unit -> 'a t
+val push : 'a -> 'a t -> unit
+val pop : 'a t -> 'a
+val length : 'a t -> int
+val iter : ('a -> unit) -> 'a t -> unit
+let read_lines in_c =
+  let rec read_lines_aux lst =
+    try
+      let line = input_line in_c in
+      read_lines_aux (line :: lst)
+    with End_of_file -> lst
+  in read_lines_aux []
+    
+    
+let ls () =
+  let (in_c, out_c, err_c) = Unix.open_process_full "ssh ubuntu 'uname -a'" (Unix.environment ()) in
+  let lines = List.rev (read_lines in_c) in
+  let err_lines = List.rev (read_lines err_c) in
+  begin
+    List.iter (fun i -> print_string "--- "; print_string i; print_newline ()) lines;
+    List.iter (fun i -> print_string "--- "; print_string i; print_newline ()) err_lines;
+    ignore (Unix.close_process_full (in_c, out_c, err_c))
+  end
+
+let _ = ls ()
+            
+
+module type UF =
+sig
+  type t
+  val init: int -> t
+  val union: t -> int -> int -> unit
+  val connected : t -> int -> int -> bool
+  val print : t -> unit
+end
+
+module QuickfindUF : UF =
+struct
+  
+  type t = int array
+  
+  let init n = 
+    let a = Array.make n 0 in
+    for i = 0 to (n - 1) do a.(i) <- i done;
+    a
+
+  let union a i j =
+    let i_val = a.(i) in
+    let j_val = a.(j) in
+    for i = 0 to (Array.length a - 1)
+    do
+      if a.(i) = i_val then a.(i) <- j_val
+    done
+
+  let connected a i j = (a.(i) = a.(j))
+
+  let print a =
+    (Array.iter (fun i -> Printf.printf "%d " i) a; print_newline ())
+
+end
+
+module QuickUnionUF : UF =
+struct
+
+  type t = int array
+
+  let init n = 
+    let a = Array.make n 0 in
+    for i = 0 to (n - 1) do a.(i) <- i done;
+    a
+
+  let rec root a i = 
+    if i = a.(i) then i else root a a.(i)
+
+  let connected a i j =
+    let i_root = root a i in
+    let j_root = root a j in
+    i_root = j_root
+
+  let union a i j = 
+    let i_root = root a i in
+    let j_root = root a j in
+    (* Make j's root the parent of i's root *)
+    a.(i_root) <- j_root
+
+  let print a =
+    (Array.iter (fun i -> Printf.printf "%d " i) a; print_newline ())
+
+end
+
+module WeightedUnion : UF =
+struct
+  type t = {a : int array; sz : int array}
+      
+  let init n = 
+    let a = Array.make n 0 in
+    let sz = Array.make n 1 in
+    for i = 0 to (n - 1) do a.(i) <- i done;
+    {a = a; sz = sz}
+
+  let rec root a i = 
+    if a.a.(i) = i then i else root a a.a.(i)
+
+  let connected a i j =
+    let i_root = root a i in
+    let j_root = root a j in
+    i_root = j_root
+
+  let union a i j = 
+    let i_root = root a i in
+    let j_root = root a j in
+    let i_sz = a.sz.(i) in
+    let j_sz = a.sz.(j) in
+    
+    if i_sz < j_sz 
+    then
+      begin
+        a.a.(i_root) <- j_root;
+        a.sz.(j) <- j_sz + i_sz
+      end
+    else
+      begin
+        a.a.(j_root) <- i_root;
+        a.sz.(i) <- i_sz + j_sz
+      end
+
+  let print a =
+    (Array.iter (fun i -> Printf.printf "%d " i) a.a; print_newline ())
+      
+end
+
+module WeightedPathCompressedUF1 : UF = 
+struct
+
+  type t = {a : int array; sz : int array}
+      
+  let init n = 
+    let a = Array.make n 0 in
+    let sz = Array.make n 1 in
+    for i = 0 to (n - 1) do a.(i) <- i done;
+    {a = a; sz = sz}
+
+  let root a i = 
+    let rec root_aux i = 
+      if a.a.(i) = i then i else root_aux a.a.(i) in
+    let rec set_root i root = 
+      if i = root  then () 
+      else 
+        let p = a.a.(i) in
+        (a.a.(i) <- root; set_root p root) in
+    let r = root_aux i in
+    (set_root i r; r)
+
+  let connected a i j =
+    let i_root = root a i in
+    let j_root = root a j in
+    i_root = j_root
+
+  let union a i j = 
+    let i_root = root a i in
+    let j_root = root a j in
+    let i_sz = a.sz.(i) in
+    let j_sz = a.sz.(j) in
+    
+    if i_sz < j_sz 
+    then
+      begin
+        a.a.(i_root) <- j_root;
+        a.sz.(j) <- j_sz + i_sz
+      end
+    else
+      begin
+        a.a.(j_root) <- i_root;
+        a.sz.(i) <- i_sz + j_sz
+      end
+  
+  let print a =
+    (Array.iter (fun i -> Printf.printf "%d " i) a.a; print_newline ())
+      
+end
+
+module U = WeightedUnion
+
+let main () =
+  
+  let n = int_of_string (input_line stdin) in
+  let a = U.init n in
+  let rec get_line () =
+    try 
+      let line = String.trim (input_line stdin) in
+      if line = "" then get_line () else Some line
+    with End_of_file -> None 
+  in 
+  let loop = ref true in
+  while !loop do
+    match get_line () with
+      | None -> (loop := false; U.print a)
+      | Some line ->
+        let words = Util.split line in
+        let cmd = List.hd words in
+        let i = int_of_string (List.nth words 1) in
+        let j = int_of_string (List.nth words 2) in
+        match cmd with
+          | "union" ->
+            begin
+              U.union a i j;
+              print_string line;
+              print_newline ()
+            end
+          | "connected" -> 
+            begin
+              print_string (line ^ " " ^ string_of_bool (U.connected a i j));
+              print_newline ()
+            end
+          | _ -> failwith ("unknown command: " ^ cmd)
+  done
+    
+(* utility functions *)
+
+let is_whitespace = function
+  | ' ' | '\n' | '\t' | '\r' -> true
+  | _ -> false
+
+let split_on fn s =
+  let s_len = String.length s in
+  let rec sub_string lst i j =
+    if j == s_len then String.sub s i (j - i) :: lst
+    else if fn (s.[j]) then sub_string (String.sub s i (j - i) :: lst) (j + 1) (j + 1)
+    else sub_string lst i (j + 1)
+  in
+  List.rev (sub_string [] 0 0)
+
+(* Same as Python's split *)
+let split s = List.filter (function s -> s <> "") (split_on is_whitespace s)
+
+let strip s =
+  let s_len = String.length s in
+  let rec index_l i =
+    if i = s_len then (i - 1) 
+    else if is_whitespace (s.[i]) then index_l (i + 1)
+    else i in
+  let rec index_r i j = 
+    if (j = i) then j
+    else if j <= 0 then 0
+    else if is_whitespace (s.[j]) then index_r i (j - 1)
+    else j + 1 in
+  let i = index_l 0 in
+  let j = index_r i (s_len - 1) in
+  if s = "" then "" else String.sub s i (j - i)
+  
+
+let rec join s = function
+  | [] -> ""
+  | (w::ws) -> (w ^ s) ^ join s ws
+
+(* end of utility functions *)
+val split_on : (char -> bool) -> string -> string list
+val split : string -> string list
+val join : string -> string list -> string
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.