Dave's page

Serializing Elixir digraphs to Yaml and back

1   Introduction

Underneath this work are two more basic capabilities:

  1. The Erlang :digraph module. For documentation see; https://erlang.org/doc/man/digraph.html.
  2. Yaml support for Elixir. You can think about Yaml as "readable XML". You can read about it here: https://yaml.org/. There are several implementations for Elixir:

2   The source code

You can find the source code for the capabilities described in this document here: digraph01.ex.

3   Set-up, configuration, etc

If you need one, create a new mix project. Example:

$ mix new digraphyamlproj

Configure dependencies. Add the following to your new mix.exs:

defp deps do
  [
    {:yaml_elixir, "~> 2.0.2"},
    {:yamlix, github: "joekain/yamlix"},
  ]
end

This is the module that implements our support for digraphs and Yaml. Copy it into your new project's lib/ directory -- digraph01.ex.

Then do:

$ mix deps.get
$ mix deps.compile
$ mix compile

And, then:

$ iex -S mix

Or, if you want history in your interactive shell, set the environment variable ERL_AFLAGS. For example:

$ ERL_AFLAGS="-kernel shell_history enabled" iex -S mix

4   Exercises for Yaml and digraphs

4.1   Yaml

Read a Yaml file:

iex> {:ok, data} = YamlElixir.read_from_file("Data/test03.yaml")
{:ok,
 %{
   "description" => "Sample graph one",
   "edges" => [
     ["n1", "n2", "edge1"],
     ["n2", "n3", "edge2"],
     ["n1", "n4", "edge3"]
   ],
   "name" => "graph01",
   "nodes" => [
     ["n1", "node n1"],
     ["n2", "node n2"],
     ["n3", "node n3"],
     ["n4", "node n4"]
   ]
 }}

Notes:

  • The data returned (actually inside a tuple) is an Elixir Map.

Serialize an Elixir data structure and write to a file -- We use Yamlix:

iex> content = Yamlix.dump(data)
"--- \ndescription: Sample graph one\nedges:\n- \n  - n1\n  - n2\n  - edge1\n- \n  - n2\n  - n3\n  - edge2\n- \n  - n1\n  - n4\n  - edge3\nname: graph01\nnodes:\n- \n  - n1\n  - node n1\n- \n  - n2\n  - node n2\n- \n  - n3\n  - node n3\n- \n  - n4\n  - node n4\n...\n"
iex>
nil
iex> File.write("content01.yaml", content)
:ok

4.2   Digraphs

Create a digraph -- We use the Erlang :digraph module -- Examples:

Here is a function that creates a sample digraph:

def create_digraph() do
  digraph = :digraph.new()
  vertices = ["vertex1", "vertex2", "vertex3", "vertex4"]
  |> Enum.map(fn label ->
    vertex = :digraph.add_vertex(digraph)
    :digraph.add_vertex(digraph, vertex, label)
  end)
  [v1, v2, v3, v4] = vertices
  :digraph.add_edge(digraph, v1, v2, "edge-1-2")
  :digraph.add_edge(digraph, v2, v3, "edge-2-3")
  :digraph.add_edge(digraph, v1, v4, "edge-1-4")
  digraph
end

And, here are some examples of its use:

