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 | |
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 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... | |
const TreeBag * | bag (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... | |
TreeDecomposition & | operator= (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 TreeDecomposition * | fromPACE (const std::string &str) |
Builds a tree decomposition from a string using the PACE text format. More... | |
static TreeDecomposition * | fromPACE (std::istream &in) |
Builds a tree decomposition from an input stream using the PACE text format. 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, 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.
|
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.