We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or registerto boost this post!

Show some love to the author of this blog by giving their post some rocket fuel π.

Login or register to start working on this issue!

Engineers who find a new job through Functional Works average a 15% increase in salary π

Erlang Digraph

Jakub Hajto 27 November, 2017 | 3 min read

Erlang has tons of goodies that most 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. The 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 tuple with three `#Reference<Something>` thingies. Don't bother with what's inside just for now.

After graph is successfully 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"
"Warszawa"
iex(6)>
nil
[:"\$e" | 0]
[:"\$e" | 1]
[:"\$e" | 2]
[:"\$e" | 3]
``````

Now you can for example find the 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 a 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

Remember 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()}).
``````

Is it quite similar to our tuple? If the record is similar to struct where did the names go? Actually.. In Erlang, records are bare tuples. The names exist only at compile time, after that they are gone. It is quite a troublesome approach, but it clarifies a lot of what we can see right now. `vtab` is the 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 a 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 its 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.

If you're passionate about functional programming and want to work with a functional stack, check out our job board here!

Originally published on hajto.github.io