Regina Calculation Engine
Classes | Typedefs | Enumerations | Enumerator | Functions | Variables | Friends
Treewidth

Treewidth and tree decompositions. More...

Classes

class  regina::TreeBag
 Represents a single bag in a tree decomposition. More...
 
struct  regina::TreeDecomposition::Graph
 Represents a graph, which may be directed or undirected. More...
 
class  regina::TreeDecomposition
 Represents a tree decomposition of a graph. More...
 

Typedefs

typedef TreeBag regina::NTreeBag
 Deprecated typedef for backward compatibility. More...
 
typedef TreeDecomposition regina::NTreeDecomposition
 Deprecated typedef for backward compatibility. More...
 

Enumerations

enum  regina::TreeDecompositionAlg { regina::TD_UPPER = 0x0001, regina::TD_UPPER_GREEDY_FILL_IN = 0x0001 }
 Indicates which algorithm should be used to compute a tree decomposition of a graph. More...
 
enum  regina::BagComparison { regina::BAG_EQUAL = 0, regina::BAG_SUBSET = -1, regina::BAG_SUPERSET = 1, regina::BAG_UNRELATED = 2 }
 Indicates the relationship between two bags in a tree decomposition. More...
 
enum  regina::NiceType { regina::NICE_INTRODUCE = 1, regina::NICE_FORGET = 2, regina::NICE_JOIN = 3 }
 Used to indicate the type of each bag in a nice tree decomposition. More...
 

Functions

 regina::TreeBag::~TreeBag ()
 Destroys this bag. More...
 
int regina::TreeBag::size () const
 Returns the number of graph nodes stored in this bag. More...
 
int regina::TreeBag::element (int which) const
 Used to query the individual graph nodes stored in this bag. More...
 
bool regina::TreeBag::contains (int element) const
 Queries whether a given graph node is contained in this bag. More...
 
int regina::TreeBag::index () const
 Returns the index of this bag within the full tree decomposition. More...
 
int regina::TreeBag::type () const
 Returns auxiliary information associated with bags in special classes of tree decompositions. More...
 
int regina::TreeBag::subtype () const
 Returns a secondary level of auxiliary information associated with bags in special classes of tree decompositions. More...
 
BagComparison regina::TreeBag::compare (const TreeBag &rhs) const
 Determines if there is a subset/superset relationship between this and the given bag. More...
 
const TreeBagregina::TreeBag::next () const
 Used for a postfix iteration through all of the bags in a tree decomposition. More...
 
const TreeBagregina::TreeBag::nextPrefix () const
 Used for a prefix iteration through all of the bags in a tree decomposition. More...
 
const TreeBagregina::TreeBag::parent () const
 Returns the parent of this bag in the underlying rooted tree. More...
 
const TreeBagregina::TreeBag::children () const
 Returns the first child of this bag in the underlying rooted tree. More...
 
const TreeBagregina::TreeBag::sibling () const
 Returns the next sibling of this bag in the underlying rooted tree. More...
 
bool regina::TreeBag::isLeaf () const
 Determines if this is a leaf bag. More...
 
void regina::TreeBag::writeTextShort (std::ostream &out) const
 Writes a short text representation of this object to the given output stream. More...
 
TreeBagregina::TreeBag::operator= (const TreeBag &)=delete
 
 regina::TreeDecomposition::Graph::Graph (int order)
 Constructs a new graph with no arcs. More...
 
 regina::TreeDecomposition::Graph::~Graph ()
 Destroys this graph. More...
 
void regina::TreeDecomposition::Graph::dump (std::ostream &out) const
 Writes the adjacency matrix of this graph in a compact format to the given output stream. More...
 
 regina::TreeDecomposition::Graph::Graph (const Graph &)=delete
 
Graphregina::TreeDecomposition::Graph::operator= (const Graph &)=delete
 
 regina::TreeDecomposition::TreeDecomposition (const TreeDecomposition &cloneMe)
 Builds a new copy of the given tree decomposition. More...
 
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. More...
 
