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	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
void	regina::swap (TreeDecomposition &a, TreeDecomposition &b) noexcept
	Swaps the contents of the two given tree decompositions. More...

Detailed Description

Treewidth and tree decompositions.

Enumeration Type Documentation

BagComparison

enum regina::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

enum regina::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

enum regina::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

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.