(* 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"