Struct TreeDecomposition 

pub struct TreeDecomposition { /* private fields */ }

A tree decomposition: bags of vertices, and an acyclic adjacency over them.

TreeDecomposition::new validates the full graph contract. PACE text can be parsed before its input graph is available, so call TreeDecomposition::validate on a value returned by TreeDecomposition::from_td. A disconnected graph may have one bag-tree component per graph component.

Implementations

impl TreeDecomposition

pub fn new( graph: &Graph, bags: impl IntoIterator<Item = Vec<u32>>, tree_edges: impl IntoIterator<Item = (usize, usize)>, ) -> Result<Self, Error>

Build and validate a tree decomposition of graph.

tree_edges are undirected pairs of indices into bags.

pub fn num_vertices(&self) -> u32

Number of vertices in the graph this decomposition was built for.

pub fn bags(&self) -> &[TdBag]

Bags in index order.

pub fn adjacency(&self) -> &[Vec<usize>]

Undirected bag adjacency, indexed like Self::bags. A decomposition built with Self::new has neighbours sorted by bag index; algorithms constructing a decomposition directly may expose their stable traversal order instead.

pub fn treewidth(&self) -> u32

This decomposition’s width: the vertices in its largest bag, less one. 0 where there is nothing to separate — no bags, one empty bag and one single-vertex bag alike.

An upper bound on the decomposed graph’s treewidth, which is the minimum width over all of its decompositions.

pub fn total_bag_size(&self) -> usize

Sum of bag sizes: the secondary quality signal beside the width. Two decompositions of equal width can have very different total bag volume.

pub fn validate(&self, graph: &Graph) -> Result<(), Error>

Check that this is a tree decomposition of graph.

This checks bag contents and acyclic bag adjacency, vertex and edge coverage, and the running intersection property. An empty decomposition is valid for an empty graph.

Examples found in repository

examples/basic.rs (line 25)

fn main() {
    let graph = Graph::new(
        8,
        [
            (0, 1),
            (1, 2),
            (3, 4),
            (4, 5),
            (0, 3),
            (1, 4),
            (2, 5),
            (1, 3),
            (2, 4),
            (4, 6),
            (5, 6),
            (5, 7),
            (6, 7),
        ],
    );
    let td = decompose(&graph, Order::MinFill, 0, None).expect("valid order");

    td.validate(&graph).expect("a valid decomposition");
    print!("{}", td.to_td());
}

impl TreeDecomposition

pub fn rooted_forest( &self, roots: impl IntoIterator<Item = usize>, ) -> Result<RootedForest, Error>

Root this decomposition’s bag forest and walk it breadth-first.

Each entry in roots that has not already been reached opens a new component. Any component not named in roots is then rooted at its first bag, so every bag occurs in the result.

Errors

Returns an error when a root is not a bag index.

pub fn project(&self, keep: &[u32]) -> Result<Projection, Error>

Project onto keep, renumbering its sorted unique vertex ids to 0..k. Projecting onto an empty set returns an empty decomposition.

Errors

Returns an error when a requested vertex is outside this decomposition’s vertex range or occurs in no bag.

impl TreeDecomposition

pub fn to_td(&self) -> String

Render as a PACE .td decomposition (1-indexed bags and vertices). A decomposition forest is connected between component roots for the PACE format; an empty decomposition is written as one empty bag.

Examples found in repository

examples/basic.rs (line 26)

fn main() {
    let graph = Graph::new(
        8,
        [
            (0, 1),
            (1, 2),
            (3, 4),
            (4, 5),
            (0, 3),
            (1, 4),
            (2, 5),
            (1, 3),
            (2, 4),
            (4, 6),
            (5, 6),
            (5, 7),
            (6, 7),
        ],
    );
    let td = decompose(&graph, Order::MinFill, 0, None).expect("valid order");

    td.validate(&graph).expect("a valid decomposition");
    print!("{}", td.to_td());
}

pub fn from_td(text: &str) -> Result<Self, Error>

Read a PACE .td decomposition — a treewidth solver’s output.

Errors

Error::Parse describing what is wrong with text: a malformed solution or bag line, an unparseable id, a bag or vertex id outside the range the solution line declares, a bag list that does not define each declared bag exactly once, a maximum-bag-size mismatch, a bag graph that is not one tree, a missing declared vertex, a failed running-intersection check, or no bags at all.

Trait Implementations

impl Clone for TreeDecomposition

fn clone(&self) -> TreeDecomposition

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for TreeDecomposition

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Eq for TreeDecomposition

impl PartialEq for TreeDecomposition

fn eq(&self, other: &TreeDecomposition) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl StructuralPartialEq for TreeDecomposition