iex> d = Test03.create_digraph()
{:digraph, #Reference<0.1196513916.555876353.174481>,
 #Reference<0.1196513916.555876353.174482>,
 #Reference<0.1196513916.555876353.174483>, true}
iex> v = :digraph.vertices(d)
[[:"$v" | 1], [:"$v" | 2], [:"$v" | 3], [:"$v" | 0]]
iex> v1 = hd v
[:"$v" | 1]
iex> :digraph.vertex(d, v1)
{[:"$v" | 1], "vertex2"}
iex> e = :digraph.edges(d)
[[:"$e" | 0], [:"$e" | 1], [:"$e" | 2]]
iex> e1 = hd e
[:"$e" | 0]
iex> :digraph.edge(d, e1)
{[:"$e" | 0], [:"$v" | 0], [:"$v" | 1], "edge-1-2"}

5   Implementation and usage details

5.1   The external Yaml representation

Here is a example of the Yaml content that represents a simple digraph:

---
description: Sample graph one
edges:
-
  - n1
  - n2
  - "edge1"
-
  - n2
  - n3
  - "edge2"
-
  - n1
  - n4
  - "edge3"
name: graph01
nodes:
-
  - n1
  - "node n1"
-
  - n2
  - "node n2"
-
  - n3
  - "node n3"
-
  - n4
  - "node n4"
...

Notes:

  • The outer-most (top-most) item is a map (or dict or associative array).
  • The name and description are strings.
  • The edges and nodes (vertices) are lists (arrays). This makes them easy to process in Elixir with Enum.each/2 and Enum.map/2.

5.2   Load a digraph from a Yaml file

This function loads a digraph from a Yaml file:

@doc """
Load (create) a digraph from a Yaml file.

## Examples

```
iex> graph1 = Test03.Digraph.load_from_yaml("junk02a.yaml")
node_names: ["n1", "n2", "n3", "n4"]
vertices: [n1: [:"$v" | 0], n2: [:"$v" | 1], n3: [:"$v" | 2], n4: [:"$v" | 3]]
edges: [[:"$e" | 0], [:"$e" | 1], [:"$e" | 2]]
{:ok,
 {:digraph, #Reference<0.1474948976.2438856707.116099>,
  #Reference<0.1474948976.2438856707.116100>,
  #Reference<0.1474948976.2438856707.116101>, true}, "graph01",
 "Sample graph one", ["n1", "n2", "n3", "n4"],
 [["n1", "n2"], ["n2", "n3"], ["n1", "n4"]],
 [n1: [:"$v" | 0], n2: [:"$v" | 1], n3: [:"$v" | 2], n4: [:"$v" | 3]],
 [[:"$e" | 0], [:"$e" | 1], [:"$e" | 2]]}
```

"""
@spec load_from_yaml(Path.t()) :: {:ok, digraph()}
def load_from_yaml(in_file_path) do
  {:ok, data} = YamlElixir.read_from_file(in_file_path)
  #{:ok, name} = Map.fetch(data, "name")
  #{:ok, description} = Map.fetch(data, "description")
  {:ok, yaml_nodes} = Map.fetch(data, "nodes")
  {:ok, yaml_edges} = Map.fetch(data, "edges")
  graph = :digraph.new()
  IO.inspect(yaml_nodes, label: "nodes")
  IO.inspect(yaml_edges, label: "edges")
  vertices = Enum.map(yaml_nodes, fn [node_name, label] ->
    node_name_atom = String.to_atom(node_name)
    vertex1 = :digraph.add_vertex(graph)
    vertex2 = :digraph.add_vertex(graph, vertex1, label)
    {node_name_atom, vertex2}
  end)
  edges = Enum.each(yaml_edges, fn [from_node, to_node, label] ->
    from_node_atom = String.to_atom(from_node)
    to_node_atom = String.to_atom(to_node)
    v1 = Keyword.get(vertices, from_node_atom)
    v2 = Keyword.get(vertices, to_node_atom)
    if not (is_nil(v1) or is_nil(v2)) do
      :digraph.add_edge(graph, v1, v2, label)
    end
  end)
  IO.inspect(vertices, label: "vertices")
  IO.inspect(edges, label: "edges")
  db_vertices = :digraph.vertices(graph)
  db_edges = :digraph.edges(graph)
  IO.inspect(db_vertices, label: "db_vertices")
  IO.inspect(db_edges, label: "db_edges")
  {:ok, graph}
end

Notes:

  • We use YamlElixir to read the file and convert it to Elixir data structures.
  • The Elixir Map module helps us extract the top-level items.
  • Edges and vertices are lists, so we use the Enum module to iterate over them.
  • While creating the vertices, we also create an Elixir Keyword list so that we can look up the to and from vertices while creating the edges.

5.3   Write a digraph to a Yaml file

These functions convert a digraph to the appropriate data structures that can be written to a Yaml file:

@doc """
Serialize a digraph and write it to a Yaml file given the
digraph, a name, and a description.

## Examples

```
iex> Digraph.write_to_yaml("save01.yaml", digraph1, "digraph-1", "digraph number one", true)
```

"""
@spec write_to_yaml(String.t(), digraph(), String.t(), String.t(), boolean()) :: :ok
def write_to_yaml(out_file_path, digraph, name, description, force \\ false) do
  {:ok, structure} = digraph_to_structure(digraph, name, description)
  #IO.inspect(structure, label: "structure")
  write_yaml(out_file_path, structure, force)
  :ok
end

@doc """
Convert a digraph to a data structure suitable for serializing to Yaml.

## Examples

```
iex> {:ok, data} = Digraph.digraph_to_structure(d1, "digraph001", "a sample digraph")
{:ok,
 %{
   "description" => "a sample digraph",
   "edges" => [
     ["n3", "n2", "edge1"],
     ["n2", "n1", "edge2"],
     ["n3", "n0", "edge3"]
   ],
   "name" => "digraph001",
   "nodes" => [
     ["n2", "node n2"],
     ["n0", "node n4"],
     ["n3", "node n1"],
     ["n1", "node n3"]
   ]
 }}
```

"""
@spec digraph_to_structure(digraph(), String.t(), String.t()) :: {:ok, map()}
def digraph_to_structure(digraph, name, description) do
  vertices = :digraph.vertices(digraph)
  edges = :digraph.edges(digraph)
  converted_vertices = Enum.map(vertices, fn vertex ->
    {[_ | nodeitem], label} = :digraph.vertex(digraph, vertex)
    nodename = "n" <> Integer.to_string(nodeitem)
    [nodename, label]
  end)
  converted_edges = Enum.map(edges, fn edge ->
    {_, vertex1, vertex2, label} = :digraph.edge(digraph, edge)
    {[_ | nodeitem1], _label1} = :digraph.vertex(digraph, vertex1)
    {[_ | nodeitem2], _label2} = :digraph.vertex(digraph, vertex2)
    nodename1 = "n" <> Integer.to_string(nodeitem1)
    nodename2 = "n" <> Integer.to_string(nodeitem2)
    [nodename1, nodename2, label]
  end)
  converted_digraph = %{
    "name" => name,
    "description" => description,
    "nodes" => converted_vertices,
    "edges" => converted_edges,
  }
  {:ok, converted_digraph}
end

Notes:

  • We call digraph_to_structure/3 to convert a digraph that is represented by the Erlang :digraph module.

  • This function (digraph_to_structure/3) converts a digraph into an Elixir Map that contains lists etc. That data structure is suitable for writing to a Yaml file.

  • Here is a simple example of that data structure:

    iex> Digraph.digraph_to_structure(d1, "digraph01", "Digraph number one")
{:ok,
 %{
   "description" => "Digraph number one",
   "edges" => [
         ["n0", "n1", "edge1"],
         ["n1", "n2", "edge2"],
         ["n0", "n3", "edge3"]
   ],
   "name" => "digraph01",
   "nodes" => [
         ["n1", "node n2"],
         ["n2", "node n3"],
         ["n3", "node n4"],
         ["n0", "node n1"]
   ]
 }}

Published

Category

elixir

Tags

Contact