Erlang Digraph

Erlang has tons of goodies that most of people don’t know about. If you are studying IT just like me you should definitely learn digraph, because you will have to implement a graph algorithm at some point and this can be considered real lifehack in such situations.

As you might have already guessed by the name it is a data structure that is used to store directed graphs in Erlang or Elixir. It is really easy to use. First thing you have to do is to actually initialize a graph.

iex(1)> graph = :digraph.new()
{:digraph, #Reference<0.3992624098.55705602.46770>,
 #Reference<0.3992624098.55705602.46771>,
 #Reference<0.3992624098.55705602.46772>, true}

If you run it in REPL you should get five element tupple with three #Reference<Something> thingies. Don’t bother with what’s inside just for now.

After graph is successfuly initialized you can add vertices and edges.

iex(2)> london = :digraph.add_vertex(graph, "London")
"London"
iex(3)> ny = :digraph.add_vertex(graph, "New York")
"New York"
iex(4)> sf = :digraph.add_vertex(graph, "San Francisco")
"San Francisco"
iex(5)> warsaw = :digraph.add_vertex(graph, "Warszawa")
"Warszawa"
iex(6)>
nil
iex(7)> :digraph.add_edge(graph, london, ny)
[:"$e" | 0]
iex(8)> :digraph.add_edge(graph, ny, sf)
[:"$e" | 1]
iex(9)> :digraph.add_edge(graph, warsaw, london)
[:"$e" | 2]
iex(10)> :digraph.add_edge(graph, london, sf)
[:"$e" | 3]

Now you can for example find shortest road between two vertices.

iex(13)> :digraph.get_path(graph,warsaw, sf)
["Warszawa", "London", "San Francisco"]

Magic applied

Let’s write simple implementation of DFS. Depth-first search is a common algorithm of checking whether you can go from one vertex to rest of them. In my implementation it will just return list of visited vertices.

defmodule GraphHelper do

  def dfs(graph, vertex, acc \\ []) do
    case vertex in acc do
      :false ->
        acc = [vertex | acc]
        Enum.reduce(:digraph.out_neighbours(graph, vertex), acc, fn elem, acc ->
          dfs(graph, elem, acc)
        end)
      :true -> acc
    end
  end

end

Runnable example available here.

Nitty gritty details

Rembember those three values I told you not to care about? It’s time to take a closer look at them.

iex(14)> graph
{:digraph, #Reference<0.3992624098.55705602.46770>,
 #Reference<0.3992624098.55705602.46771>,
 #Reference<0.3992624098.55705602.46772>, true}
iex(15)>

First thing we should do to find enlightment is to look up how it is actually implemented in Erlang. In the digraph module source we can find following lines:

-record(digraph, {vtab = notable :: ets:tab(),
		  etab = notable :: ets:tab(),
		  ntab = notable :: ets:tab(),
	      cyclic = true  :: boolean()}).

It is quite similar to our tuple? If record is similar to struct where did the names go? Actually.. In Erlang records are bare tuples. The names exist only in compile time, after that they are gone. It is quite troublesome approach, but it clarifies a lot of what we can see right now. vtab is first element, etab is second and so forth and so on.

You might also have realized that all of the operations we performed previously were impure. That’s because digraph is internally represented as set of three ets tables and those weird #Reference are actually results of creating new unnamed Erlang Term Storage table.

What’s even more important we can actually see how it is internally represented! We can just call :ets.tab2list/1 and see how digraph manages it data.

iex(15)> {_, vertices, edges, neighbours,cyclic} = graph
{:digraph, #Reference<0.3992624098.55705602.46770>,
 #Reference<0.3992624098.55705602.46771>,
 #Reference<0.3992624098.55705602.46772>, true}

iex(16)> :ets.tab2list(vertices)

[{"London", []}, {"Warszawa", []}, {"New York", []}, {"San Francisco", []}]
iex(17)> :ets.tab2list(edges)
[{[:"$e" | 0], "London", "New York", []},
 {[:"$e" | 3], "London", "San Francisco", []},
 {[:"$e" | 2], "Warszawa", "London", []},
 {[:"$e" | 1], "New York", "San Francisco", []}]

iex(18)> :ets.tab2list(neighbours)
[&#123&#123:out, "Warszawa"}, [:"$e" | 4]}, {:"$eid", 5}, {:"$vid", 0},
 &#123&#123:in, "Warszawa"}, [:"$e" | 2]}, &#123&#123:out, "London"}, [:"$e" | 0]},
 &#123&#123:out, "London"}, [:"$e" | 2]}, &#123&#123:out, "London"}, [:"$e" | 3]},
 &#123&#123:out, "New York"}, [:"$e" | 1]}, &#123&#123:in, "London"}, [:"$e" | 4]},
 &#123&#123:in, "San Francisco"}, [:"$e" | 1]}, &#123&#123:in, "San Francisco"}, [:"$e" | 3]},
 &#123&#123:in, "New York"}, [:"$e" | 0]}]

We can see a lot of interesting information here. As we can see edges are actually numbered. Even more interesting is neighbours table which kind of resembles math notation of Neighbour relation.

Written on July 1, 2017