Yog.IO.Graph6 (YogEx v1.0.0)

Copy Markdown View Source

Graph6 format import/export for undirected simple graphs.

Graph6 is a compact ASCII encoding for undirected simple graphs (no loops, no multiple edges). It encodes the upper triangle of the adjacency matrix column by column into printable characters.

This module provides bidirectional conversion between Yog.Graph structures and graph6 strings, as well as file I/O for datasets commonly found in graph theory repositories (e.g., House of Graphs, nauty).

Format

A graph6 string consists of:

  1. A header encoding the number of vertices n
  2. A payload of 6-bit chunks encoding the strict upper triangle of the adjacency matrix

Examples

iex> {:ok, graph} = Yog.IO.Graph6.parse("DqK")
iex> Yog.Model.node_count(graph)
5
iex> Yog.Model.edge_count(graph)
5

iex> graph = Yog.undirected() |> Yog.add_edge_ensure(0, 1, 1) |> Yog.add_edge_ensure(0, 2, 1) |> Yog.add_edge_ensure(1, 3, 1) |> Yog.add_edge_ensure(2, 4, 1) |> Yog.add_edge_ensure(3, 4, 1)
iex> {:ok, g6} = Yog.IO.Graph6.serialize(graph)
iex> g6
"DqK"

See Also

Summary

Functions

Parses a graph6 string into an undirected graph.

Reads one or more graph6 graphs from a file.

Serializes an undirected simple graph to a graph6 string.

Writes one or more graphs to a graph6 file.

Functions

parse(string)

@spec parse(String.t()) :: {:ok, Yog.graph()} | {:error, atom()}

Parses a graph6 string into an undirected graph.

Returns {:ok, graph} on success, or {:error, reason} if the string is empty, malformed, or contains invalid characters or payload lengths.

Raises ArgumentError if string is not a binary string.

Time complexity: $\mathcal{O}(V^2)$ where $V$ is the number of nodes.

Examples

iex> {:ok, graph} = Yog.IO.Graph6.parse("DqK")
iex> Yog.Model.node_count(graph)
5
iex> Yog.Model.edge_count(graph)
5

read(path)

@spec read(String.t()) :: {:ok, [Yog.graph()]} | {:error, atom()}

Reads one or more graph6 graphs from a file.

Each non-empty line in the file is treated as a separate graph6 string. Returns {:ok, [graph]} on success.

Raises ArgumentError if path is not a binary string.

serialize(graph)

@spec serialize(Yog.graph()) :: {:ok, String.t()} | {:error, atom()}

Serializes an undirected simple graph to a graph6 string.

The graph must be undirected, simple, and use integer node IDs 0..n-1.

Returns {:ok, string} on success, or {:error, reason} if the graph cannot be represented in graph6 format.

Raises ArgumentError if graph is not a Yog.Graph or Yog.DAG struct.

Time complexity: $\mathcal{O}(V^2 + E)$ where $V$ is the number of nodes and $E$ is the number of edges.

Examples

iex> graph = Yog.undirected() |> Yog.add_edge_ensure(0, 1, 1) |> Yog.add_edge_ensure(0, 2, 1) |> Yog.add_edge_ensure(1, 3, 1) |> Yog.add_edge_ensure(2, 4, 1) |> Yog.add_edge_ensure(3, 4, 1)
iex> {:ok, g6} = Yog.IO.Graph6.serialize(graph)
iex> g6
"DqK"

write(path, graphs)

@spec write(String.t(), Yog.graph() | [Yog.graph()]) :: :ok | {:error, atom()}

Writes one or more graphs to a graph6 file.

Accepts either a single graph or a list of graphs. Each graph is written on its own line.

Raises ArgumentError if path is not a binary string or if graphs is not a valid graph struct or list of graph structs.