(* functii de uz general *)
let comp f g x = f (g x)
                   
let repeat transf cond =        (* repeta transformarea pana cond e true *)
  let rec rep v =
    let nxt = transf v in
    if cond nxt then nxt else rep nxt
  in rep

module type NODE = sig        (* tip pentru nod, cu comparatie si tiparire *)
    type t
    val compare: t -> t -> int          (* necesar pt. multimi *)
    val print: t -> unit
  end
                     
module Graph(Node: NODE) = struct
  module M = Map.Make(Node)
  module S = Set.Make(Node)

  (* succesorii lui n, sau multimea vida *)
  let find0 gr n = try M.find n gr with Not_found -> S.empty

  let set_of_list lst = List.fold_right S.add lst S.empty

  let build_graph =
    List.fold_left (fun dict (src, nodes)
                    -> M.add src (set_of_list nodes) dict) M.empty

  let dfs gr n =        (* cautare in adancime in gr de la nodul n *)
    let rec dfs1 n vis = (* vis = multimea de noduri vizitate *)
      if S.mem n vis then vis        (* nod deja atins, multime neschimbata *)
      else (Node.print n; print_newline();
            S.fold dfs1 (find0 gr n) (S.add n vis))
    in dfs1 n S.empty

  (* nodurile atinse din multimea s intr-un pas *)
  let step gr s = S.fold (comp S.union (find0 gr)) s S.empty

  let bfs gr n =        (* cautare in largime *)
    let ns = S.singleton n in
    repeat (fun (all, nxt) ->
            List.iter Node.print (S.elements nxt); print_newline();
            let nxt1 = step gr nxt in (S.union nxt1 all, S.diff nxt1 all))
           (comp S.is_empty snd) (ns, ns)        
end
                             
module Int = struct 
  type t = int
  let compare = compare
  let print = print_int
end
module G = Graph(Int)
                
let pairlst = [(1, [2; 5; 8]); (2, [3]); (3, [4]);
               (4, [2]); (5, [6]); (6, [3; 7; 8])]
let g = G.build_graph pairlst
;;
  G.dfs g 1
;;
  G.bfs g 1

This document was generated using caml2html