Chapter X Undirected Hamilton Circuit

Concurrent search in Elixir

Elixir on the BEAM — same actor model as Erlang, but with pipelines and Task.async_stream giving you a parallel-search idiom in a single line.

Represent the graph as a map from vertex to a MapSet of neighbors. MapSet membership tests are O(log n) — fast enough that the visited-set check isn't your bottleneck.

defmodule Hamilton do
  def graph do
    %{
      :a => MapSet.new([:b, :c, :d]),
      :b => MapSet.new([:a, :c]),
      :c => MapSet.new([:a, :b, :d]),
      :d => MapSet.new([:a, :c])
    }
  end
end

Backtracking helper. Pattern matching on the path length lets us split "still extending" from "trying to close the loop" into two function clauses with no branching.

def search(_g, start, [v | _] = path, n) when length(path) == n do
  if start in elem(get_neighbors(_g, v), 0), do: {:ok, [start | path]}, else: :none
end

def search(g, start, [v | _] = path, n) do
  g[v]
  |> Enum.reject(&(&1 in path))
  |> Enum.find_value(:none, fn nxt ->
    case search(g, start, [nxt | path], n) do
      {:ok, full} -> {:ok, full}
      :none       -> nil
    end
  end)
end

Parallelize the first step with Task.async_stream. Each starting neighbor of the root gets its own lightweight process; the first one to find a circuit wins.

def parallel_hamilton(g, start) do
  n = map_size(g)
  g[start]
  |> Task.async_stream(fn nxt -> search(g, start, [nxt, start], n) end,
                       max_concurrency: System.schedulers_online())
  |> Enum.find_value(:none, fn
    {:ok, {:ok, p}} -> {:ok, p}
    _               -> nil
  end)
end

04

Run it from iex. Elixir's piped expressions read top-to-bottom — find a starting move, kick off the parallel search, return the first hit.
```
iex> Hamilton.parallel_hamilton(Hamilton.graph(), :a)
{:ok, [:a, :b, :c, :d, :a]}
```

Grammar — Elixir

Elixir is the modern face of the BEAM — same runtime and concurrency as Erlang, with a Ruby-flavored syntax and a pipeline operator that lets you read top-to-bottom data flow.

defmodule M do ... end: a module. The build unit; every function lives inside one.
def name(args), do: expr: one-line function definition. Use `def ... do ... end` for multi-line bodies.
:atom: an atom (constant symbol). Leading colon distinguishes it from variables.
%{key => value}: a map literal. Read with map[key]; pattern-match by listing keys.
|>: the pipe operator: `x |> f(y)` is `f(x, y)`. Lets data flow left-to-right through a transformation chain.
fn x -> body end: an anonymous function (lambda). Call it with `f.(arg)` — note the dot before the parenthesis.
&fun/arity: capture syntax — `&Enum.map/2` is a reference to Enum.map with two arguments.
MapSet.new([...]): an immutable set. MapSet.member?, MapSet.put, MapSet.union all return new sets.
Task.async_stream(items, fn): concurrent map. Pass `max_concurrency:` to bound parallelism.

Walk a vertex's neighbors and filter out the already-visited ones, all in a pipeline. Reads top-to-bottom: start with neighbors, reject the visited, find the first that closes a cycle.

g = %{a: [:b, :c], b: [:c, :d], c: [:d], d: [:a]}
visited = [:a, :b]

g[:b]
|> Enum.reject(&(&1 in visited))
|> Enum.find(fn nxt -> nxt == :a end)
# -> nil here; reject left only [:c, :d]

Livebook — interactive Elixir notebooks →