defmodule Graphvix.Graph do
@moduledoc """
Models a directed graph that can be written to disk and displayed using
[Graphviz](http://www.graphviz.org/) notation.
Graphs are created by
* adding vertices of various formats to a graph
* `add_vertex/3`
* `add_record/2`
* `add_html_record/2`
* connecting them with edges
* `add_edge/4`
* grouping them into subgraphs and clusters,
* `add_subgraph/3`
* `add_cluster/3`
* providing styling to all these elements
* `set_graph_property/3`
* `set_global_properties/3`
They can then be
* written to disk in `.dot` format
* `write/2`
* compiled and displayed in any number of image formats (`Graphvix` defaults to `.png`)
* `compile/3`
* `show/2`
"""
import Graphvix.DotHelpers
alias Graphvix.{HTMLRecord, Record}
defstruct digraph: nil,
global_properties: [node: [], edge: []],
graph_properties: [],
subgraphs: []
@type digraph :: {:digraph, reference(), reference(), reference(), boolean()}
@type t :: %__MODULE__{
digraph: digraph(),
global_properties: keyword(),
graph_properties: keyword(),
subgraphs: list()
}
@compiler Application.compile_env(:graphvix, :compiler, "dot")
@doc """
Creates a new `Graph` struct.
A `Graph` struct consists of an Erlang `digraph` record, a list of subgraphs,
and two keyword lists of properties.
## Examples
iex> graph = Graph.new()
iex> Graph.to_dot(graph)
~S(digraph G {
})
iex> graph = Graph.new(graph: [size: "4x4"], node: [shape: "record"])
iex> Graph.to_dot(graph)
~S(digraph G {
size="4x4"
node [shape="record"]
})
"""
def new(attributes \\ []) do
digraph = :digraph.new()
[_, _, ntab] = _digraph_tables(digraph)
true = :ets.insert(ntab, {:"$sid", 0})
%__MODULE__{
digraph: digraph,
global_properties: [
node: Keyword.get(attributes, :node, []),
edge: Keyword.get(attributes, :edge, [])
],
graph_properties: Keyword.get(attributes, :graph, [])
}
end
@doc """
Destructures the references to the ETS tables for vertices, edges, and
neighbours from the `Graph` struct.
## Examples
iex> graph = Graph.new()
iex> Graph.digraph_tables(graph)
[
#Reference<0.4011094290.3698196484.157076>,
#Reference<0.4011094290.3698196484.157077>,
#Reference<0.4011094290.3698196484.157078>
]
"""
def digraph_tables(%__MODULE__{digraph: graph}), do: _digraph_tables(graph)
defp _digraph_tables({:digraph, vtab, etab, ntab, _}) do
[vtab, etab, ntab]
end
@doc """
Adds a vertex to `graph`.
The vertex's label text is the argument `label`, and additional attributes
can be passed in as `attributes`. It returns a tuple of the updated graph
and the `:digraph`-assigned ID for the new vertex.
## Examples
iex> graph = Graph.new()
iex> {_graph, vid} = Graph.add_vertex(graph, "hello", color: "blue")
iex> vid
[:"$v" | 0]
"""
def add_vertex(graph, label, attributes \\ []) do
next_id = get_and_increment_vertex_id(graph)
attributes = Keyword.put(attributes, :label, label)
vertex_id = [:"$v" | next_id]
vid = :digraph.add_vertex(graph.digraph, vertex_id, attributes)
{graph, vid}
end
@doc """
Add an edge between two vertices in a graph.
It takes 3 required arguments and one optional. The first argument is the graph,
the second two arguments are the tail and head of the edge respectively, and the
fourth, optional, argument is a list of layout attributes to apply to the edge.
The arguments for the ends of the edge can each be either the id of a vertex, or
a tuple of a vertex id and a port name to attach the edge to. This second
option is only valid with `Record` or `HTMLRecord` vertices.
## Examples
iex> graph = Graph.new()
iex> {graph, v1id} = Graph.add_vertex(graph, "start")
iex> {graph, v2id} = Graph.add_vertex(graph, "end")
iex> {_graph, eid} = Graph.add_edge(graph, v1id, v2id, color: "green")
iex> eid
[:"$e" | 0]
"""
def add_edge(graph, out_from, in_to, attributes \\ [])
def add_edge(graph, {id = [:"$v" | _], port}, in_to, attributes) do
add_edge(graph, id, in_to, Keyword.put(attributes, :outport, port))
end
def add_edge(graph, out_from, {id = [:"$v" | _], port}, attributes) do
add_edge(graph, out_from, id, Keyword.put(attributes, :inport, port))
end
def add_edge(graph, out_from, in_to, attributes) do
eid = :digraph.add_edge(graph.digraph, out_from, in_to, attributes)
{graph, eid}
end
@doc """
Group a set of vertices into a subgraph within a graph.
In addition to the graph and the vertex ids, you can pass attributes for
`node` and `edge` to apply common styling to the vertices included
in the subgraph, as well as the edges between two vertices both in the subgraph.
## Examples
iex> graph = Graph.new()
iex> {graph, v1id} = Graph.add_vertex(graph, "start")
iex> {graph, v2id} = Graph.add_vertex(graph, "end")
iex> {_graph, sid} = Graph.add_subgraph(
...> graph, [v1id, v2id],
...> node: [shape: "triangle"],
...> edge: [style: "dotted"]
...> )
iex> sid
"subgraph0"
"""
def add_subgraph(graph, vertex_ids, properties \\ []) do
_add_subgraph(graph, vertex_ids, properties, false)
end
@doc """
Group a set of vertices into a cluster in a graph.
In addition to the graph and the vertex ids, you can pass attributes
for `node` and `edge` to apply common styling to the vertices included
in the cluster, as well as the edges between two vertices both in the cluster.
The difference between a cluster and a subgraph is that a cluster can also
accept attributes to style the cluster, such as a border, background color,
and custom label. These attributes can be passed as top-level attributes in
the final keyword list argument to the function.
## Example
iex> graph = Graph.new()
iex> {graph, v1id} = Graph.add_vertex(graph, "start")
iex> {graph, v2id} = Graph.add_vertex(graph, "end")
iex> {_graph, cid} = Graph.add_cluster(
...> graph, [v1id, v2id],
...> color: "blue", label: "cluster0",
...> node: [shape: "triangle"],
...> edge: [style: "dotted"]
...> )
iex> cid
"cluster0"
In `.dot` notation a cluster is specified, as opposed to a subgraph, by
giving the cluster an ID that begins with `"cluster"` as seen in the example
above. Contrast with `Graphvix.Graph.add_subgraph/3`.
"""
def add_cluster(graph, vertex_ids, properties \\ []) do
_add_subgraph(graph, vertex_ids, properties, true)
end
@doc """
Add a vertex built from a `Graphvix.Record` to the graph.
iex> graph = Graph.new()
iex> record = Record.new(["a", "b", "c"])
iex> {_graph, rid} = Graph.add_record(graph, record)
iex> rid
[:"$v" | 0]
See `Graphvix.Record` for details on `Graphvix.Record.new/2`
and the complete module API.
"""
def add_record(graph, record) do
label = Record.to_label(record)
attributes = Keyword.put(record.properties, :shape, "record")
add_vertex(graph, label, attributes)
end
@doc """
Add a vertex built from a `Graphvix.HTMLRecord` to the graph.
iex> graph = Graph.new()
iex> record = HTMLRecord.new([
...> HTMLRecord.tr([
...> HTMLRecord.td("start"),
...> HTMLRecord.td("middle"),
...> HTMLRecord.td("end"),
...> ])
...> ])
iex> {_graph, rid} = Graph.add_html_record(graph, record)
iex> rid
[:"$v" | 0]
See `Graphvix.HTMLRecord` for details on `Graphvix.HTMLRecord.new/2`
and the complete module API.
"""
def add_html_record(graph, record) do
label = HTMLRecord.to_label(record)
attributes = [shape: "plaintext"]
add_vertex(graph, label, attributes)
end
@doc """
Converts a graph to its representation using `.dot` syntax.
## Example
iex> graph = Graph.new(node: [shape: "triangle"], edge: [color: "green"], graph: [size: "4x4"])
iex> {graph, vid} = Graph.add_vertex(graph, "a")
iex> {graph, vid2} = Graph.add_vertex(graph, "b")
iex> {graph, vid3} = Graph.add_vertex(graph, "c")
iex> {graph, eid} = Graph.add_edge(graph, vid, vid2)
iex> {graph, eid2} = Graph.add_edge(graph, vid, vid3)
iex> {graph, clusterid} = Graph.add_cluster(graph, [vid, vid2])
iex> Graph.to_dot(graph)
~S(digraph G {
size="4x4"
node [shape="triange"]
edge [color="green"]
subgraph cluster0 {
v0 [label="a"]
v1 [label="b"]
v0 -> v1
}
v2 [label="c"]
v1 -> v2
})
For more expressive examples, see the `.ex` and `.dot` files in the `examples/` directory of
Graphvix's source code.
"""
def to_dot(graph) do
[
"digraph G {",
graph_properties_to_dot(graph),
global_properties_to_dot(graph),
subgraphs_to_dot(graph),
vertices_to_dot(graph),
edges_to_dot(graph),
"}"
]
|> Enum.reject(&is_nil/1)
|> Enum.join("\n\n")
end
@doc """
Writes a `Graph` to a named file in `.dot` format
```
iex> Graph.write(graph, "my_graph")
```
will write a file named `"my_graph.dot"` to your current working directory.
`filename` works as expected in Elixir. Filenames beginning with `/` define
an absolute path on your file system. Filenames otherwise define a path relative
to your current working directory.
"""
def write(graph, filename) do
File.write(filename <> ".dot", to_dot(graph))
end
@doc """
Writes the graph to a `.dot` file and compiles it to the specified output
format (defaults to `.png`).
The following code creates the files `"graph_one.dot"` and `"graph_one.png"`
in your current working directory.
```
iex> Graph.compile(graph, "graph_one")
```
This code creates the files `"graph_one.dot"` and `"graph_one.pdf"`.
```
iex> Graph.compile(graph, "graph_one", :pdf)
```
`filename` works as expected in Elixir. Filenames beginning with `/` define
an absolute path on your file system. Filenames otherwise define a path relative
to your current working directory.
"""
def compile(graph, filename, format \\ :png) do
:ok = write(graph, filename)
{output, 0} =
System.cmd(@compiler, [
"-T",
"#{format}",
filename <> ".dot",
"-o",
filename <> ".#{format}"
])
{:ok, String.trim(output)}
end
@doc """
Write a graph to file, compile it, and open the resulting image in your
system's default image viewer.
The following code will write the contents of `graph` to `"graph_one.dot"`,
compile the file to `"graph_one.png"` and open it.
```
iex> Graph.show(graph, "graph_one")
```
`filename` works as expected in Elixir. Filenames beginning with `/` define
an absolute path on your file system. Filenames otherwise define a path relative
to your current working directory.
"""
def show(graph, filename) do
:ok = write(graph, filename <> ".dot")
:ok = compile(graph, filename)
{_, 0} = System.cmd("open", [filename <> ".png"])
:ok
end
@doc """
Adds a top-level graph property.
These attributes affect the overall layout of the graph at a high level.
Use `set_global_properties/3` to modify the global styling for vertices
and edges.
## Example
iex> graph = Graph.new()
iex> graph.graph_properties
[]
iex> graph = Graph.set_graph_property(graph, :rank_direction, "RL")
iex> graph.graph_properties
[
rank_direction: "RL"
]
"""
def set_graph_property(graph, key, value) do
new_properties = Keyword.put(graph.graph_properties, key, value)
%{graph | graph_properties: new_properties}
end
@doc """
Sets a property for a vertex or edge that will apply to all vertices or edges
in the graph.
*NB* `:digraph` uses `vertex` to define the discrete points in
a graph that are connected via edges, while Graphviz and DOT use the word
`node`. `Graphvix` attempts to use "vertex" when the context is constructing
the data for the graph, and "node" in the context of formatting and printing
the graph.
## Example
```
iex> graph = Graph.new()
iex> {graph, vid} = Graph.add_vertex(graph, "label")
iex> graph = Graph.set_global_property(graph, :node, shape: "triangle")
```
When the graph is drawn, the vertex whose id is `vid`, and any other vertices
added to the graph, will have a triangle shape.
Global properties are overwritten by properties added by a subgraph or cluster:
```
{graph, subgraph_id} = Graph.add_subgraph(graph, [vid], shape: "hexagon")
```
Now when the graph is drawn the vertex `vid` will have a hexagon shape.
Properties written directly to a vertex or edge have the highest priority
of all. The vertex created below will have a circle shape despite the global
property set on `graph`.
```
{graph, vid2} = Graph.add_vertex(graph, "this is a circle!")
```
"""
def set_global_properties(graph, attr_for, attrs \\ []) do
Enum.reduce(attrs, graph, fn {k, v}, g ->
_set_global_property(g, attr_for, [{k, v}])
end)
end
## PRIVATE
defp _set_global_property(graph, attr_for, [{key, value}]) do
properties = Keyword.get(graph.global_properties, attr_for)
new_props = Keyword.put(properties, key, value)
new_properties = Keyword.put(graph.global_properties, attr_for, new_props)
%{graph | global_properties: new_properties}
end
defp subgraphs_to_dot(graph) do
case graph.subgraphs do
[] ->
nil
subgraphs ->
subgraphs
|> Enum.map_join("\n\n", &Graphvix.Subgraph.to_dot(&1, graph))
end
end
defp vertices_to_dot(graph) do
[vtab, _, _] = digraph_tables(graph)
elements_to_dot(vtab, fn {vid = [_ | id], attributes} ->
case in_a_subgraph?(vid, graph) do
true ->
nil
false ->
[
"v#{id}",
attributes_to_dot(attributes)
]
|> compact()
|> Enum.join(" ")
|> indent()
end
end)
end
defp edge_side_with_port(v_id, nil), do: "v#{v_id}"
defp edge_side_with_port(v_id, port), do: "v#{v_id}:#{port}"
defp edges_to_dot(graph) do
[_, etab, _] = digraph_tables(graph)
elements_to_dot(etab, fn edge = {_, [:"$v" | v1], [:"$v" | v2], attributes} ->
case edge in edges_contained_in_subgraphs(graph) do
true ->
nil
false ->
v_out = edge_side_with_port(v1, Keyword.get(attributes, :outport))
v_in = edge_side_with_port(v2, Keyword.get(attributes, :inport))
attributes = attributes |> Keyword.delete(:outport) |> Keyword.delete(:inport)
["#{v_out} -> #{v_in}", attributes_to_dot(attributes)]
|> compact()
|> Enum.join(" ")
|> indent()
end
end)
end
defp get_and_increment_vertex_id(graph) do
[_, _, ntab] = digraph_tables(graph)
[{:"$vid", next_id}] = :ets.lookup(ntab, :"$vid")
true = :ets.delete(ntab, :"$vid")
true = :ets.insert(ntab, {:"$vid", next_id + 1})
next_id
end
defp get_and_increment_subgraph_id(graph) do
[_, _, ntab] = digraph_tables(graph)
[{:"$sid", next_id}] = :ets.lookup(ntab, :"$sid")
true = :ets.delete(ntab, :"$sid")
true = :ets.insert(ntab, {:"$sid", next_id + 1})
next_id
end
defp in_a_subgraph?(vertex_id, graph) do
vertex_id in vertex_ids_in_subgraphs(graph)
end
defp vertex_ids_in_subgraphs(%__MODULE__{subgraphs: subgraphs}) do
Enum.reduce(subgraphs, [], fn c, acc ->
acc ++ c.vertex_ids
end)
end
defp edges_contained_in_subgraphs(graph = %__MODULE__{subgraphs: subgraphs}) do
[_, etab, _] = digraph_tables(graph)
edges = :ets.tab2list(etab)
Enum.filter(edges, fn {_, vid1, vid2, _} ->
Enum.any?(subgraphs, fn subgraph ->
Graphvix.Subgraph.both_vertices_in_subgraph?(subgraph.vertex_ids, vid1, vid2)
end)
end)
end
defp graph_properties_to_dot(%{graph_properties: []}), do: nil
defp graph_properties_to_dot(%{graph_properties: properties}) do
properties
|> Enum.map_join("\n", fn {k, v} ->
attribute_to_dot(k, v)
end)
|> indent
end
defp _add_subgraph(graph, vertex_ids, properties, is_cluster) do
next_id = get_and_increment_subgraph_id(graph)
subgraph = Graphvix.Subgraph.new(next_id, vertex_ids, is_cluster, properties)
new_graph = %{graph | subgraphs: graph.subgraphs ++ [subgraph]}
{new_graph, subgraph.id}
end
end
