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