Adventures in Erlang: Undirected Graphs
At [RailsConf Europe](http://www.railsconfeurope.com/) it quickly became obvious that while there's a bunch of really cool things happening in the Ruby and Rails worlds, the current hotness is all about [Erlang](http://www.erlang.org/). I decided to give it a whirl, so I picked up a few screencasts and the [Programming Erlang](http://www.pragprog.com/titles/jaerlang/programming-erlang) book and played for a few hours.
I very quickly noticed that Erlang is remarkably similar to [Prolog](http://en.wikipedia.org/wiki/Prolog) -- and when I mentioned this, it turned out Erlang was originally a Prolog descendant built for high-availability, high-performance distributed applications. Great news for me: I spent the best part of three years working with Prolog during my AI course.
To shake the rust off, I decided to implement some fairly trivial predicates -- the kind of thing you'd use at the start of a degree course to introduce Prolog.
#### A brief introduction to graphs
*Also known as "here comes the maths bit..."*
For those who haven't covered [graph theory](http://en.wikipedia.org/wiki/Graph_theory) in 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. Ever played join-the-dots? That's a close enough comparison.
There are two kinds of graphs: directed and undirected. In a directed graph, the direction of edges matters. In an undirected graph, it doesn't.
In a directed graph with vertices A and B and an edge A → B, there's no implied edge from B to A (above). In an undirected graph, there is (below).
For this exercise I'll use a simple undirected graph like the one above and ask Erlang whether two vertices are connected.
#### Less maths, more Erlang
First, let's represent the graph. In English I'd describe it 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
The Erlang representation should read just as clearly:
```erlang
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 and ask: "does this edge connect N to M?"
```erlang
% 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 this is an undirected graph, an edge connecting N to M also connects M to N. So I need to check the reverse too:
```erlang
% 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 current edge matches neither condition, discard it and try the next one:
```erlang
% 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 exhausted the entire graph and found no matching edge, the vertices aren't connected:
```erlang
% If there are no edges to consider then the nodes aren't joined.
%
connected([], _, _) -> no.
```
Note the punctuation: each clause ends with a semicolon (;) except the final one, which gets a full stop (.).
#### Organising Erlang code
Erlang code lives in modules. The module name and the filename should match -- since I'm dealing with undirected graphs, the module is called `unigraph` and lives in `unigraph.erl`. At the top of the file, declare the module and its exports:
```erlang
-module(unigraph).
-export([connected/3]).
```
#### Running the code
Change into the directory containing the Erlang file and launch the Erlang shell:
```
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, set up the graph, and start querying:
```erlang
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
```
What about a vertex that doesn't exist? Let's ask if `{vertex, a}` is connected to an imaginary `{vertex, z}`:
```erlang
5> unigraph:connected(Graph, { vertex, a }, { vertex, z }).
no
```
Exactly what you'd expect -- no edge, no connection.
#### Get the code
The complete module is available at [http://barkingiguana.com/file_download/2](http://barkingiguana.com/file_download/2).
#### Wrapping up
This was mainly an exercise in getting reacquainted with a Prolog-like language. Erlang's pattern matching feels wonderfully natural once you're used to it, and I'm looking forward to seeing what else I can build with it. Prolog just got a lot prettier and a bunch more fun.
Questions or thoughts? Get in touch.