### Basic Graph Traversal in OCaml

This is my solution to Cracking The Coding Interview problem 4.2. The problem is: Given a directed graph, design an algorithm to find out whether there is a route between two nodes.

Keep in mind that I’ve only been writing OCaml for a few weeks. There is
probably a more elegant solution. Once my OCaml is more advanced, I’ll make a
new post. This solution does BFS traversal, returning `None`

early when it can’t
traverse any further and hasn’t reached the destination node.

module Graph = struct type node = int type graph = { nodes : node list; edges : (node*node) list } let mk = { nodes=[] ; edges= [] } let mk_outgoing g = fun n -> let keep ((left,_) as edge) acc = if left = n then [edge] @ acc else acc in let next_to = List.fold_right g.edges ~f:keep ~init:[] in Int.Set.of_list (List.map next_to ~f:snd) let bfs_traverse_until g root ~f:action = let outgoing = mk_outgoing g and visited = Int.Set.empty and to_visit = Queue.create () in Queue.enqueue to_visit root; let rec loop visited = Option.value_map (Queue.dequeue to_visit) ~default:None ~f:(fun id -> if action id then Some id else begin if not (Int.Set.mem visited id) then let children = Int.Set.diff (outgoing id) visited in Int.Set.iter children ~f:(fun n -> Queue.enqueue to_visit n); let visited' = Int.Set.add visited id in loop visited' else loop visited end ) in loop visited let route g n1 n2 = Option.is_some (bfs_traverse_until g n1 ~f:(fun node -> node = n2)) end let my_graph : Graph.graph = { Graph.nodes = [1;2;3;4;5;6;7;8;9;10] ; Graph.edges = [(1,2); (1,3); (1,5); (1,8); (1,9) ;(2,3); (2,10); (2,7) ;(3,8) ;(4,6); (4,10) ;(5,4); (5,6) ;(6,3) ;(7,8); (7,10); (7,1) ;(8,9); (8,6) ;(9,6); (9,3) ;(10,9); (10,8)] }

Here’s how I tested it:

utop[2]> Graph.route;; - : Graph.graph -> int -> int -> bool = <fun> utop[4]> Graph.route my_graph 1 10;; - : bool = true utop[5]> Graph.route my_graph 10 1;; - : bool = false utop[6]> Graph.route my_graph 3 9;; - : bool = true utop[7]> Graph.route my_graph 4 7;; - : bool = false