Treewidth

Treewidth and tree decompositions. More...

Classes
class	regina::TreeBag
	Represents a single bag in a tree decomposition. More...
class	regina::TreeDecomposition
	Represents a tree decomposition of a graph. More...

Enumerations
enum class	regina::TreeDecompositionAlg { regina::TreeDecompositionAlg::Upper = 0x0001 , regina::TreeDecompositionAlg::UpperGreedyFillIn = 0x0001 }
	Indicates which algorithm should be used to compute a tree decomposition of a graph. More...
enum class	regina::BagComparison { regina::BagComparison::Equal = 0 , regina::BagComparison::Subset = -1 , regina::BagComparison::Superset = 1 , regina::BagComparison::Unrelated = 2 }
	Indicates the relationship between two bags in a tree decomposition. More...
enum class	regina::NiceType { regina::NiceType::None = 0 , regina::NiceType::Introduce = 1 , regina::NiceType::Forget = 2 , regina::NiceType::Join = 3 }
	Used to indicate the type of each bag in a nice tree decomposition. More...

Functions
void	regina::swap (TreeDecomposition &a, TreeDecomposition &b) noexcept
	Swaps the contents of the two given tree decompositions.

Detailed Description

Treewidth and tree decompositions.

Enumeration Type Documentation

BagComparison

enum class regina::BagComparison

strong

Indicates the relationship between two bags in a tree decomposition.

Enumerator
Equal	Indicates that the two bags have identical contents.
Subset	Indicates that the first bag is a strict subset of the second.
Superset	Indicates that the first bag is a strict superset of the second.
Unrelated	Indicates that neither bag is a subset of the other.

NiceType

enum class regina::NiceType

strong

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, and see TreeBag::niceType() and TreeBag::niceIndex() for how to access this information for each bag.

Enumerator
None	Indicates that either the underlying tree decomposition is not nice, or the details of the nice tree decomposition have not yet been computed.
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.
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.
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

enum class regina::TreeDecompositionAlg

strong

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
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 TreeDecompositionAlg::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.
UpperGreedyFillIn	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

swap()

void regina::swap ( TreeDecomposition & a, TreeDecomposition & b )

inlinenoexcept

Swaps the contents of the two given tree decompositions.

This global routine simply calls TreeDecomposition::swap(); it is provided so that TreeDecomposition meets the C++ Swappable requirements.

Parameters

a	the first tree decomposition whose contents should be swapped.
b	the second tree decomposition whose contents should be swapped.