template<int dim>
 regina::TreeDecomposition::TreeDecomposition (const FacetPairing< dim > &pairing, TreeDecompositionAlg alg=TD_UPPER)
 Builds a tree decomposition of the given facet pairing graph. More...
 
 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. More...
 
template<typename T >
 regina::TreeDecomposition::TreeDecomposition (unsigned order, T const **const graph, TreeDecompositionAlg alg=TD_UPPER)
 Builds a tree decomposition of an arbitrary graph. More...
 
 regina::TreeDecomposition::~TreeDecomposition ()
 Destroys this tree decomposition and all of its bags. More...
 
int regina::TreeDecomposition::width () const
 Returns the width of this tree decomposition. More...
 
int regina::TreeDecomposition::size () const
 Returns the number of bags in this tree decomposition. More...
 
const TreeBagregina::TreeDecomposition::root () const
 Returns the bag at the root of the underlying tree. More...
 
const TreeBagregina::TreeDecomposition::first () const
 Used for a postfix iteration through all of the bags in the tree decomposition. More...
 
const TreeBagregina::TreeDecomposition::firstPrefix () const
 Used for a prefix iteration through all of the bags in the tree decomposition. More...
 
const TreeBagregina::TreeDecomposition::bag (int index) const
 A slow (linear-time) routine that returns the bag at the given index. More...
 
bool regina::TreeDecomposition::compress ()
 Removes redundant bags from this tree decomposition. More...
 
void regina::TreeDecomposition::makeNice (int *heightHint=nullptr)
 Converts this into a nice tree decomposition. More...
 
void regina::TreeDecomposition::reroot (TreeBag *newRoot)
 Reverses child-parent relationships so that the given bag becomes the root of the tree decomposition. More...
 
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. More...
 
void regina::TreeDecomposition::writeDot (std::ostream &out) const
 Outputs this tree decomposition in the Graphviz DOT language. More...
 
std::string regina::TreeDecomposition::dot () const
 Returns a Graphviz DOT representation of this tree decomposition. More...
 
void regina::TreeDecomposition::writePACE (std::ostream &out) const
 Outputs this tree decomposition using the PACE text format. More...
 
std::string regina::TreeDecomposition::pace () const
 Returns a text representation of this tree decomposition using the PACE text format. More...
 
void regina::TreeDecomposition::writeTextShort (std::ostream &out) const
 Writes a short text representation of this object to the given output stream. More...
 
void regina::TreeDecomposition::writeTextLong (std::ostream &out) const
 Writes a detailed text representation of this object to the given output stream. More...
 
static TreeDecompositionregina::TreeDecomposition::fromPACE (const std::string &str)
 Builds a tree decomposition from a string using the PACE text format. More...
 
static TreeDecompositionregina::TreeDecomposition::fromPACE (std::istream &in)
 Builds a tree decomposition from an input stream using the PACE text format. More...
 
TreeDecompositionregina::TreeDecomposition::operator= (const TreeDecomposition &)=delete
 

Variables

int regina::TreeDecomposition::Graph::order_
 The number of nodes in the graph. More...
 
bool ** regina::TreeDecomposition::Graph::adj_
 The adjacency matrix for the graph. More...
 

Friends

class regina::TreeBag::TreeDecomposition
 

Detailed Description

Treewidth and tree decompositions.

Typedef Documentation

◆ NTreeBag

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NTreeBag has now been renamed to TreeBag.

◆ NTreeDecomposition

Deprecated typedef for backward compatibility.

This typedef will be removed in a future release of Regina.

Deprecated:
The class NTreeDecomposition has now been renamed to TreeDecomposition.

Enumeration Type Documentation

◆ BagComparison

Indicates the relationship between two bags in a tree decomposition.

Enumerator
BAG_EQUAL 

Indicates that the two bags have identical contents.

BAG_SUBSET 

Indicates that the first bag is a strict subset of the second.

BAG_SUPERSET 

Indicates that the first bag is a strict superset of the second.

BAG_UNRELATED 

