Module Graphs
type a dgraph =
Graph of (a ® a list)
exception Not_Found
let dfs (g: a dgraph) (p: a ® bool) (start: a) =
match g with Graph succ ®
let rec search visited l =
match l with
[ ] ® raise Not_Found
| a::rl ®
if (List.mem a visited)
then (search visited rl)
else
if (p a)
then a
else search (a::visited) (rl @ (succ a))
in
search [ ] [start]
let dfs_collect (g: a dgraph) (p: a ® bool) (start: a) : a list =
match g with Graph succ ®
let rec search (visited: a list) (l:a list) (hits: a list): a list =
match l with
[ ] ® hits
| a::rl ®
if (List.mem a visited)
then (search visited rl hits)
else
if (p a)
then search (a::visited) ((succ a) @ rl) (a::hits)
else search (a::visited) ((succ a) @ rl) hits
in search [ ] [start] [ ]
January 31, 2002