(* A graph is a list of nodes that are connected together. We can
   represent a graph using the following data structures. *)

type name  = string

type node = {
  label:name;              (* Name of the node *)
  value:int;               (* Value that it stores *)
  mutable edges:node list  (* List of nodes that neighbor it. *)
}

type graph = node list 

(* A sample graph with 6 nodes:

   a -> d -> e 
   ^    |
   |    |
   V    V 
   b -> c  -> f

   For example, we can represent the graph above with the following code.
   Since graphs may have cycles in them, we must make the list of edges
   in a node mutable.
*)

let test_graph : graph = 
  let a = { label="a"; value=1; edges = [] } in
  let b = { label="b"; value=2; edges = [] } in
  let c = { label="c"; value=3; edges = [] } in
  let d = { label="d"; value=4; edges = [] } in
  let e = { label="e"; value=5; edges = [] } in
  let f = { label="f"; value=6; edges = [] } in
    a.edges <- [b;d];
    b.edges <- [a;c];
    c.edges <- [f];
    d.edges <- [c;e];
    [a;b;c;d;e;f]

(* ----------------- Depth first search of the graph --------------------- *)
type path = name list (* A path is a list of labels describing the route. *)

(* depth-first search. Find a path from the starting node
   to a node labelled with stop. *)
let rec dfs (start:node) (stop:name) : int option = 
  dfs_aux start stop []

and dfs_aux 
  (current:node) (* the node that we're currently starting the path from *)
  (stop:name)           (* the label of the node that we are looking for. *)
  (visited:name list)   (* a list of nodes that we have seen on this path, 
                           so that we may detect cycles *)
  : int option = 
  let l = current.label in
  if l = stop then Some current.value
  else if List.mem l visited then None
  else (dfs_edges current.edges stop (l::visited)) 

and dfs_edges (edges:node list)(stop:name)(visited:name list): int option = 
  match edges with 
      [] -> None
    | (hd::tl) -> 
        match dfs_aux hd stop visited with 
            Some v -> Some v 
          | None -> dfs_edges tl stop visited 


(* --------- code to print out the answer once we've found it ----------- *)

let doit (stop:name) : unit = 
  let po = dfs (List.hd test_graph) stop in 
  print_string "VALUE IS: ";
  match po with 
      Some v -> (print_string (string_of_int v); print_string "\n")
    | None -> print_string "NO VALUE\n"
        
let main = 
  doit "c";
  doit "e"