Previous Contents Next

Module Graphs

type a dgraph =
     Graph of (a ® a list)

exception Not_Found

let dfs (ga dgraph) (pa ® bool) (starta) = 
   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 (ga dgraph) (pa ® bool) (starta) : a list = 
       match g with Graph succ ®
         let rec search (visiteda list) (l:a list) (hitsa 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) @ rlhits
         in search [ ] [start] [ ]
January 31, 2002
Previous Contents Next