At RailsConf Europe 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. I decided to give it a whirl, so I picked up a few screencasts and the Programming Erlang book and played for a few hours.
I very quickly noticed that Erlang is remarkably similar to 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 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:
- There’s an edge between vertex A and vertex B
- There’s an edge between vertex B and vertex C
- There’s an edge between vertex C and vertex A
The Erlang representation should read just as clearly:
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?”
% 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:
% 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:
% 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:
% 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:
-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:
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}:
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.
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.