Yog.IO.Sparse6 (YogEx v0.97.0)

Copy Markdown View Source

Sparse6 format import/export for undirected simple graphs.

Sparse6 is a compact ASCII encoding for large, sparse, undirected simple graphs. Like graph6, it only supports undirected simple graphs with no loops or multiple edges. It stores edges column-by-column using a variable-length integer encoding, making it much more space-efficient than graph6 for sparse graphs.

Format

A sparse6 string starts with : followed by:

  1. A header encoding the number of vertices n (same as graph6)
  2. Edge data encoded as a sequence of variable-length integers

Edges are listed in order of the column (higher endpoint), and within each column in decreasing order of the smaller endpoint. For each column v:

  • If the column is empty: nothing is written
  • If the column has exactly the same edges as v-1: nothing is written
  • Otherwise: v is written first, followed by v - u for each edge (u, v)

Examples

iex> graph = Yog.undirected() |> Yog.add_edge_ensure(0, 1, 1) |> Yog.add_edge_ensure(1, 2, 1) |> Yog.add_edge_ensure(2, 3, 1) |> Yog.add_edge_ensure(3, 4, 1) |> Yog.add_edge_ensure(0, 4, 1)
iex> {:ok, s6} = Yog.IO.Sparse6.serialize(graph)
iex> String.starts_with?(s6, ":")
true

iex> {:ok, graph} = Yog.IO.Sparse6.parse(":DgA?")
iex> Yog.Model.node_count(graph)
5

See Also

Summary

Functions

parse(arg1)

Parses a sparse6 string into an undirected graph.

read(path)

Reads one or more sparse6 graphs from a file.

serialize(graph)

Serializes an undirected simple graph to a sparse6 string.

write(path, graphs)

Writes one or more graphs to a sparse6 file.

Functions

parse(arg1)

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

Parses a sparse6 string into an undirected graph.

Returns {:ok, graph} on success, or {:error, reason} if the string is malformed.

read(path)

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

Reads one or more sparse6 graphs from a file.

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

serialize(graph)

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

Serializes an undirected simple graph to a sparse6 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 sparse6 format.

write(path, graphs)

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

Writes one or more graphs to a sparse6 file.

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