fork(1) download 
  1. (* your code goes here *)
  2.  
  3. let dfs graph visited start_node = 
  4.   let rec explore path visited node = 
  5.     if List.mem node visited then visited else     
  6.       let new_path = node :: path in 
  7.       let edges    = List.assoc node graph in
  8.       let visited  = List.fold_left (explore new_path) visited edges in
  9.       node :: visited
  10.   in explore [] visited start_node
  11.  
  12. let toposort graph = 
  13.   List.fold_left (fun visited (node,_) -> dfs graph visited node) [] graph
  14.  
  15. type recipe = Eggs | Milk | Wheat | Mix | Cook | Serve
  16.  
  17. module Node = struct 
  18.   type t = recipe 
  19. end
  20.  
  21. let graph = [ Wheat, [Eggs;Milk;Mix] ;
  22.               Milk,  [Mix] ;
  23.               Eggs,  [Mix] ;
  24.               Mix,   [Cook] ;
  25.               Cook,  [Serve] ;
  26.               Serve, [] ]
  27.  
  28.  
  29. let sorted = toposort graph
  30.  
  31.  
  32. let str_recipe = function
  33. | Eggs -> "Eggs"
  34. | Milk -> "Milk"
  35. | Wheat -> "Wheat"
  36. | Mix -> "Mix"
  37. | Cook -> "Cook!"
  38. | Serve -> "Serve"
  39.  
  40. let () = List.iter (fun i -> Printf.printf "%s -> " (str_recipe i)) sorted
Success #stdin #stdout 0s 4948KB
comments (?)
stdin 
Standard input is empty
stdout 
Wheat -> Milk -> Eggs -> Mix -> Cook! -> Serve ->
https://ideone.com/y6MBMc
language:
OCaml (ocamlopt 4.05.0)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!