Indicates that neither bag is a subset of the other.

◆ NiceType

Used to indicate the type of each bag in a nice tree decomposition.

A nice tree decomposition is produced by calling TreeDecomposition::makeNice(). As a result:

  • every bag will be either an introduce bag, a forget bag, or a join bag, as defined below;
  • the root bag will be a forget bag, and will be empty;
  • every leaf bag will be an introduce bag, containing precisely one node.

See TreeDecomposition::makeNice() for further details, including how TreeBag::type() and TreeBag::subtype() are defined for a nice tree decomposition.

Enumerator
NICE_INTRODUCE 

Indicates an introduce bag.

An introduce bag has only one child bag. It contains all of the nodes in this child bag plus exactly one new node, and contains no other nodes besides these.

As a special case, a leaf bag (which has no child bags at all) is also considered to be an introduce bag. In this case, the leaf bag contains exactly one node.

NICE_FORGET 

Indicates a forget bag.

A forget bag has only one child bag. It contains all of the nodes in this child bag except for exactly one missing node, and contains no other nodes besides these.

NICE_JOIN 

Indicates a join bag.

A join bag has exactly two child bags, where the join bag and both of its child bags are all identical.

◆ TreeDecompositionAlg

Indicates which algorithm should be used to compute a tree decomposition of a graph.

Additional algorithms may be added to this list in future versions of Regina.

Enumerator
TD_UPPER 

Indicates that a fast upper bound algorithm should be used.

This does not promise to find a tree decomposition of smallest possible width (an NP-hard problem), but it does promise to run in small polynomial time.

This constant TD_UPPER indicates that the "most appropriate" upper bound algorithm should be used. This is a good choice for users who just want a good tree decomposition and want it quickly, without needing to know the details of how it was produced.

TD_UPPER_GREEDY_FILL_IN 

Indicates that the greedy fill-in heuristic should be used.

This does not promise to find a tree decomposition of smallest possible width (an NP-hard problem), but it does promise to run in small polynomial time.

The greedy fill-in heuristic has been found experimentally to perform well on general graphs (T. van Dijk, J.-P. van den Heuvel and W. Slob, "Computing treewidth with LibTW", www.treewidth.com, 2006). Experimentation within Regina also suggests that it performs well in the setting of face pairing graphs of 3-manifold triangulations.

Function Documentation

◆ bag()

