open Printf
   
module M = Map.Make(String)
module S = Set.Make(String)

(************* definirea grafurilor ************)

let edges = [ ("a", "b"); ("b", "e"); ("e", "a");
  ("b", "f"); ("e", "f"); ("b", "c"); ("c", "d"); ("d", "c");
  ("d", "h"); ("h", "d"); ("h", "g"); ("f", "g"); ("g", "f") ]

let add_edge_list graf (u, v) =
  let vecini = try M.find u graf with Not_found -> []
  in M.add u (v :: vecini) graf

let add_edge_set graf (u, v) =
  let vecini = try M.find u graf with Not_found -> S.empty
  in let gplus = M.add u (S.add v vecini) graf
     in if M.mem v graf then gplus else M.add v S.empty gplus

let grlist = List.fold_left add_edge_list M.empty edges
let grset = List.fold_left add_edge_set M.empty edges

(*************** afișare ************)
          
let dotfile = "grtrav.dot"

let showstep gr noi viz edgeiter =
  let nodes = M.fold (fun k _ -> S.add k) gr S.empty in
  let f = open_out dotfile in
  let printedge n dest =
    fprintf f  "%s -> { " n;
    edgeiter (fprintf f "%s ") dest; output_string f "}\n"
  in
  output_string f "digraph {\n";
  S.iter (fun n -> output_string f n;
                   output_string f (if S.mem n noi then " [color=red] "
                                    else if S.mem n viz then " [style=filled] "
                                    else " ")) nodes;
  M.iter printedge gr;
  output_string f "}\n";
  close_out f;
  Sys.command ("dotty " ^ dotfile) |> ignore; read_line() |> ignore

(*********** parcurgere în adâncime **************)
  
let dfs gr =
  let rec dfs1 vazute nod = 
    if S.mem nod vazute then vazute
    else (
      showstep gr (S.singleton nod) vazute List.iter;
    
      let vecini = M.find nod gr
      in List.fold_left dfs1 (S.add nod vazute) vecini
    )
  in dfs1 S.empty

(************ parcurgere prin cuprindere **************)

let bfs gr start =
  let vecini n = M.find n gr in
  let rec pas vazute curente =
    showstep gr curente vazute S.iter;        (* scrie; afișează; așteaptă enter *)

    (* pentru fiecare nod nou, adaugă vecinii la mulțimea celor văzute *)
    let vazut_plus = S.fold (fun n -> vecini n |> S.union) curente vazute
    in let noi = S.diff vazut_plus vazute        (* am găsit noduri noi ? *)
       in if S.is_empty noi then vazute else pas vazut_plus noi        (* continuă? *)
  in pas start start
  
(* let all1 = dfs grlist "a" (* |> S.elements *) *)
let all2 = bfs grset (S.singleton "a") (* |> S.elements *)

This document was generated using caml2html