Yog.Property.TreeDecomposition (YogEx v0.97.0)

Copy Markdown View Source

Represents a tree decomposition of a graph.

A valid tree decomposition satisfies three properties:

  1. Vertex coverage: The union of all bags equals all vertices of the graph.
  2. Edge coverage: For each edge (u, v), some bag contains both u and v.
  3. Running intersection: For each vertex v, the bags containing v form a connected subtree.

The width of a tree decomposition is max(|bag|) - 1. The treewidth of a graph is the minimum width over all valid tree decompositions.

Examples

iex> td = %Yog.Property.TreeDecomposition{
...>   bags: %{0 => MapSet.new([1, 2]), 1 => MapSet.new([2, 3])},
...>   tree: Yog.undirected() |> Yog.add_edge_ensure(0, 1, 1),
...>   width: 1
...> }
iex> is_struct(td, Yog.Property.TreeDecomposition)
true

Summary

Types

bag()

A bag is a set of vertices from the original graph.

t()

A tree decomposition struct containing bags, a tree graph connecting bag indices, and the decomposition width.

Functions

valid?(td, graph)

Validates that a tree decomposition satisfies all three properties.

Types

bag()

@type bag() :: MapSet.t(Yog.node_id())

A bag is a set of vertices from the original graph.

t()

@type t() :: %Yog.Property.TreeDecomposition{
  bags: %{required(non_neg_integer()) => bag()},
  tree: Yog.Graph.t(),
  width: non_neg_integer()
}

A tree decomposition struct containing bags, a tree graph connecting bag indices, and the decomposition width.

Functions

valid?(td, graph)

@spec valid?(t(), Yog.graph()) :: boolean()

Validates that a tree decomposition satisfies all three properties.

Examples

iex> graph = Yog.from_edges(:undirected, [{1, 2, 1}, {2, 3, 1}])
iex> {:ok, td} = Yog.Approximate.tree_decomposition(graph)
iex> Yog.Property.TreeDecomposition.valid?(td, graph)
true