Erlang provides a module for working with directed graphs, called digraph. Let's look at a few things it can do. This episode is inspired by a blog post that has some excellent introductory information on this module. You can find the post in the resources section.

Project

We'll kick this off with a new project. We're going with mix new digraph_maps. cd into the directory.

Let's start off by writing a test. We'll build our own module that is implemented by way of digraph, so we'll write tests for our module.

Go ahead and open up test/digraph_maps_test.exs and let's build out our acceptance test:

defmodule DigraphMapsTest do
  use ExUnit.Case
end

Alright, so this project is going to consist of a module that can be used to represent a road map of a city. In these maps, intersections will be the vertices of our graphs, and road portions will be the edges.

We'll go ahead and build out an acceptance test to make sure we can build a trivial map. I've attached the image that I'm going to be using to the episode's files, but let's have a look at it as we build this out. (show map)

On this map, I've highlighted a single block, and we're only going to model the city-level streets - these are the white roads in this map. There are four of them, and four intersections. Let's get to it.

  alias DigraphMaps.Map
  alias DigraphMaps.Intersection
  alias DigraphMaps.Road.OneWay
  alias DigraphMaps.Road.TwoWay

  test "Four intersections can be connected" do
    # Create our map
    map   = Map.new

    # Add our block's intersections
    ra_9  = Intersection.new(map, "Richard Arrington and 9th Avenue")
    ra_aw = Intersection.new(map, "Richard Arrington and Abraham Woods")
    ts_aw = Intersection.new(map, "22nd and Abraham Woods")
    ts_9  = Intersection.new(map, "22nd and 9th Avenue")

    # Add our block's streets
    ra    = OneWay.new(ra_aw, ra_9)
    ninth = TwoWay.new(ra_9, ts_9)
    ts    = OneWay.new(ts_9, ts_aw)
    aw    = TwoWay.new(ts_aw, ra_aw)

    # Add some assertions on our response types
    assert ra_9.map == map
    assert %Intersection{} = ra_9

    assert ra.map == map
    assert %OneWay{} = ra
    assert %TwoWay{} = ninth

    # Finally, the shortest way to get from "Richard Arrington and 9th Avenue"
    # to "Richard Arrington and Abraham Woods" should be by making the block
    assert Map.shortest_path(ra_9, ra_aw) == ["Richard Arrington and 9th Avenue", "22nd and 9th Avenue", "22nd and Abraham Woods", "Richard Arrington and Abraham Woods"]
    
    # However, the shortest way to get from "Richard Arrington and Abraham
    # Woods" to "Richard Arrington and 9th Avenue" should be by going directly
    assert Map.shortest_path(ra_aw, ra_9) == ["Richard Arrington and Abraham Woods", "Richard Arrington and 9th Avenue"]
  end

Alright, so that was a lot to take in, but I hope it's all made sense so far. If you're confused, just reference the map image until it makes sense...

OK, so this test won't pass yet of course :) This was just to describe what our end state would look like. Let's look at building out these bits, using both maps for our data structures and the digraph module.

From this, we can build out a fairly basic unit test for our Map module, so let's do that next. Open up test/map_test.exs:

defmodule DigraphMaps.MapsTest do
  use ExUnit.Case
  alias DigraphMaps.Map

  test "Creating a map" do
    # Create our map
    map   = Map.new

    assert %Map{} = map
  end
end

This is easy enough - basically, for now we're just asserting that Map.new returns a Map struct. Let's make that happen, at the top of the test for now:

defmodule DigraphMaps.Map do
  defstruct []

  def new do
    %DigraphMaps.Map{}
  end
end

Run the test, and it will pass. Of course, this does us fairly little good - what use is this map? We made it so that we could place the digraph structure into it.

Erlang's digraph module returns a 5-tuple whose first element is the atom :digraph. We'll create one of those and place it in the map when you create a new one.

  test "Creating a map" do
    # Create our map
    map   = Map.new

    assert %Map{} = map
    assert {:digraph, _, _, _, _} = map.digraph
  end

Run the tests, and of course they'll fail. Let's make them pass:

defmodule DigraphMaps.Map do
  defstruct [:digraph]

  def new do
    %DigraphMaps.Map{digraph: :digraph.new()}
  end
end

Run them again, and they pass. That's really all our map consists of for now, so let's extract it to the lib directory. (do it)

Next, let's implement intersection. Just like for map, let's open up test/intersection_test.exs:

