Adventures In Erlang: undirected graphs.

At RailsConf Europe it quickly became obvious that while there's a bunch of really cool things happening in the Ruby and Rails worlds just now, the current hotness is all about Erlang. I decided to give it a whirl so I bought a few screencasts and the Programming Erlang book and played for a few hours.

I very quickly found out that Erlang is incredibly similar to Prolog and when I commented on this it turned out that Erlang was originally a Prolog descendent intended for high-availability, high-performance distributed applications. That's great for me - I spent the best part of three years working with Prolog as part of my AI course!

To see if I could remember how to reason with Prolog I decided to implement some fairly trivial predicates - the sort of thing that you'd use at the start of a degree course to introduce Prolog, for example.

A brief introduction to graphs

Also know as "here comes the maths bit..."

For those who haven't covered graph theory as part of mathematics, graphs aren't bar charts or pie charts. The clue's in the name: those are charts. A graph is a collection of vertices and edges that join them. Every played join the dots? That's a close enough comparison.

There are two kinds of graphs: directed and undirected. For directed graphs the direction of the edges matters while for undirected graphs it doesn't.

If we have an directed graph with two vertices A and B, and an edge A → B, there is no edge between B and A (above). In an undirected graph there is one (below).

To play with Erlang, I'll make an arbitrary choice and use a simple undirected graph like the last of the two graphs above. I'll ask Erlang to check if there's a connection between two vertices in the graph.

Less Mathematics, More Erlang

First, let's decide how to represent the graph. In English I'd describe the graph like this:

1. There's an edge between vertex A and vertex B
2. There's an edge between vertex B and vertex C
3. There's an edge between vertex C and vertex A
so I should do the same in Erlang to keep it clear.

Graph = [
  { edge, 
    { vertex, a },
    { vertex, b }},
  { edge, 
    { vertex, b },
    { vertex, c }},
  { edge, 
    { vertex, c },
    { vertex, a }}
].

With a graph to reason about, how do I decide if two vertices, N and M, are connected? I look at the first edge in the graph and ask "does this edge connect N to M?"

% If there's an edge from A -> B then A and B are connected.
% 
connected([ { edge, { vertex, A }, { vertex, B } } | _ ], { vertex, A }, { vertex, B }) -> yes;

Since I'm considering an undirected graph edges that connect N to M can also be defined as edges that connect M to N, so I also have to ask "does this edge connect M to N?"

% If there's an edge from B -> A then A and B are connected (since we're 
% considering only undirected graphs).
%
connected([ { edge, { vertex, B }, { vertex, A } } | _ ], { vertex, A }, { vertex, B }) -> yes;

If the edge I'm considering meets neither of the above two conditions than possibly the next edge in the graph will match them so discard the first edge and repeat the above with the next vertex.

% If the edge currently being examined doesn't join the vertices, try 
% looking through the rest of the graph searching for a matching edge.
% 
connected([ _ | Graph], { vertex, A }, { vertex, B }) ->
  connected(Graph, { vertex, A }, { vertex, B });

If we've looked through the entire graph in this manner and there are no edges left to consider, the nodes aren't joined.

% If there are no edges to consider then the nodes aren't joined.
% 
connected([], _, _) -> no.

There are no other cases I can think of so I finish the predicate definition with a period (.) - note that the previous cases had a semi-colon at the end.

Organising Erlang code

Erlang code is organised in modules. I suspect that these act sort of like namespaces, but I haven't dug that deep yet so can't say for sure. In any case, the module name and the name of the file that the Erlang code is stored in should be the same. Since I'm dealing with undirected graphs I've called the module unigraph which makes the filename unigraph.erl. I have to tell Erlang which module this is, and which predicates I want to make available to the outside world so the following code goes at the top of that file.

-module(unigraph).
-export([connected/3]).

Running the code

Change into the directory containing the Erlang file and Launch the Erlang shell by typing erl.

webstc09@MC-S001877 graphs $ erl
Erlang (BEAM) emulator version 5.5.5 [source] [async-threads:0] [hipe] [kernel-poll:false]

Eshell V5.5.5  (abort with ^G)

Once in the shell compile the module, setup the graph given above and ask Erlang if some of the nodes are connected.

1> c(unigraph).
{ok,unigraph}
2> Graph = [
2>   { edge, 
2>     { vertex, a },
2>     { vertex, b }},
2>   { edge, 
2>     { vertex, b },
2>     { vertex, c }},
2>   { edge, 
2>     { vertex, c },
2>     { vertex, a }}
2> ].
[{edge,{vertex,a},{vertex,b}},
 {edge,{vertex,b},{vertex,c}},
 {edge,{vertex,c},{vertex,a}}]
3> unigraph:connected(Graph, { vertex, a }, { vertex, b }).
yes
4> unigraph:connected(Graph, { vertex, a }, { vertex, c }).
yes

That's great, but what happens if we ask about a vertex that doesn't exist? Let's ask if { vertex, a } is connected to an imaginary { vertex, z }.

5> unigraph:connected(Graph, { vertex, a }, { vertex, z }).
no

Get the code

The code to the module I've described is available at http://barkingiguana.com/file_download/2.

Confusing tangent

I'm not really sure how to finish up since this post was mainly to help me get to grips with a Prolog-like language again. I look forward to seeing what else I can make Erlang do, and I'll probably post that here too. Prolog just got a lot prettier and a bunch more fun.

If you found this article useful, give me some love over at Working With Rails... because obviously, Erlang has so much to do with Rails.

written by

Craig

published

2008-09-05