Chapter IX Directed Hamilton Circuit

Search in Erlang

Erlang's pattern matching and lightweight processes make a parallel backtracking search read like English.

01

Represent the graph as a map from vertex to a list of successors. Erlang's maps and lists are the natural shape — no defining structs, no boilerplate.
```
%% graph: #{a => [b,c], b => [c,d], c => [d], d => [a]}.
make_graph() ->
    #{a => [b,c], b => [c,d], c => [d], d => [a]}.
```

Recursive search. Pattern-match on whether the path is complete (and closes back to start) or extends to a successor not yet visited. lists:member is the visited check.

hamilton(G, Start) ->
    Vs = maps:keys(G),
    case search(G, Start, [Start], length(Vs)) of
        {ok, P} -> {ok, P};
        none    -> none
    end.

search(G, V, Path, N) when length(Path) =:= N ->
    case lists:member(hd(Path), maps:get(V, G)) of
        true  -> {ok, lists:reverse([hd(Path) | Path])};
        false -> none
    end;
search(G, V, Path, N) ->
    Succs = maps:get(V, G, []),
    try_succs(G, [S || S <- Succs, not lists:member(S, Path)], Path, N).

try_succs(_, [], _, _)         -> none;
try_succs(G, [S|R], Path, N) ->
    case search(G, S, [S|Path], N) of
        {ok, P} -> {ok, P};
        none    -> try_succs(G, R, Path, N)
    end.

Spawn a worker per branch when the search space gets big. The actor model lets one process handle each candidate first-step, gathering results via message passing. No shared state, no locks.

parallel_hamilton(G, Start) ->
    Self = self(),
    Succs = maps:get(Start, G, []),
    [spawn(fun() -> Self ! {self(), search(G, S, [S, Start], map_size(G))} end)
        || S <- Succs],
    wait_for_any(length(Succs)).

wait_for_any(0) -> none;
wait_for_any(N) ->
    receive
        {_, {ok, P}} -> {ok, P};
        {_, none}    -> wait_for_any(N-1)
    end.

04

Run it. Erlang shines when the problem decomposes into independent search branches — each lightweight process is ~300 bytes, so spawning thousands is normal.
```
1> reduce:hamilton(reduce:make_graph(), a).
{ok,[a,b,c,d,a]}
```

Grammar — Erlang

Erlang lives on the BEAM, the runtime built for telecom switches. Single-assignment variables, pattern matching, and lightweight processes are the whole language; the rest is the OTP libraries on top.

lowercase: an atom — a constant symbol. Like a string, but interned and cheap to compare.
Uppercase, _: a variable. Single-assignment: once bound, it cannot change.
f(X) -> ...; f(Y) -> ...: function clauses with pattern matching. The first matching head runs; clauses are separated by semicolons, ended by a period.
[H|T]: list cons pattern — H is the head, T is the rest.
#{a => 1, b => 2}: a map literal. maps:get(K, M) reads, maps:put(K, V, M) returns a new map with K updated.
case X of pat1 -> e1; pat2 -> e2 end: a case expression — pattern-match X against alternatives, return the first matching branch.
spawn(fun() -> ... end): start a new process. Returns a Pid; processes are cheap (~300 bytes each).
Pid ! Msg: send Msg to the mailbox of Pid. Asynchronous, never blocks.
receive Pat -> body end: block until a message matching Pat arrives, then run body. Add `after T -> ...` for a timeout.

Represent the directed graph as a map from vertex to a list of successors. Walking neighbors is just maps:get plus a list comprehension.

G = #{a => [b, c], b => [c, d], c => [d], d => [a]}.
Successors = maps:get(a, G).      % -> [b, c]

%% filter out already-visited vertices in one shot:
Visited = [a, b],
Frontier = [V || V <- Successors, not lists:member(V, Visited)].
%% Frontier -> [c]

Erlang — official site and docs →