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