Regina Calculation Engine
Classes | Public Member Functions | Static Public Member Functions | List of all members
regina::TreeDecomposition Class Reference

Represents a tree decomposition of a graph. More...

#include <treewidth/treedecomposition.h>

Inheritance diagram for regina::TreeDecomposition:
regina::Output< TreeDecomposition >

Classes

struct  Graph
 Represents a graph, which may be directed or undirected. More...
 

Public Member Functions

 TreeDecomposition (const TreeDecomposition &cloneMe)
 Builds a new copy of the given tree decomposition. More...
 
template<int dim>
 TreeDecomposition (const Triangulation< dim > &triangulation, TreeDecompositionAlg alg=TD_UPPER)
 Builds a tree decomposition of the facet pairing graph of the given triangulation. More...
 
template<int dim>
 TreeDecomposition (const FacetPairing< dim > &pairing, TreeDecompositionAlg alg=TD_UPPER)
 Builds a tree decomposition of the given facet pairing graph. More...
 
 TreeDecomposition (const Link &link, TreeDecompositionAlg alg=TD_UPPER)
 Builds a tree decomposition of the planar multigraph corresponding to the given knot or link diagram. More...
 
template<typename T >
 TreeDecomposition (unsigned order, T const **const graph, TreeDecompositionAlg alg=TD_UPPER)
 Builds a tree decomposition of an arbitrary graph. More...
 
 ~TreeDecomposition ()
 Destroys this tree decomposition and all of its bags. More...
 
int width () const
 Returns the width of this tree decomposition. More...
 
int size () const
 Returns the number of bags in this tree decomposition. More...
 
const TreeBagroot () const
 Returns the bag at the root of the underlying tree. More...
 
const TreeBagfirst () const
 Used for a postfix iteration through all of the bags in the tree decomposition. More...
 
const TreeBagfirstPrefix () const
 Used for a prefix iteration through all of the bags in the tree decomposition. More...
 
const TreeBagbag (int index) const
 A slow (linear-time) routine that returns the bag at the given index. More...
 
bool compress ()
 Removes redundant bags from this tree decomposition. More...
 
void makeNice (int *heightHint=nullptr)
 Converts this into a nice tree decomposition. More...
 
void reroot (TreeBag *newRoot)
 Reverses child-parent relationships so that the given bag becomes the root of the tree decomposition. More...
 
template<typename T >
void reroot (const T *costSame, const T *costReverse, const T *costRoot=nullptr)
 Reroots the tree by reversing child-parent relationships, in a way that minimises a maximum estimated processing cost amongst all bags. More...
 
void writeDot (std::ostream &out) const
 Outputs this tree decomposition in the Graphviz DOT language. More...
 
std::string dot () const
 Returns a Graphviz DOT representation of this tree decomposition. More...
 
void writePACE (std::ostream &out) const
 Outputs this tree decomposition using the PACE text format. More...
 
std::string pace () const
 Returns a text representation of this tree decomposition using the PACE text format. More...
 
void writeTextShort (std::ostream &out) const
 Writes a short text representation of this object to the given output stream. More...
 
void writeTextLong (std::ostream &out) const
 Writes a detailed text representation of this object to the given output stream. More...
 
TreeDecompositionoperator= (const TreeDecomposition &)=delete
 
std::string str () const
 Returns a short text representation of this object. More...
 
std::string utf8 () const
 Returns a short text representation of this object using unicode characters. More...
 
std::string detail () const
 Returns a detailed text representation of this object. More...
 

Static Public Member Functions

static TreeDecompositionfromPACE (const std::string &str)
 Builds a tree decomposition from a string using the PACE text format. More...
 
static TreeDecompositionfromPACE (std::istream &in)
 Builds a tree decomposition from an input stream using the PACE text format. More...
 

Detailed Description

Represents a tree decomposition of a graph.

Whilst this class can be used to build tree decompositions of arbitrary graphs, it also offers a simple interface for building a tree decomposition of the facet pairing graph of a given triangulation. This is an important step in the implementation of fixed-parameter tractable algorithms on triangulated manifolds.

Given a graph G, a tree decomposition of G consists of (i) an underlying tree T; and (ii) a bag at every node of this tree. Each bag is a set of zero or more nodes of G, and these bags are subject to the following constraints:

In Regina, the underlying tree T is a rooted tree, so that every non-root bag has exactly one parent bag, and every bag has some number of children (possibly many, possibly zero).

Tree decompositions are generally considered "better" if their bags are smaller (i.e., contain fewer nodes of G). To this end, the width of a tree decomposition is one less than its largest bag size, and the treewidth of G is the minimum width over all tree decompositions of G.

A tree decomposition is described by a single TreeDecomposition object, and the class TreeBag is used to represent each individual bag.

The bags themselves are stored as sets of integers: it is assumed that the nodes of G are numbered 0,1,2,..., and so the bags simply store the numbers of the nodes that they contain.

This class also numbers its bags 0,1,...,size()-1 in a leaves-to-root, left-to-right manner:

This bag numbering may be useful if you wish to store auxiliary information alongside each bag in a separate array. You can access this numbering through the function TreeBag::index(). However, note that TreeDecomposition does not store its bags in an array, and so the "random access" function bag() is slow, with worst-case linear time.

There are two broad classes of algorithms for building tree decompositions: (i) exact algorithms, which are slow but guarantee to find a tree decomposition of the smallest possible width; and (ii) greedy algorithms, which are fast and which aim to keep the width small but which do not promise minimality. Currently Regina only offers greedy algorithms, though this may change in a future release. See the TreeDecompositionAlg enumeration for a list of all algorithms that are currently available.

Note that individual bags are allowed to be empty. Moreover, if the underlying graph G is empty then the tree decomposition may contain no bags at all.

Member Function Documentation

◆ detail()

std::string regina::Output< TreeDecomposition , false >::detail ( ) const
inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns
a detailed text representation of this object.

◆ str()

std::string regina::Output< TreeDecomposition , false >::str ( ) const
inherited

Returns a short text representation of this object.

This text should be human-readable, should fit on a single line, and should not end with a newline. Where possible, it should use plain ASCII characters.

Python
In addition to str(), this is also used as the Python "stringification" function str().
Returns
a short text representation of this object.

◆ utf8()

std::string regina::Output< TreeDecomposition , false >::utf8 ( ) const
inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should fit on a single line, and should not end with a newline. In addition, it may use unicode characters to make the output more pleasant to read. This string will be encoded in UTF-8.

Returns
a short text representation of this object.

The documentation for this class was generated from the following file:

Copyright © 1999-2021, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).