(* 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