open Scanf
open Printf

module Node = struct
  type t = int
  let compare = compare
end

module G = Map.Make(Node)        (* graph = node -> set of nodes *)
module S = Set.Make(Node)       (* set of nodes *)

let id x = x        (* identity function *)

(* adds edge to graph, and nodes if new *)
let add_edge g src dest =
  let dset = try G.find src g with Not_found -> S.empty in
  let g = G.add src (S.add dest dset) g in
  if G.mem dest g then g else G.add dest S.empty g
  
(* all functions take a generic 'visit' node function as arg *)

(* BFS using iterator over frontier set *)
(* can add integer parameter to count depth *)
let bfs visit n g =
  let rec bfs1 frontier seen =
    if frontier <> S.empty then
      bfs1 (
        S.fold (fun n ->
          if S.mem n seen then id
          else (visit n; S.union (G.find n g))
        ) frontier S.empty
      ) (S.union seen frontier)
  in bfs1 (S.singleton n) S.empty

(* DFS; returns set of nodes seen *)
let dfs visit start g =
  let rec dfs1 n seen =
    if S.mem n seen then seen
    else (visit n; S.fold dfs1 (G.find n g) (S.add n seen))
  in dfs1 start S.empty

(* DFS using explicit stack; prints back and cross edges *)
let dfst visit start g =
  let rec dfs1 h stk seen =
    visit h;
    let stk = h :: stk in S.fold (fun n ->
      if S.mem n seen then (
        if List.mem n stk then printf "back edge %d->%d\n" h n
        else printf "cross edge %d->%d\n" h n;
        id
      ) else dfs1 n stk) (G.find h g) (S.add h seen)
  in dfs1 start [] S.empty

(* generic traversal choosing node from frontier *)
let trav visit start g =
  let rec trav1 frontier seen =
    if frontier <> S.empty then
      let n = S.choose frontier in
      let fr = S.remove n frontier in
      if S.mem n seen then trav1 fr seen
      else (visit n; trav1 (S.union fr (G.find n g)) (S.add n seen))
  in trav1 (S.singleton start) S.empty
      
let print_graph = G.iter (fun src -> S.iter (printf "%d -> %d\n" src))

let read_graph () = 
  let rec rdg g =
    try rdg (scanf " %d %d" (add_edge g))
    with End_of_file -> g
  in (printf "input graph edges: pairs of ints\n"; rdg G.empty)
;;

let g = read_graph() in
let init = fst (G.min_binding g) in
let visit = printf "visiting %d\n" in
(print_endline "Graph:"; print_graph g;
 print_endline "BFS:"; bfs visit init g;
 print_endline "DFS:"; ignore (dfs visit init g);
 print_endline "DFS-List:"; ignore (dfst visit init g);
 print_endline "Generic traversal:"; trav visit init g
)

This document was generated using caml2html