/ elixir

Implementing BFS in Elixir

After 12 days of adventofcode I think I'm starting to understand Elixir's mindset, or at least I'm starting to write code I wasn't able to read 2 weeks ago. Let's try to use my BFS implementation below to explain some Elixir concepts.

Graph Representation

Before we can dive into the actual algorithm code for breadth first search we need to figure out a way to store the graph.

The original problem input arrived in text format and looked like this:

0 <-> 2
1 <-> 1
2 <-> 0, 3, 4
3 <-> 2, 4
4 <-> 2, 3, 6
5 <-> 6
6 <-> 4, 5

In elixir I'd like to represent the graph using a map, where each key is a vertex and each value is a set its neighbors. The actual representation would look like this:

graph = %{
    "0" => MapSet.new(["2"]),
    "1" => MapSet.new(["1"]),
    "2" => MapSet.new(["0", "3", "4"]),
    "3" => MapSet.new(["2", "4"]),
    "4" => MapSet.new(["2", "3", "6"]),
    "5" => MapSet.new(["6"]),
    "6" => MapSet.new(["4", "5"])

Surprisingly the following code is all we need:

  def parse(stream) do
    |> Enum.map(&String.trim/1)
    |> Enum.map(&String.split(&1, ~r/\W/, trim: true))
    |> Enum.reduce(%{}, fn([v | n], graph) -> 
      Map.put(graph, v, MapSet.new(n))

It's easier to read than to write: You take an input stream (list of lines), pass each line to trim to remove its line break, then send each line to split so you now have a list where the first element is the vertex and next are its neighbors.

Just up to here the above input would turn into this list of lists:

    ["0", "2"],
    ["1", "1"],
    ["2", "0", "3", "4"],
    ["3", "2", "4"],
    ["4", "2", "3", "6"],
    ["5", "6"],
    ["6", "4", "5"]

And this list of lists will make a great input for the reduce in the next line. As a reminder:

    |> Enum.reduce(%{}, fn([v | n], graph) -> 
      Map.put(graph, v, MapSet.new(n))

Takes a list of lists, separates each list to its "first" and "rest" parts and then adds the new (key, value) pair in the graph map, leading us to the graph representation described above.

Now Let's Search For Neighbors

The suggested graph representation makes it trivial to get a vertex's neighbors (using Map.get). Thus the code for BFS search:

  def neighbors(graph, v) do
    Map.get(graph, v, MapSet.new)

  def bfs(_, [], seen) do

  def bfs(graph, frontier, seen) do
    unseen_neighbors = for v <- frontier do
      neighbors(graph, v)
    |> Enum.reduce(MapSet.new, &MapSet.union/2)
    |> MapSet.difference(seen)
    |> MapSet.to_list

      MapSet.union(seen, MapSet.new(unseen_neighbors))

This is a recursive algorithm. Its halting condition is having an empty list of vertexes to search from (as BFS from nothing is nothing).

The more interesting bit is the second function which handles the general case. We basically take the list of "seen" vertexes and expand it with all our "source" vertexes. Then we call BFS again with the new expanded "seen" and change the source to include all unseen neighbors. Do this enough times and you'll cover the whole reachable vertexes in your graph.

Elixir's recursion provided a much nicer implementation compared with a queue. It's short, concise and works.