const TreeBag* regina::TreeDecomposition::bag ( int  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
indexthe number of a bag; this must be between 0 and size()-1 inclusive.
Returns
the bag with the given number.

◆ children()

const TreeBag * regina::TreeBag::children ( ) const
inline

Returns the first child of this bag in the underlying rooted tree.

If a bag has no children, then children() will be null. If a bag has many children, then these will be children(), children()->sibling(), children()->sibling()->sibling(), and so on.

Returns
the first child of this bag, or null if this is a leaf bag (i.e., it has no children).

◆ compare()

BagComparison regina::TreeBag::compare ( const TreeBag rhs) const

Determines if there is a subset/superset relationship between this and the given bag.

Recall that, in a tree decomposition of a graph G, each bag is a set of nodes of G. This function will return one of the following constants:

  • BAG_EQUAL if this and rhs are equal;
  • BAG_SUBSET if this bag is a strict subset of rhs;
  • BAG_SUPERSET if this bag is a strict superset of rhs;
  • BAG_UNRELATED if neither this nor rhs is a subset of the other.
Parameters
rhsthe bag to compare with this.
Returns
the relationship between the two bags, as outlined above.

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

◆ contains()

bool regina::TreeBag::contains ( int  element) const

Queries whether a given graph node is contained in this bag.

Suppose this is a bag in a tree decomposition of some graph G, whose nodes are numbered 0,1,2,.... Then contains(x) queries whether the node numbered x is contained in this bag.

Parameters
elementthe number of some node in the graph G.
Returns
true if and only if the given node is in this bag.

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

◆ dump()

void regina::TreeDecomposition::Graph::dump ( std::ostream &  out) const

Writes the adjacency matrix of this graph in a compact format to the given output stream.

The output will be formatted as a matrix, and will be spread across multiple lines.

Parameters
outthe output stream to which to write.

◆ element()

int regina::TreeBag::element ( int  which) const
inline

Used to query the individual graph nodes stored in this bag.

Suppose this is a bag in a tree decomposition of some graph G, whose nodes are numbered 0,1,2,.... Then element(i) returns the number of the ith node stored in this bag.

Nodes are always stored in ascending order. This means that element(0) < element(1) < element(2) < ....

Parameters
whichindicates which node should be returned; this must be between 0 and size()-1 inclusive.
Returns
the number of the corresponding node stored in this bag.

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

This routine does some basic error checking as it reads the input, but this checking is not exhaustive; in particular, it does not verify that the connections between bags actually form a tree.

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.

Parameters
stra text representation of the tree decomposition using the PACE text format.
Returns
a newly constructed tree decomposition, or null if the input was found to be invalid.
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 constructor TreeDecomposition(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).

Python:\n Not present.
Parameters
paceFormatan input stream that provides a text representation of the tree decomposition using the PACE text format.
Returns
a newly constructed tree decomposition, or null if the input was found to be invalid.
See also
https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/

◆ Graph()

regina::TreeDecomposition::Graph::Graph ( int  order)
inline

Constructs a new graph with no arcs.

Parameters
orderthe number of nodes in the new graph.

◆ index()

int regina::TreeBag::index ( ) const
inline

Returns the index of this bag within the full tree decomposition.

Suppose the entire tree decomposition contains n bags. Then these bags are automatically numbered 0,1,...,n-1. This member function returns the number of this particular bag.

The numbering of bags follows a leaves-to-root, left-to-right scheme:

  • for any non-root bag b, we have b.index() < b.parent()->index();
  • for any bag b with a next sibling, we have b.index() < b.sibling()->index();
Returns
the index of this bag within the full tree decomposition d; this will be between 0 and d.size()-1 inclusive.

◆ isLeaf()

bool regina::TreeBag::isLeaf ( ) const
inline

Determines if this is a leaf bag.

A leaf bag is a bag with no children in the underlying tree.

This is equivalent to testing whether children() is null.

Returns
true if and only if this is a leaf bag.

◆ makeNice()

void regina::TreeDecomposition::makeNice ( 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:\n The heightHint argument is not present.
Parameters
heightHintan 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.

◆ next()

const TreeBag* regina::TreeBag::next ( ) const

Used for a postfix iteration through all of the bags in a 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).

The bags in a tree decomposition are indexed as 0,1,2,..., as described by the index() member function. This postfix iteration is equivalent to iterating through bags 0,1,2,... in order.

Returns
the next bag after this in a postfix iteration of all bags, or null if this is the final bag in such an iteration (i.e., the root bag).

◆ nextPrefix()

const TreeBag* regina::TreeBag::nextPrefix ( ) const

Used for a prefix iteration through all of the bags in a 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() (or equivalently, d.root());
  • 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).

Returns
the next bag after this in a prefix iteration of all bags, or null if this is the final bag in such an iteration.

◆ pace()

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

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

The 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&).

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

See the writePACE() notes for further details.

Returns
the output of writePACE(), as outlined above.
See also
https://pacechallenge.wordpress.com/pace-2016/track-a-treewidth/

◆ parent()

const TreeBag * regina::TreeBag::parent ( ) const
inline

Returns the parent of this bag in the underlying rooted tree.

Returns
the parent of this bag, or null if this bag is at the root of the tree.

◆ 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:\n 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:\n Not present.
Template Parameters
Tthe 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
costSameAn array of size() elements giving an estimated cost of preserving each child-parent connection;
costReverseAn array of size() elements giving an estimated cost of reversing each child-parent connection;
costRootAn 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
newRootthe 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).

◆ sibling()

const TreeBag * regina::TreeBag::sibling ( ) const
inline

Returns the next sibling of this bag in the underlying rooted tree.

