Graph Traversal in OCaml 2016-01-28

## Table of contents

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
``````