Is there a way to convert a matrix based graph representation into something like an adjacency list in OCaml?

Question

Generally, in programming interviews, you're given a problem where you're asked to traverse a 2D matrix representation of a graph using something like DFS or BFS like this problem on LeetCode. Unfortunately, the typical algorithms of looping over the elements and running a dfs when you encounter a patch of nodes are hard to implement functionally. I'm wondering if there's an easy way to convert the 2D matrix to an adjacency list representation in OCaml so that a functional algorithm can get a more efficient solution.

Answer 1

Unfortunately, the typical algorithms of looping over the elements and running a dfs when you encounter a patch of nodes are hard to implement functionally.

Contrary, they are very easy and natural to implement. Let's show it. The input from LeetCode is stated as,

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

which maps directly to OCaml as

let grid = [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"0"]
]

The only syntactic difference is that you have to use ; instead of , as a separator.

Iterations in OCaml, and functional languages in general, are expressed using iterators. An iterator is a higher-order function that takes a container and another function and applies this function to each element of that container. Thus there is no need for special language constructs for iteration, like for or while¹.

Iterators could be roughly split into two groups: folders and mappers. A folder applies a function to each element and accumulates the result. A mapper creates a new data structure where each element is the mapping (transformation) of the original element. Mappers that do not map each element, i.e., that produce output data structures that could be smaller than inputs, are called filters. Finally, every mapper could be (and usually is) implemented using a folder, so folders is the most general form of iteration.

Now, when we're equipped with this knowledge, we can take a look into the List to see what iterators it provides. Since we need to find the number of isolated islands, the input representation is not optimal and we will need to transform it into something more suitable. From the graph theory perspective, an island is a connected component and we need to partition our land into a set of islands. Obviously, our input data structure is not very well suited as it doesn't allow us to efficiently query if an element is connected to other elements. All queries in a single-linked list are linear since they have to go from the first element to the last one. So we need to find a better data structure to represent our information about our world geography.

Since we're interested only in is_land an efficient representation would be a set of positions, where each position is represented as x and y coordinates,

type pos = {x : int; y : int}

Let's define a module for the position type and add some useful functions in it,

module Pos = struct
  type t = pos
  let compare = compare   (* use structural compare *)
  let zero = {x=0; y=0}
  let north p = {p with y = p.y - 1}
  let south p = {p with y = p.y + 1}
  let east p = {p with x = p.x + 1}
  let west p = {p with x = p.x - 1}
end

And finally, we're ready to define the world as a set of positions,

module World = Set.Make(Pos)

Now we can iterate over our matrix and create a world,

let is_land = function "1" -> true | _ -> false

let make_world input : World.t =
  snd @@
  List.fold_left (fun (pos,map) ->
      List.fold_left (fun ({x;y},map) piece ->
          if is_land piece
          then ({x=x+1; y}, World.add {x;y} map)
          else ({x=x+1; y}, map))
        ({x=1; y = pos.y + 1},map))
    ({Pos.zero with x = 1},World.empty)
    input

See how we used List iterators to perform an iteration over a matrix.

Next, we will implement the union-find algorithm to partition a world into a set of islands. Let's develop it topdown. The union-find algorithm partitions a set of elements into a set of non-intersecting sets (colloquially called quotient set). Our initial set is World.t that is the set of all positions that are land. And for each position, we need to find a list of islands to which this position is_connected. We now need to precisely define what is_connected means. In terms of the geometry of our world, a piece of land at the position pos is connected to an island island if it belongs to island or if any of its neighbors belong to the island, where neighbors of pos are,

let neighbors pos = [
  Pos.north pos;
  Pos.south pos;
  Pos.east pos;
  Pos.west pos;
]

so is_connected is defined using the List.exists iterator,

let is_connected pos island =
  List.exists (fun x -> World.mem x island)
    (pos :: neighbors pos)

Now, we can write a function that partitions the quotient set of islands into the set of islands to which a piece of land belongs and the set of islands that are not connected to that piece. It is very easy to implement using the List.partition iterator,

let find_islands pos =
  List.partition (is_connected pos)

If an element belongs to several islands, then it means that it is a connecting element, a link, that connects several islands that were thought to be disconnected before we found this element. We need a function that will join several pieces of an island into a single island. Again, we can use List.fold_left for that,

let union = List.fold_left World.union World.empty

Now, we have all the necessary building elements to find our main algorithm,

let islands world =
  World.fold (fun pos islands ->
      let found,islands = find_islands pos islands in
      World.add pos (union found) :: islands)
    world []

Let's reiterate its implementation. For each piece of our world, we partition our initial set of islands (which starts with an empty set) into islands to which this piece belongs and to which it doesn't. Then we union the found islands and add the current piece to the newly formed island and add this island to the set of islands.

Notice, how simple is the implementation of the union-find in a functional programming language!

The number of islands is obviously the cardinality of our partition, e.g.,

let number_of_islands world = List.length (islands world)

Finally, the solve function, which takes the input in the specified form and returns the number of islands is defined as,

let solve input = number_of_islands (make_world input)

Let's play with it a little bit,

# solve [
  ["1";"1";"1";"0";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 3
# solve [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 2
# solve [
  ["1";"1";"1";"1";"0"];
  ["1";"1";"0";"1";"1"];
  ["1";"1";"0";"0";"1"];
  ["0";"0";"0";"0";"1"]
];;
          - : int = 1
# 

Looks good! But what if it wont work from the beginning? We need to debug it. In functional programming debugging is easy, as you debug each small function independently. But for that you need to be able to print your data and our World.t is an abstract data type which is printed as <abstr>. To be able to print it, we need to define some printers, e.g.,

let pp_pos ppf {x; y} = Format.fprintf ppf "(%d,%d)" x y
let pp_comma ppf () = Format.fprintf ppf ", "
let pp_positions ppf world =
  Format.pp_print_list ~pp_sep:pp_comma pp_pos ppf
    (World.elements world)
let pp_world ppf world =
  Format.fprintf ppf "{%a}" pp_positions world

Now we can install it (and I assume that you're running this program using ocaml or utop interpreter), and now we can see how our algorithm partitions our worlds into islands,

# #install_printer pp_world;;

# islands @@ make_world [
  ["1";"1";"1";"0";"0"];
  ["1";"1";"0";"1";"0"];
  ["1";"1";"0";"0";"0"];
  ["0";"0";"0";"0";"1"]
];;
          - : World.t list =
[{(5,4)}; {(4,2)}; {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1)}]

---

¹⁾ We still have them in OCaml but use very rarely.

Answer 2

I guess you'd like something like this:

let to_adjacency_list m =
  (* Create an array of the size of the matrix with empty lists as values *)
  let ml = Array.init (Array.length m) (fun _ -> []) in
  (* For each cell (i, j) that contains true, append j to the list at index i *)
  Array.iteri
    (fun i a -> Array.iteri (fun j v -> if v then ml.(i) <- j :: ml.(i)) a)
    m;
  (* Reverse all the created lists for readability and convert the array to a list *)
  Array.to_list (Array.map List.rev ml)

If I apply it to a matrix:

# let m =
  [|
    [| true; true; true; true; false |];
    [| true; true; false; true; false |];
    [| true; true; false; false; false |];
    [| false; false; false; false; false |];
  |] in to_adjacency_list m;;

- : int list list = [[0; 1; 2; 3]; [0; 1; 3]; [0; 1]; []]