Regina Calculation Engine
|
Represents a tree decomposition of a graph. More...
#include <treewidth/treedecomposition.h>
Classes | |
struct | Graph |
Represents a graph, which may be directed or undirected. More... | |
Public Member Functions | |
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... | |
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 TreeBag * | root () const |
Returns the bag at the root of the underlying tree. More... | |
const TreeBag * | first () const |
Used for a postfix iteration through all of the bags in the tree decomposition. More... | |
const TreeBag * | firstPrefix () const |
Used for a prefix iteration through all of the bags in the tree decomposition. More... | |
bool | compress () |
Removes redundant bags from this tree decomposition. More... | |
void | makeNice () |
Converts this into a nice tree decomposition. 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 | 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... | |
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... | |
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 manner; that is, for each non-root bag b, the parent of b will have a higher index than b itself. This 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(). (Note that TreeDecomposition does not store its bags in an array, and so does not offer a "random access" function to access the bag at an arbitrary index.)
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.
|
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.
|
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.
__str__()
.
|
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.