Regina Calculation Engine
Classes | 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

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 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...
 
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...
 

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 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.

Constructor & Destructor Documentation

◆ TreeDecomposition() [1/3]

template<int dim>
regina::TreeDecomposition::TreeDecomposition ( 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.

Headers:
This routine is implemented in a separate header (treedecomposition-impl.h), which is not included automatically by this file. However, typical end users should never need this extra header, since Regina's calculation engine already includes explicit instantiations for standard dimensions.
Python:
This constructor is only available in Python when dim is one of Regina's standard dimensions.
Parameters
triangulationthe triangulation whose facet pairing graph we are working with.
algthe 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.

◆ TreeDecomposition() [2/3]

template<int dim>
regina::TreeDecomposition::TreeDecomposition ( 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.

Headers:
This routine is implemented in a separate header (treedecomposition-impl.h), which is not included automatically by this file. However, typical end users should never need this extra header, since Regina's calculation engine already includes explicit instantiations for standard dimensions.
Python:
This constructor is only available in Python when dim is one of Regina's standard dimensions.
Parameters
pairingthe facet pairing graph that we are working with.
algthe 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.

◆ TreeDecomposition() [3/3]

template<typename T >
regina::TreeDecomposition::TreeDecomposition ( 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.

Headers:
This routine is implemented in a separate header (treedecomposition-impl.h), which is not included automatically by this file. Regina's calculation engine already includes explicit instantiations for types bool and int, but for other types you will need to include treedecomposition-impl.h along with this header.
Python:
The adjacency matrix should be given as a list of lists. There is no need to use the same data type T throughout: each element of the matrix will be individually interpreted as a boolean as described above.
Parameters
orderthe number of nodes in the graph.
graphthe adjacency matrix of the graph.
algthe 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.

◆ ~TreeDecomposition()

regina::TreeDecomposition::~TreeDecomposition ( )
inline

Destroys this tree decomposition and all of its bags.

Member Function Documentation

◆ compress()

bool regina::TreeDecomposition::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 TreeBag objects may be destroyed (thereby invalidating pointers or references to them), and for those bags that are not destroyed, their indices (as returned by TreeBag::index()) may change.

Returns
true if and only if the tree decomposition was changed.

◆ 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.

◆ dot()

std::string regina::TreeDecomposition::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.

Returns
the output of writeDot(), as outlined above.

◆ first()

const TreeBag* regina::TreeDecomposition::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:

  • the first bag in a postfix iteration is d.first();
  • the next bag after b in the iteration is b.next();
  • the iteration terminates when 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 TreeBag::index().

Returns
the first bag in a postfix iteration of all bags, or null if there are no bags (which means the underlying graph G is empty).

◆ firstPrefix()

const TreeBag * regina::TreeDecomposition::firstPrefix ( ) const
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:

  • the first bag in a prefix iteration is d.firstPrefix();
  • the next bag after b in the iteration is b.nextPrefix();
  • the iteration terminates when 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().

Returns
the first bag in a prefix iteration of all bags, or null if there are no bags (which means the underlying graph G is empty).

◆ makeNice()

void regina::TreeDecomposition::makeNice ( )

Converts this into a nice tree decomposition.

A nice tree decomposition is one in which every bag is one of the following types:

  • an introduce bag, which has only one child bag, and which contains all of the nodes in this child bag plus exactly one new node (and nothing else);
  • a forget bag, which has only one child bag, and which contains all of the nodes in this child bag except for exactly one missing node (and nothing else);
  • a join bag, which has exactly two child bags, and where each child bag contains exactly the same nodes as the join bag itself.

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 TreeBag::type() and TreeBag::subtype() for each bag as follows:

  • TreeBag::type() will be one of the constants from the NiceType enumeration, indicating whether the bag is an introduce, forget or join bag.
  • For an introduce bag b, TreeBag::subtype() will indicate which "new" node was introduced. Specifically, the new node will be b.element(b.subtype()).
  • For a forget bag b, TreeBag::subtype() will indicate which "missing" node was forgotten. Specifically, the missing node will be b.children()->element(b.subtype()).
  • For a join bag, TreeBag::subtype() will be undefined.

If the underlying graph is empty, then this routine will produce a tree decomposition with no bags at all.

Warning
Note that TreeBag::subtype() is not the number of the new or missing node, but instead gives the index of the new or missing node within the relevant bag.
Note
This routine calls compress() automatically, and so there is no need to explicitly call compress() before calling makeNice().

◆ root()

const TreeBag * regina::TreeDecomposition::root ( ) const
inline

Returns the bag at the root of the underlying tree.

Returns
the root bag, or null if there are no bags (which means the underlying graph G is empty).

◆ size()

int regina::TreeDecomposition::size ( ) const
inline

Returns the number of bags in this tree decomposition.

Returns
the number of bags.

◆ 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.

◆ width()

int regina::TreeDecomposition::width ( ) const
inline

Returns the width of this tree decomposition.

This is one less than the size of the largest bag.

Returns
the width of this tree decomposition.

◆ writeDot()

void regina::TreeDecomposition::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.

Python:
The out argument is not present; instead standard output is assumed.
Parameters
outthe output stream to which to write.
See also
http://www.graphviz.org/

◆ writeTextLong()

void regina::TreeDecomposition::writeTextLong ( std::ostream &  out) const

Writes a detailed text representation of this object to the given output stream.

Python:
Not present.
Parameters
outthe output stream to which to write.

◆ writeTextShort()

void regina::TreeDecomposition::writeTextShort ( std::ostream &  out) const

Writes a short text representation of this object to the given output stream.

Python:
Not present.
Parameters
outthe output stream to which to write.

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

Copyright © 1999-2016, 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).