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

#include <treewidth/treedecomposition.h>

Inheritance diagram for regina::TreeDecomposition:

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

Public Member Functions
	TreeDecomposition (const TreeDecomposition &src)
	Builds a new copy of the given tree decomposition. More...

	TreeDecomposition (TreeDecomposition &&src) noexcept
	Moves the contents of the given tree decomposition into this new 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 (const Matrix< T > &graph, TreeDecompositionAlg alg=TD_UPPER)
	Builds a tree decomposition of an arbitrary graph. More...

template<typename Row >
	TreeDecomposition (const std::vector< Row > &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...

TreeDecomposition &	operator= (const TreeDecomposition &src)
	Sets this to be a copy of the given tree decomposition. More...

TreeDecomposition &	operator= (TreeDecomposition &&src) noexcept
	Moves the contents of the given tree decomposition into this tree decomposition. More...

void	swap (TreeDecomposition &other) noexcept
	Swaps the contents of this and the given tree decomposition. More...

ssize_t	width () const
	Returns the width of this tree decomposition. More...

size_t	size () const
	Returns the number of bags in this tree decomposition. More...

bool	operator== (const TreeDecomposition &other) const
	Determines whether this and the given tree decomposition are identical. More...

bool	operator!= (const TreeDecomposition &other) const
	Determines whether this and the given tree decomposition are different. 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 (size_t 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 (const 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...

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

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:

Every node of G belongs to some bag;
Every arc of G has both its endpoints in some common bag;
For every node v of G, the set of all bags containing v forms a (connected) subtree of T.

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.

You can build a tree decomposition using the various TreeDecomposition constructors, and manipulate it using member functions such as compress() and makeNice().
To iterate through the bags of the tree decomposition, you can use TreeDecomposition::first() and TreeBag::next() (for a postfix iteration), or you can use TreeDecomposition::firstPrefix() and TreeBag::nextPrefix() (for a prefix iteration).

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:

for each non-root bag b, the parent of b will have a higher index than b;
for each bag b with a next sibling, the next sibling of b will have a higher index than b.

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.

This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.

Constructor & Destructor Documentation

◆ TreeDecomposition() [1/7]

regina::TreeDecomposition::TreeDecomposition ( const TreeDecomposition & src )

Builds a new copy of the given tree decomposition.

This will be a deep copy, in the sense that all of the bags of src will be cloned also.

Parameters

src	the tree decomposition to clone.

◆ TreeDecomposition() [2/7]

regina::TreeDecomposition::TreeDecomposition ( TreeDecomposition && src )

inlinenoexcept

Moves the contents of the given tree decomposition into this new tree decomposition.

This is a fast (constant time) operation.

The tree decomposition that was passed (src) will no longer be usable.

Parameters

src	the tree decomposition to move.

◆ TreeDecomposition() [3/7]

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

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.

◆ TreeDecomposition() [4/7]

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

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.

◆ TreeDecomposition() [5/7]

regina::TreeDecomposition::TreeDecomposition	(	const Link &	link,
		TreeDecompositionAlg	alg = `TD_UPPER`
	)

Builds a tree decomposition of the planar multigraph corresponding to the given knot or link diagram.

The nodes of the graph will be numbered in the same way as the crossings of the given knot / link.

Parameters

link	the knot or link 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.

◆ TreeDecomposition() [6/7]

template<typename T >

regina::TreeDecomposition::TreeDecomposition	(	const Matrix< T > &	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, expressed using Regina's own matrix type.

Each entry graph[i][j] will be treated as a boolean, indicating whether the graph contains an arc from node i to node j.

Exceptions

InvalidArgument The adjacency matrix does not have the same number of rows as columns.

Python: The argument graph must be of type MatrixBool (which is the Python type corresponding to the C++ class Matrix<bool>).

Parameters

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.

◆ TreeDecomposition() [7/7]

template<typename Row >

regina::TreeDecomposition::TreeDecomposition	(	const std::vector< Row > &	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, given as a vector of rows:

The number of elements in each row should be equal to the number of rows (i.e., the adjacency matrix should be square).
The individual elements of each row r should be accessible using a range-based for loop over r.
Each entry in row i, column j will be treated as a boolean, indicating whether the graph contains an arc from node i to node j.

An example of a suitable type for the adjacency matrix could be std::vector<std::vector<bool>>.

Exceptions

InvalidArgument The adjacency matrix does not have the same number of rows as columns.

Python: The adjacency matrix should be given as a list of lists.

Parameters

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.

◆ ~TreeDecomposition()

regina::TreeDecomposition::~TreeDecomposition ( )

inline

Destroys this tree decomposition and all of its bags.

Member Function Documentation

◆ bag()

const TreeBag * regina::TreeDecomposition::bag ( size_t index ) const

A slow (linear-time) routine that returns the bag at the given index.

Recall that the bags in a tree decomposition are numbered 0,1,...,size()-1. This routine returns the bag with the given number.

This routine is linear-time, and so you should not use it to iterate through all bags. Instead, to iterate through all bags, use TreeDecomposition::first() and TreeBag::next().

Warning: This routine is slow, with a worst-case linear time. This is because the bags are not stored internally in an array, and so this routine must search the tree from the root downwards to find the bag that is being requested.

Parameters

index the number of a bag; this must be between 0 and size()-1 inclusive.

Returns: the bag with the given number.

◆ 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 string can be saved as a standalone DOT file, which in turn 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.

This routine simply returns the output of writeDot() as a string, instead of dumping it to an output stream.

If you are writing this text representation to an output stream then you should call writeDot() instead, which is more efficient.

Returns: the DOT representation of this tree decomposition, 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).

◆ fromPACE() [1/2]

static TreeDecomposition regina::TreeDecomposition::fromPACE ( const std::string & str )

static

Builds a tree decomposition from a string using the PACE text format.

The text format is described in detail at https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/ .

In short, the format contains a number of lines of text:

Any line beginning with c is considered a comment, and will be ignored.
The first non-comment line should be of the form s td <num_bags> <max_bag_size> <num_vertices>.
The next num_bags non-comment lines should describe the contents of the bags. Each such line should be of the form b <bag_number> <element> <element> .... The bags are numbered 1,2,...,num_bags, and may appear in any order. Likewise, the vertices of the graph are numbered 1,2,...,num_vertices, and within each bag they may again appear in any order.
The remaining num_bags - 1 non-comment lines should indicate the connections between the bags in the tree decomposition. Each such line should be of the form <first_bag_index> <second_bag_index>, where first_bag_index is smaller than second_bag_index.

Bags may be empty, but there must be at least one bag, and the connections between the bags must form a tree. This routine will choose the root of the tree arbitrarily.

An example of this text format is as follows:

c A tree decomposition with 4 bags and width 2
s td 4 3 5
b 1 1 2 3
b 2 2 3 4
b 3 3 4 5
b 4
1 2
2 3
2 4

There are two variants of this routine. This variant contains a single string containing the entire text representation. The other variant takes an input stream, from which the text representation will be read.

Warning: While this routine does some basic error checking on the input, this checking is not exhaustive; in particular, it does not verify that the connections between bags actually form a tree.

Exceptions

InvalidArgument The input was not a valid representation of a tree decomposition using the PACE text format. As noted above, the checks performed here are not exhaustive.

Parameters

str	a text representation of the tree decomposition using the PACE text format.

Returns: the corresponding tree decomposition.

See also: https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/

◆ fromPACE() [2/2]

static TreeDecomposition regina::TreeDecomposition::fromPACE ( std::istream & in )

static

Builds a tree decomposition from an input stream using the PACE text format.

The text format is described in detail at https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/ .

See the routine fromPACE(const std::string&) for a description of this text format.

There are two variants of this routine. The other variant contains a single string containing the entire text representation. This variant takes an input stream, from which the text representation will be read.

This routine assumes that it should exhaust the input stream (i.e., it should contain no additional text after this text representation).

Exceptions

InvalidArgument The input was not a valid representation of a tree decomposition using the PACE text format. As documented more thoroughly in the string variant of this routine, the checks performed here are not exhaustive.

Python: Not present. Instead you can use the variant of fromPACE() that takes a string.

Parameters

in	an input stream that provides a text representation of the tree decomposition using the PACE text format.

Returns: the corresponding tree decomposition.

See also: https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/

◆ makeNice()

void regina::TreeDecomposition::makeNice ( const int * heightHint = nullptr )

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.

You may optionally pass an argument heightHint, which is an array indicating how close to the root of the tree you would like each node to be. At present, this only affects the final chain of forget bags leading up to the root bag - if heightHint is passed, then this chain will be ordered so that nodes with a larger heightHint will be forgotten closer to the root bag. These should be considered hints only, in that their effect on the final tree decomposition might change in future versions of Regina.

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

Python: If a heightHint argument is given, it should be passed as a Python list of integers.

Parameters

heightHint an optional array where, for each node i, a higher value of heightHint[i] indicates that the node should be forgotten closer to the root bag. If this is non-null, then the size of this array should be the number of nodes in the underlying graph.

◆ operator!=()

bool regina::TreeDecomposition::operator!= ( const TreeDecomposition & other ) const

inline

Determines whether this and the given tree decomposition are different.

To be considered identical (i.e., for this comparison to return false), the two tree decompositions must have the same number of bags; moreover, the same numbered bags must contain the same elements (i.e., numbered graph nodes), and must have the same numbered child bags. Bag types and subtypes are ignored.

Parameters

other the tree decomposition to compare with this.

Returns: true if and only if this and the given tree decomposition are different.

◆ operator=() [1/2]

TreeDecomposition & regina::TreeDecomposition::operator= ( const TreeDecomposition & src )

inline

Sets this to be a copy of the given tree decomposition.

This will be a deep copy, in the sense that all of the bags of src will be copied also.

It does not matter if this and the given tree decomposition were originally built from different and/or differently sized objects or graphs.

Parameters

src	the tree decomposition to copy.

Returns: a reference to this tree decomposition.

◆ operator=() [2/2]

TreeDecomposition & regina::TreeDecomposition::operator= ( TreeDecomposition && src )

inlinenoexcept

Moves the contents of the given tree decomposition into this tree decomposition.

This is a fast (constant time) operation.

The tree decomposition that was passed (src) will no longer be usable.

It does not matter if this and the given tree decomposition were originally built from different and/or differently sized objects or graphs.

Parameters

src	the tree decomposition to move.

Returns: a reference to this tree decomposition.

◆ operator==()

bool regina::TreeDecomposition::operator== ( const TreeDecomposition & other ) const

Determines whether this and the given tree decomposition are identical.

To be considered identical, the two tree decompositions must have the same number of bags; moreover, the same numbered bags must contain the same elements (i.e., numbered graph nodes), and must have the same numbered child bags. Bag types and subtypes are ignored.

Parameters

other the tree decomposition to compare with this.

Returns: true if and only if this and the given tree decomposition are identical.

◆ pace()

std::string regina::TreeDecomposition::pace ( ) const

Returns a text representation of this tree decomposition using the PACE text format.

This text format is described in detail at https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/ , and is documented in detail by the routine fromPACE(const std::string&).

If you write a tree decomposition using pace() or writePACE() and then read it again using fromPACE(), you are not guaranteed to obtain an identical tree decomposition. This is because the PACE text format stores the connections between bags as an undirected, unrooted tree.

If you are writing this text representation to an output stream then you should call writePACE() instead, which is more efficient.

Returns: the PACE text representation of this tree decomposition.

See also: https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/

◆ reroot() [1/2]

template<typename T >

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

The user needs to supply three arrays, which are used to estimate the cost of hanging the tree from any possible root. This routine then identifies which root minimises this cost, and reroots the underlying tree from that bag.

The three arrays play the following roles. Let b be some bag at index i in the original tree decomposition, and let p be its parent bag.

costSame[i] indicates the cost of preserving the parent-child relationship between b and p (i.e., after rerooting, p is still the parent bag of b). If b is the root bag of the original tree decomposition then costSame[i] is ignored.
costReverse[i] indicates the cost of reversing the parent-child relationship between b and p (i.e., after rerooting, b is now the parent bag of p). Again, if b is the root bag of the original tree decomposition then costReverse[i] is ignored.
costRoot[i] is an additional cost that is incurred if and only if b becomes the new root bag. The argument costRoot may be null, in which case these additional costs are all assumed to be zero.

It follows that, for each potential new root, there are size() costs to aggregate: this comes from size()-1 costs from the arrays costSame and/or costReverse (one for each connection between bags in the underlying tree), and one cost from costRoot. These costs will be aggregated by taking the maximum over all individual costs. This means that you do not need to estimate running times and/or memory consumption accurately; instead you only need to find some heuristic that aims to be monotonic in time and/or memory.

So: in essence then, this routine minimises the maximum cost. In the case of a tie, it then minimises multiplicity; that is, it minimises the number of times that this maximum cost occurs over the individual size() costs that are being aggregated.

Note that the costSame and costReverse arrays are technically defined as a cost per arc, not a cost per bag. If you wish to estimate a cost per bag, the typical way of doing this would be:

costSame[i] estimates the processing cost at bag i if its relationship with its parent is preserved;
costReverse[i] estimates the processing cost at the original parent of bag i if its relationship with bag i is reversed (i.e., it becomes a child of bag i);
costRoot[i] estimates the processing cost at bag i if bag i becomes the root.

This scheme ensures that, for any possible rerooting, each bag is costed exactly once amongst the three arrays.

After rerooting, all pointers to bags will remain valid, and the contents of the bags will not change. However:

the bags will be reindexed, to reflect the changes in the leaves-to-root, left-to-right ordering;
all bag types will be reset to 0, since in general rerooting may break whatever properties the bag types and subtypes represent.

If the given bag is already the root bag, then this routine does nothing (and in particular, types and subtypes are preserved).

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

Python: The costSame and costReverse arrays, as well as costRoot if it is given, should be passed as Python lists of real numbers.

Template Parameters

T	the type being used to estimate costs. It must be possible to assign 0 to a variable of type T using both constructors and the assignment operator.

Parameters

costSame	An array of size() elements giving an estimated cost of preserving each child-parent connection;
costReverse	An array of size() elements giving an estimated cost of reversing each child-parent connection;
costRoot	An array of size() elements giving an additional estimated cost for each bag being the new root. This array may be `null`.

◆ reroot() [2/2]

void regina::TreeDecomposition::reroot ( TreeBag * newRoot )

Reverses child-parent relationships so that the given bag becomes the root of the tree decomposition.

All pointers to bags will remain valid, and the contents of the bags will not change. However:

the bags will be reindexed, to reflect the changes in the leaves-to-root, left-to-right ordering;
all bag types will be reset to 0, since in general rerooting may break whatever properties the bag types and subtypes represent.

If the given bag is already the root bag, then this routine does nothing (and in particular, types and subtypes are preserved).

Parameters

newRoot the bag that should become the root of this tree decomposition. This must already be a bag of this tree decomposition.

◆ 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()

size_t 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 use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python __str__() and __repr__() functions.

Python: The Python "stringification" function __str__() will use precisely this function, and for most classes the Python __repr__() function will incorporate this into its output.

Returns: a short text representation of this object.

◆ swap()

void regina::TreeDecomposition::swap ( TreeDecomposition & other )

inlinenoexcept

Swaps the contents of this and the given tree decomposition.

Parameters

other the tree decomposition whose contents should be swapped with this.

◆ 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 not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.

Returns: a short text representation of this object.

◆ width()

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

Calling td.writeDot(out) is equivalent to out << td.dot(). However, this routine is more efficient.

Python: Not present. Instead use the variant dot() that takes no arguments and returns a string.

Parameters

out	the output stream to which to write.

See also: http://www.graphviz.org/

◆ writePACE()

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

Outputs this tree decomposition using the PACE text format.

This text format is described in detail at https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/ , and is documented in detail by the routine fromPACE(const std::string&).

If you write a tree decomposition using pace() or writePACE() and then read it again using fromPACE(), you are not guaranteed to obtain an identical tree decomposition. This is because the PACE text format stores the connections between bags as an undirected, unrooted tree.

Calling td.writePACE(out) is equivalent to out << td.pace(). However, this routine is more efficient.

Python: Not present. Instead use the variant pace() that takes no arguments and returns a string.

Parameters

out	the output stream to which to write.

See also: https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/

◆ 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. Use detail() instead.

Parameters

out	the 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. Use str() instead.

Parameters

out	the output stream to which to write.

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

treewidth/treedecomposition.h

Classes

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ TreeDecomposition() [1/7]

◆ TreeDecomposition() [2/7]

◆ TreeDecomposition() [3/7]

◆ TreeDecomposition() [4/7]

◆ TreeDecomposition() [5/7]

◆ TreeDecomposition() [6/7]

◆ TreeDecomposition() [7/7]

◆ ~TreeDecomposition()

Member Function Documentation

◆ bag()

◆ compress()

◆ detail()

◆ dot()

◆ first()

◆ firstPrefix()

◆ fromPACE() [1/2]

◆ fromPACE() [2/2]

◆ makeNice()

◆ operator!=()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator==()

◆ pace()

◆ reroot() [1/2]

◆ reroot() [2/2]

◆ root()

◆ size()

◆ str()

◆ swap()

◆ utf8()

◆ width()

◆ writeDot()

◆ writePACE()

◆ writeTextLong()

◆ writeTextShort()