Regina Calculation Engine
|
Represents a tree decomposition of a graph. More...
#include <treewidth/ntreedecomposition.h>
Classes | |
struct | Graph |
Represents a graph, which may be directed or undirected. More... | |
Public Member Functions | |
template<int dim> | |
NTreeDecomposition (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> | |
NTreeDecomposition (const FacetPairing< dim > &pairing, TreeDecompositionAlg alg=TD_UPPER) | |
Builds a tree decomposition of the given facet pairing graph. More... | |
template<typename T > | |
NTreeDecomposition (unsigned order, T const **const graph, TreeDecompositionAlg alg=TD_UPPER) | |
Builds a tree decomposition of an arbitrary graph. More... | |
~NTreeDecomposition () | |
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 NTreeBag * | root () const |
Returns the bag at the root of the underlying tree. More... | |
const NTreeBag * | first () const |
Used for a postfix iteration through all of the bags in the tree decomposition. More... | |
const NTreeBag * | 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... | |
REGINA_DEPRECATED std::string | toString () const |
A deprecated alias for str(). More... | |
REGINA_DEPRECATED std::string | toStringLong () const |
A deprecated alias for detail(). 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 NTreeDecomposition object, and the class NTreeBag 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 NTreeBag::index(). (Note that NTreeDecomposition 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.
regina::NTreeDecomposition::NTreeDecomposition | ( | const Triangulation< dim > & | triangulation, |
TreeDecompositionAlg | alg = TD_UPPER |
||
) |
Builds a tree decomposition of the facet pairing graph of the given triangulation.
The nodes of the graph will be numbered in the same way as the top-dimensional simplices of the given triangulation.
triangulation | the triangulation whose facet pairing graph we are working with. |
alg | the algorithm that should be used to compute the tree decomposition; in particular, this specifies whether to use a slow exact algorithm or a fast greedy algorithm. |
regina::NTreeDecomposition::NTreeDecomposition | ( | const FacetPairing< dim > & | pairing, |
TreeDecompositionAlg | alg = TD_UPPER |
||
) |
Builds a tree decomposition of the given facet pairing graph.
The nodes of the graph will be numbered in the same way as the top-dimensional simplices of the given triangulation.
pairing | the facet pairing graph that we are working with. |
alg | the algorithm that should be used to compute the tree decomposition; in particular, this specifies whether to use a slow exact algorithm or a fast greedy algorithm. |
regina::NTreeDecomposition::NTreeDecomposition | ( | unsigned | order, |
T const **const | graph, | ||
TreeDecompositionAlg | alg = TD_UPPER |
||
) |
Builds a tree decomposition of an arbitrary graph.
The graph may be directed or undirected.
The graph is specified by an adjacency matrix. The matrix may contain any data type (this is the template argument T). However, the contents of this matrix will be interpreted as booleans: an arc runs from node i to node j if and only if graph[i][j] is true
when interpreted as a boolean.
bool
and int
, but for other types you will need to include ntreedecomposition-impl.h along with this header.order | the number of nodes in the graph. |
graph | the adjacency matrix of the graph. |
alg | the algorithm that should be used to compute the tree decomposition; in particular, this specifies whether to use a slow exact algorithm or a fast greedy algorithm. |
|
inline |
Destroys this tree decomposition and all of its bags.
bool regina::NTreeDecomposition::compress | ( | ) |
Removes redundant bags from this tree decomposition.
Specifically, this routine "compresses" the tree decomposition as follows: whenever two bags are adjacent in the underlying tree and one is a subset of the other, these bags will be merged.
Note that some NTreeBag objects may be destroyed (thereby invalidating pointers or references to them), and for those bags that are not destroyed, their indices (as returned by NTreeBag::index()) may change.
true
if and only if the tree decomposition was changed.
|
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.
std::string regina::NTreeDecomposition::dot | ( | ) | const |
Returns a Graphviz DOT representation of this tree decomposition.
This routine simply returns the output of writeDot() as a string, instead of dumping it to an output stream.
See the writeDot() notes for further details.
const NTreeBag* regina::NTreeDecomposition::first | ( | ) | const |
Used for a postfix iteration through all of the bags in the tree decomposition.
Amongst other things, a postfix iteration is one in which all of the children of any bag b will be processed before b itself.
If d is a non-empty tree decomposition, then you can complete a full postfix iteration of bags as follows:
d.first()
;b.next()
;b.next()
is null
.This iteration processes the children of each bag in order; that is, it processes each bag b before b.sibling()
(if the latter exists).
This postfix iteration is equivalent to iterating through bags numbered 0,1,2,...; that is, following the order of NTreeBag::index().
null
if there are no bags (which means the underlying graph G is empty).
|
inline |
Used for a prefix iteration through all of the bags in the tree decomposition.
Amongst other things, a prefix iteration is one in which each bag will be processed before any of its children.
If d is a non-empty tree decomposition, then you can complete a full prefix iteration of bags as follows:
d.firstPrefix()
;b.nextPrefix()
;b.nextPrefix()
is null
.This iteration processes the children of each bag in order; that is, it processes each bag b before b.sibling()
(if the latter exists).
Since the first bag in a prefix iteration must be the root bag, this function is identical to calling root().
null
if there are no bags (which means the underlying graph G is empty). void regina::NTreeDecomposition::makeNice | ( | ) |
Converts this into a nice tree decomposition.
A nice tree decomposition is one in which every bag is one of the following types:
As a special case, each leaf bag (which has no child bags at all) is also considered to be an introduce bag, and will contain exactly one node.
This routine will also ensure that the root bag is a forget bag, containing no nodes at all.
This routine will set NTreeBag::type() and NTreeBag::subtype() for each bag as follows:
b.element(b.subtype())
.b.children()->element(b.subtype())
.If the underlying graph is empty, then this routine will produce a tree decomposition with no bags at all.
|
inline |
Returns the bag at the root of the underlying tree.
null
if there are no bags (which means the underlying graph G is empty).
|
inline |
Returns the number of bags in this tree decomposition.
|
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 |
A deprecated alias for str().
|
inherited |
A deprecated alias for detail().
|
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.
|
inline |
Returns the width of this tree decomposition.
This is one less than the size of the largest bag.
void regina::NTreeDecomposition::writeDot | ( | std::ostream & | out | ) | const |
Outputs this tree decomposition in the Graphviz DOT language.
This produces a standalone DOT file that can be run through Graphviz in order to visualise the tree decomposition.
This routine generates a directed graph (with arrows running from parent bags to their children). The nodes of this graph will be labelled in a way that indicates the tetrahedra contained in each bag. The resulting DOT file should be used with the dot program shipped with Graphviz.
out | the output stream to which to write. |
void regina::NTreeDecomposition::writeTextLong | ( | std::ostream & | out | ) | const |
Writes a detailed text representation of this object to the given output stream.
out | the output stream to which to write. |
void regina::NTreeDecomposition::writeTextShort | ( | std::ostream & | out | ) | const |
Writes a short text representation of this object to the given output stream.
out | the output stream to which to write. |