2
\$\begingroup\$

The following is my tree coloring realisation attempted to get a feel of Elixir (simple, but slow coloring algorithm from Principles of Distributed Computing). Coloring runs from the root, using alternative colors 0 and 1.

defmodule Graph do
  def add_v g, v, label do
    :digraph.add_vertex(g, v, label)
    g
  end

  def add_e g, v1, v2 do
    :digraph.add_edge(g, v1, v2)
    g
  end
end

defmodule GraphNode do
  import :digraph
  def worker parent, v, children do
    receive do
      {_, {parent_, :color, x}} when parent == parent_ ->
        (
        IO.puts "result: #{elem(v, 1)} color #{x}"
        Enum.map children,
          fn (child) ->
            send child, {self, {elem(v, 0), :color, 1 - x}}
          end
         )
      _ -> IO.puts "???"
    end
    worker(parent, v, children)
  end
end

defmodule ProcessGraph do
  import :digraph
  def start g, current, parent \\ nil do
    children = Enum.map out_neighbours(g, current),
       fn (v) -> ProcessGraph.start(g, v, current) end
    p = spawn(GraphNode, :worker, [parent, vertex(g, current), children])
    if is_nil parent do
      send p, {nil, {nil, :color, 0}}
    end
    p
  end
end

defmodule Graph.Examples do
  import Graph
  def example do
    :digraph.new([:acyclic])
    |> add_v(:root, "Root")
    |> add_v(:a1, "A1")
    |> add_e(:root, :a1)
  end

  def example2 do
    :digraph.new([:acyclic])
    |> add_v(:root, "Root")
    |> add_v(:a1, "A1")
    |> add_v(:a2, "A2")
    |> add_v(:a1b1, "B1")
    |> add_v(:a1b2, "B2")
    |> add_v(:a2b1, "B3")
    |> add_v(:a1b1c1, "C1")
    |> add_e(:root, :a1)
    |> add_e(:root, :a2)
    |> add_e(:a1, :a1b1)
    |> add_e(:a1, :a1b2)
    |> add_e(:a2, :a2b1)
    |> add_e(:a1b1, :a1b1c1)
  end
end

The idea is to have true "no sharing" between processes, so global graph structure is not available to "workers" (one worker per tree node).

As this is the longest of my first programs in Elixir, I am not sure if it is the best way

  • to use recursion to start workers
  • to have this format for message contents

Also, the way to add vertices and edges (in examples) seems to me quite Elixirish (if we do not use macros for making DSL).

After this I plan to implement more effective graph coloring algorithms.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.