(* Given an array, mtd, with entries (int * int * float) where the float is ds2 between the identified vertices, returns an efficient routine that given two vertices, returns the ds2. *)
let mxl mtd i j = let sz = Array.length mtd in
let n = Array.init sz (fun j -> match mtd.(j) with a, b, c ->
   if a < b then (a, b, c) else (b, a, c)) in
let vc = (let rec mx m j = if j = sz then m else mx
  (max m (match n.(j) with k, l, f ->k)) (j+1) in mx 0 0) in
(let tbl = Array.create (vc+1) [] in
for j = 0 to sz-1 do match (n.(j)) with k, l, f -> 
   tbl.(k) <- (l, f)::tbl.(k) done;
 let g i j = List.assq j tbl.(i) in
 if i < j then g i j else g j i)

(*
mxl [|1, 2, 1.4; 2, 3, 1.7; 3, 1, 2.1|] 3 2;; => 1.7
mxl [|1, 2, 1.4; 2, 3, 1.7; 3, 1, 2.1|] 1 3;; => 2.1
mxl [|1, 2, 1.4; 1, 3, 1.7; 2, 3, 2.1|] 2 1;; => 1.4
*)

let mem n =
let a = Array.make (n * (n+1)/2) (0, 0, 0.) in
let k = ref 0 in for i = 0 to n-1 do for j = i to n-1 do 
  a.(!k) <- (i, j, Random.float 1.);
  k := !k + 1 done done; mxl a;;