defmodule DigraphMaps.IntersectionTest do
  use ExUnit.Case
  alias DigraphMaps.Map
  alias DigraphMaps.Intersection

  test "Creating an intersection" do
    # Create our map
    map   = Map.new

    # Create an intersection
    intersection = Intersection.new(map, "Some intersection name")

    assert %Intersection{} = intersection
    assert intersection.name == "Some intersection name"
    assert intersection.map == map
  end
end

Alright, this is fairly straightforward, given what we've already done. Let's just implement it fairly quickly at the top of the test:

defmodule DigraphMaps.Intersection do
  defstruct [:map, :name]

  def new(map, name) do
    %DigraphMaps.Intersection{map: map, name: name}
  end
end

So this will pass the test, but it doesn't do anything with the underlying digraph datastructure we're interested in. However, that's easy. Let's add one more assertion:

    assert ["Some intersection name"] = :digraph.vertices(map.digraph)

Now let's make it pass:

  def new(map, name) do
    :digraph.add_vertex(map.digraph, name)
    %DigraphMaps.Intersection{map: map, name: name}
  end

Run the tests, and they'll pass. Now extract this into the lib directory (do it).

Alright, we just need to implement the roads now. We'll wrap both kinds of roads up into a single test file. Open up test/roads_test.exs:

defmodule DigraphMaps.RoadsTest do
  use ExUnit.Case
  alias DigraphMaps.Map
  alias DigraphMaps.Intersection
  alias DigraphMaps.Road.OneWay
  alias DigraphMaps.Road.TwoWay

  test "Creating a one way road" do
    # Create our map
    map   = Map.new

    # Create two intersections
    first_int = Intersection.new(map, "First")
    second_int = Intersection.new(map, "Second")

    # Create a one way road between them
    road = OneWay.new(first_int, second_int)

    assert %OneWay{} = road
    assert road.map == map
  end
end

Once again, we've just written the parts that aren't concerned with the digraph module yet - we're focused on our abstraction first. Let's make this part pass at the top of the test:

defmodule DigraphMaps.Road do
  defmodule OneWay do
    defstruct [:map]

    def new(from, to) do
      %OneWay{map: from.map}
    end
  end
end

Alright, run the test and it should pass. Next, we'll want to actually build the parts that interact with the digraph. Our roads are represented by edges in the directional graph, so we'll build a single edge pointing from the from intersection to the to intersection. First, we'll write a test for this to verify that there's a single edge in the road's edges list, which we'll also implement:

    assert Enum.count(road.edges) == 1

Now let's create the edge on initialization:

defmodule DigraphMaps.Road do
  defmodule OneWay do
    defstruct [:map, :edges]

    def new(from, to) do
      edge = :digraph.add_edge(from.map.digraph, from.name, to.name)
      %OneWay{map: from.map, edges: [edge]}
    end
  end
end

Run the tests, and they should pass. Next we'll want to implement two way roads. We'll just copy the one way test for now:

  test "Creating a two way road" do
    # Create our map
    map   = Map.new

    # Create two intersections
    first_int = Intersection.new(map, "First")
    second_int = Intersection.new(map, "Second")

    # Create a two way road between them
    road = TwoWay.new(first_int, second_int)

    assert %TwoWay{} = road
    assert road.map == map
    assert Enum.count(road.edges) == 2
  end

Alright, let's implement TwoWay up top:

  defmodule TwoWay do
    defstruct [:map, :edges]

    def new(from, to) do
      edge1 = :digraph.add_edge(from.map.digraph, from.name, to.name)
      edge2 = :digraph.add_edge(from.map.digraph, to.name, from.name)
      %TwoWay{map: from.map, edges: [edge1, edge2]}
    end
  end

Run the tests, and they should pass. Extract the modules to the lib dir. We'll put them both in lib/digraph_maps/road.ex. (do it)

Now we just need to open up our main test and implement the missing bits. Open up test/digraph_maps_test.exs and let's run it. It fails because we haven't yet implemented the shortest_path function on Map. Let's look at implementing that, using digraphs get_short_path function. Open up lib/digraph_maps/map.ex:

  def shortest_path(from, to) do
    :digraph.get_short_path(from.map.digraph, from.name, to.name)
  end

So here you can see that digraph gives us an excellent function for handling this very situation. That shouldn't be that surprising I don't guess, since finding paths is one of the core things you do in directional graphs. Still, it makes me pretty happy how easy this module is to use. Go ahead and run the tests, and they should all pass now.

Summary

So that's it. We built a quick abstraction for building maps and roads between intersections, using the digraph module in Erlang's standard library to provide us with a nice feature for path finding within the graph. There's a lot more to this module, but I think this is a fun introduction to it.

Resources