Software Development

Modelling graphs with processes in Erlang

One of the advantages of Erlang's concurrency model is that creating and running new processes is much cheaper. This opens up opportunities to write algorithms in new ways. In this article, I'll show you how you can implement a graph searching algorithm by modeling the domain using process interaction.

One of the advantages of Erlang's concurrency model is that creating and running new processes is much cheaper. This opens up opportunities to write algorithms in new ways. In this article, I'll show you how you can implement a graph searching algorithm by modeling the domain using process interaction.

I'll assume you're more or less comfortable with Erlang, if you're not you might want to go back and read through Builder AU's previous guides on the subject.

First we need to write a function for the nodes in the graph. When we spawn a process for each node it will need to run a function that sends and receives messages. Each node needs two things, its own name, and the links it has to other nodes. To store the links, we'll use a dictionary which maps name to the node's Pid.

In this program, we'll use three types of messages.

  • link (ToName, ToPid): tells a node that it is connected to another node, and gives that node's name and pid.
  • search (Path): the path of one traversal through the graph. This message will be passed on by the node to all other nodes it is connected to. The path is sent with the message so we can eliminate cycles.
  • endPoint: send to change which node is the goal for graph searches.

The searchNode function and its cycle-checking helper looks like this:

-module(graph).
-export([start/0, searchNode/2])

notIn(_, []) -> true;
notIn(N, [H|T]) ->
    (N /= H) and notIn(N,T).

searchNode(Name, LinkDict) ->
    receive
        {link, ToName, ToPid} -> 
            searchNode(Name, dict:store(ToName, ToPid, LinkDict));
        {search, Path} -> 
            Free = notIn(Name, Path),
            if
                Free ->
                    lists:foreach(
                        fun(X)-> 
                            {_, Pid} = X,
                            Pid ! {search, Path++[Name]}
                        end, 
                    dict:to_list(LinkDict));
                true -> true
            end,
            searchNode(Name, LinkDict);
        {endPoint} ->
            last(Name, LinkDict)
    end.

We need to have a separate function for the node that is the target of the search:

last(Name, LinkDict) ->
        receive
            {link, ToName, ToPid} -> 
                last(Name, dict:store(ToName, ToPid, LinkDict));
            {search, Path} ->
                io:format("Found path: ~w~n", [Path++[Name]]),
                searchNode(Name, LinkDict);
            {endPoint} ->
                searchNode(Name, LinkDict)
        end.

We could just as easily have these cases in a branch in the searchNode function, but this way is a bit clearer.

Building the graph

We need a method for building the graph. For this example, we'll read the graph configuration from a text file. A sample file (names.gph) has the following format:

jeff [tom, dick, harry]
tom [dick, bob]
dick [harry]
harry [ted]
bob [ted]
ted [jeff]

The name of the node is followed by a list of the nodes it has links to. We'll use Erlang's built in token scanner (found in the erl_scan module), so the brackets are optional, but white space is significant.

Building the graph has two stages, first we need to create all the nodes, then we need to connect them by sending nodes the relevant link messages.

To build the graph, we load lines from the configuration file one by one, spawning processes as we go and building a dictionary that maps names to process identifiers:

getAtoms([]) -> [];
getAtoms([H|T]) -> case H of
                        {atom,_, A} -> [A | getAtoms(T)];
                        _ -> getAtoms(T)
                    end.

buildGraph(File, NodeDict) ->
    case io:get_line(File,'') of
        eof -> linkGraph(NodeDict), NodeDict;
        LS -> 
            [Name | L] = getAtoms(element(2,erl_scan:string(LS))),
            Pid = spawn(?MODULE, searchNode, [Name, dict:new()]),
            io:format("~w ", [Name]),
            buildGraph(File, dict:store(Name, {Pid, L}, NodeDict))
    end.

Linking the graph is just a matter of running through the list of node names and sending a link message for each node they're connected to. We use two foreach calls to reduce code depth:

linkGraph(Dict) ->
    lists:foreach(
        fun(X) -> 
            {_, {Pid, L}} = X,
            lists:foreach(
                fun(LinkName) -> 
                    {LinkPid,_} = dict:fetch(LinkName, Dict),
                    Pid ! {link, LinkName, LinkPid} 
                end,
             L)
         end,
        dict:to_list(Dict)).

Running the search

To run the search we have three things to do: take input from the user, send a search message to the source node for the search and send an endPoint message to the intended destination. The function will repeat immediately, so the solution may be printed below the next prompt. Again, the formatting punctuation in the input is not required since we're using the Erlang scanner.

runSearch(LinkDict) ->
        case io:get_line('enter start -> end: ') of
            eof -> exit(die);
            String ->
                case erl_scan:string(String) of
                    {ok, [{atom, 1, quit}], _} -> finished;
                    {ok, Tokens, _} -> 
                        [Start , End | _] = getAtoms(Tokens),
                        {EndPid, _} = dict:fetch(End, LinkDict),
                        EndPid ! {endPoint},
                        {StartPid, _} = dict:fetch(Start, LinkDict),
                        StartPid ! {search, []},
                        runSearch(LinkDict);
                    _ -> runSearch(LinkDict)
                end
        end.

All that's left to do is put it all together.

start() ->
    io:format("Nodes: ",[]),
    LinkDict = buildGraph(element(2,file:open("names.gph", [read])), dict:new()),
    io:format("~n",[]),
    runSearch(LinkDict).

Now, this program isn't perfect, and relies on the rejected search paths completing their paths before the next search is started -- fine for small graphs, so long as you're entering the source and destination nodes at the prompt -- but not guaranteed to work.

Obviously, outside of examples, you'll want to incorporate a method for handling the branching of search traversals, either by returning multiple paths, or by keeping track of the number of messages in the wild.

The source code for this program can be downloaded here.

0 comments