• This is more “note to self” type of post rather than tutorial thing.
• It’s hard to write blog posts when you are trying to take over the world :)

Why ?

Recently in “professor Toons” :) computer club was a task that was ideal to solve as graph. It was one of this “find path” tasks. Yesterday just before going to bed I thought “Why not solve it in Erlang”. And this are my thoughts about erlang digraph: library.

Task

First of all http://erldocs.com/ is the way to go when working with documentation.

Second “the Task”. It had two parts, first was to load xml file with songs and second was to build graph and find playlist between two songs having in mind that for each song following has to start with the same letter that first ended.

example.

if you have song list: ABC CBA BAC ACB BBA

And you want to find playlist from ABC to BAC you will get ABC –> CBA –> ACB –> BAC. Easy

Digraph

Digraph API is quite nice but there are few things you have to have in mind.

• Digraph is imperative graph!
• You need to pass vertices to get_path!
• Graph with loads of edges can be quite big :D

To create empty graph you call :new/0

1

Graph = digraph:new().

To add node to graph you call :add_vertex/2

1
2

Data = {Value1, Value2, Value3},
digraph:add_vertex(Graph, Data).

To add edge to graph you call :add_edge/3

1

digraph:add_edge(Graph, VertexStart, VertexEnd).

To get all vertices from graph (random order) :vertices/1

1

Vertices = digraph:vertices(Graph).

And finally to get path you just call :get_path/3

1

Path = digraph:get_path(Graph, VertexStart, VertexEnd).

This path is a list of vertices in order. This API is just to remind me essential things about using the digraph from erlang stdlib. This graph is quite simple.

And for me for about 5000 vertices and a lot of edges it consumed 1.5 GB of ram. But when it was created it was super fast to use.

It was fun to play with.

Quick summary

I will make quick summary in form of short code sample!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

G = digraph:new(),
V1 = digraph:add_vertex(G, "Andrychow"),
V2 = digraph:add_vertex(G, "Krakow"),
V3 = digraph:add_vertex(G, "London"),
V4 = digraph:add_vertex(G, "Warsaw"),
V5 = digraph:add_vertex(G, "Paris"),

digraph:add_edge(G, V1, V2),
digraph:add_edge(G, V2, V4),
digraph:add_edge(G, V2, V5),
digraph:add_edge(G, V2, V3),
digraph:add_edge(G, V3, V4),
digraph:add_edge(G, V3, V2),
digraph:add_edge(G, V2, V1),

PathHome = digraph:get_path(G, V3, V1).

This gives you back ["London","Krakow","Andrychow"] so Win! we are at home!

Summary

It was fun to play a bit with digraph before going to bed. There is a tone of things i did not use and also look into digraph_utils for even more things :)