Contents
1 Introduction
Underneath this work are two more basic capabilities:
- The Erlang :digraph module. For documentation see; https://erlang.org/doc/man/digraph.html.
- 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:
- For loading and "de-serializing" (converting Yaml text to Elixir data structures) we will use the YamlElixir module: https://github.com/KamilLelonek/yaml-elixir. Which, in turn is built on top of yamerl: https://github.com/yakaz/yamerl.
- And, for serializing (converting an Elixir data structure to Yaml text) we will use YamLix: https://github.com/joekain/yamlix. The author makes qualifications about how it is a work-in-progress, but it seems suitable for our purposes.
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"] ] }}