Specifically, if the parent of this bag has many children, then sibling() will return the next child after this.

More generally, all of the children of a bag b can be accessed as b.children(), b.children()->sibling(), b.children()->sibling()->sibling(), and so on.

Returns
the next sibling of this bag, or null if either (i) this is the final child of the parent bag, or (ii) this is the root bag.

◆ size() [1/2]

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

Returns the number of graph nodes stored in this bag.

Suppose this is a bag in a tree decomposition of some graph G. Then each bag is a subset of the nodes of G, and this function simply returns the size of this subset.

Returns
the number of graph nodes in this bag.

◆ size() [2/2]

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

Returns the number of bags in this tree decomposition.

Returns
the number of bags.

◆ subtype()

int regina::TreeBag::subtype ( ) const
inline

Returns a secondary level of auxiliary information associated with bags in special classes of tree decompositions.

If the underlying tree decomposition is of a special type, then each bag may be adorned with some additional information indicating the particular role that the bag plays. This additional information can be accessed through the member functions type() and subtype().

  • If there is no type and/or subtype information stored for this bag, then type() will return zero, and subtype() will be undefined.
  • If there is type and/or subtype information stored for this bag, then type() will be non-zero, and the specific meaning of subtype() (and indeed whether it is even defined) will depend on the value of type().

At present, types and subtypes are only stored for nice tree decompositions. See TreeDecomposition::makeNice() for details on what type() and subtype() represent.

Returns
additional information indicating the role that this bag plays in this tree decomposition, or undefined if no additional subtype information is stored for this bag.

◆ TreeDecomposition() [1/5]

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:\n 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:\n 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() [2/5]

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
linkthe knot or link 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/5]

regina::TreeDecomposition::TreeDecomposition ( const TreeDecomposition cloneMe)

Builds a new copy of the given tree decomposition.

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

Parameters
cloneMethe tree decomposition to clone.

◆ TreeDecomposition() [4/5]

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:\n 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:\n 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() [5/5]

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:\n 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:\n The argument order is not present (it will be
deduced automatically from graph). 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.

◆ type()

int regina::TreeBag::type ( ) const
inline

Returns auxiliary information associated with bags in special classes of tree decompositions.

If the underlying tree decomposition is of a special type, then each bag may be adorned with some additional information indicating the particular role that the bag plays. This additional information can be accessed through the member functions type() and subtype().

  • If there is no type and/or subtype information stored for this bag, then type() will return zero, and subtype() will be undefined.
  • If there is type and/or subtype information stored for this bag, then the return value of type() is guaranteed to be non-zero. The specific meaning of subtype() (and indeed whether it is even defined) will typically depend on the return value of type().

At present, types and subtypes are only stored for nice tree decompositions. See TreeDecomposition::makeNice() for details on what type() and subtype() represent.

Returns
a non-zero value indicating the role that this bag plays in this tree decomposition, or zero if type and subtype information are not stored.

◆ 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:\n 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/

◆ writePACE()

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

Outputs this tree decomposition using the PACE text format.

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

Python:\n The out argument is not present; instead
standard output is assumed.
Parameters
outthe 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:\n Not present.
Parameters
outthe output stream to which to write.

◆ writeTextShort() [1/2]

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

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

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

◆ writeTextShort() [2/2]

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

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

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

◆ ~Graph()

regina::TreeDecomposition::Graph::~Graph ( )
inline

Destroys this graph.

◆ ~TreeBag()

regina::TreeBag::~TreeBag ( )
inline

Destroys this bag.

◆ ~TreeDecomposition()

regina::TreeDecomposition::~TreeDecomposition ( )
inline

Destroys this tree decomposition and all of its bags.

Variable Documentation

◆ adj_

bool** regina::TreeDecomposition::Graph::adj_

The adjacency matrix for the graph.

Specifically, adj_[i][j] is true if and only if there is an arc from node i to node j.

◆ order_

int regina::TreeDecomposition::Graph::order_

The number of nodes in the graph.


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