Represents a single bag in a tree decomposition. More...

#include <treewidth/treedecomposition.h>

Inheritance diagram for regina::TreeBag:

Public Member Functions
	~TreeBag ()
	Destroys this bag.

size_t	size () const
	Returns the number of graph nodes stored in this bag.

size_t	element (size_t which) const
	Used to query the individual graph nodes stored in this bag.

bool	contains (size_t element) const
	Queries whether a given graph node is contained in this bag.

size_t	index () const
	Returns the index of this bag within the full tree decomposition.

NiceType	niceType () const
	Returns the role that this bag plays in a nice tree decomposition, if this information is known.

int	type () const
	Deprecated function that returns the role that this bag plays in a nice tree decomposition, if this information is known.

ssize_t	niceIndex () const
	Returns additional details on the role that an introduce or forget bag plays in a nice tree decomposition.

ssize_t	subtype () const
	Deprecated function that returns additional details on the role that an introduce or forget bag plays in a nice tree decomposition.

BagComparison	compare (const TreeBag &rhs) const
	Determines if there is a subset/superset relationship between this and the given bag.

const TreeBag *	next () const
	Used for a postfix iteration through all of the bags in a tree decomposition.

const TreeBag *	nextPrefix () const
	Used for a prefix iteration through all of the bags in a tree decomposition.

const TreeBag *	parent () const
	Returns the parent of this bag in the underlying rooted tree.

const TreeBag *	children () const
	Returns the first child of this bag in the underlying rooted tree.

const TreeBag *	sibling () const
	Returns the next sibling of this bag in the underlying rooted tree.

bool	isLeaf () const
	Determines if this is a leaf bag.

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream.

TreeBag &	operator= (const TreeBag &)=delete

void	writeTextLong (std::ostream &out) const
	A default implementation for detailed output.

std::string	str () const
	Returns a short text representation of this object.

std::string	utf8 () const
	Returns a short text representation of this object using unicode characters.

std::string	detail () const
	Returns a detailed text representation of this object.

Friends
class	TreeDecomposition

Detailed Description

Represents a single bag in a tree decomposition.

The class TreeDecomposition is used to build, manipulate and iterate over tree decompositions of graphs. A tree decomposition of a graph 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 various constraints as described in the TreeDecomposition class notes.

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

This class TreeBag represents a single bag in a tree decomposition.

You can query which nodes of G the bag contains through the member functions size(), element() and contains(). It is assumed that the nodes of G are numbered 0,1,2,..., and so the nodes stored in this bag are simply represented as integers.
You can query the location of the bag in the underlying tree T through the member functions parent(), children(), sibling() and isLeaf().
You can iterate through all the bags in the tree decomposition with the help of member functions next(), nextPrefix() and index().
If the underlying tree decomposition is a nice tree decomposition (and this nice structure has actually been computed, typically via makeNice()), then you can call niceType() and niceIndex() to access the specific role that each bag plays in the nice structure.

To build a tree decomposition of a graph, see the various TreeDecomposition class constructors.

Note that a bag may be empty (indeed, if you call TreeDecomposition::makeNice() then it is guaranteed that the root bag will be empty).

Tree bags do not support value semantics: they cannot be copied, swapped, or manually constructed. Their location in memory defines them, and they are often passed and compared by pointer. End users are never responsible for their memory management; this is all taken care of by the TreeDecomposition to which they belong.

Constructor & Destructor Documentation

◆ ~TreeBag()

regina::TreeBag::~TreeBag ( )

inline

Destroys this bag.

Member Function Documentation

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

BagComparison::Equal if this and rhs are equal;
BagComparison::Subset if this bag is a strict subset of rhs;
BagComparison::Superset if this bag is a strict superset of rhs;
BagComparison::Unrelated if neither this nor rhs is a subset of the other.

Parameters

rhs	the bag to compare with this.

Returns: the relationship between the two bags, as outlined above.

◆ contains()

bool regina::TreeBag::contains ( size_t 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

element the number of some node in the graph G.

Returns: true if and only if the given node is in this bag.

◆ detail()

std::string regina::Output< TreeBag, supportsUtf8 >::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.

◆ element()

size_t regina::TreeBag::element ( size_t 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

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

◆ index()

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

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

◆ niceIndex()

ssize_t regina::TreeBag::niceIndex ( ) const

inline

Returns additional details on the role that an introduce or forget bag plays in a nice tree decomposition.

This function is only relevant if niceType() returns either NiceType::Introduce or NiceType::Forget. That is, the underlying tree decomposition must be nice, and this nice structure must have actually been computed, and this bag must be an introduce bag or a forget bag.

In this case, niceIndex() gives information on which specific node of the underyling graph has been added (in the case of an introduce bag) or removed (in the case of a forget bag). This information will be returned as an index into either this bag or its child bag respectively.

See TreeDecomposition::makeNice() for further information.

Returns: details on the role that an introduce or forget bag plays in a nice tree decomposition, or undefined if this information is unknown and/or irrelevant (i.e., niceType() does not return either NiceType::Introduce or NiceType::Forget).

◆ niceType()

NiceType regina::TreeBag::niceType ( ) const

inline

Returns the role that this bag plays in a nice tree decomposition, if this information is known.

This information is only available if the underlying tree decomposition is nice and this nice structure has actually been computed. For this to happen, either:

TreeDecomposition::makeNice() must have been called upon this tree decomposition; or
this tree decomposition must have been copied, moved or assigned from some other nice tree decomposition for which this information had likewise been computed.

For introduce and forget bags (i.e., where niceType() returns either NiceType::Introduce or NiceType::Forget), the function niceIndex() returns additional information on the role that this bag plays within the overall nice tree decomposition.

See TreeDecomposition::makeNice() for further information.

Returns: the role that this bag plays in a nice tree decomposition, or NiceType::None if this information is not available (either because the tree decomposition is not nice, or because its nice structure has not been computed).

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

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

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

◆ str()

std::string regina::Output< TreeBag, supportsUtf8 >::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.

◆ subtype()

ssize_t regina::TreeBag::subtype ( ) const

inline

Deprecated function that returns additional details on the role that an introduce or forget bag plays in a nice tree decomposition.

Deprecated: This function has been renamed to niceIndex(). See niceIndex() for further details.

Returns: details on the role that an introduce or forget bag plays in a nice tree decomposition, or undefined if this information is unknown and/or irrelevant (i.e., niceType() does not return either NiceType::Introduce or NiceType::Forget).

◆ type()

int regina::TreeBag::type ( ) const

inline

Deprecated function that returns the role that this bag plays in a nice tree decomposition, if this information is known.

Deprecated: This function has been named to niceType(), which returns a properly-typed NiceType instead of an int. See niceType() for further details.

Python: For Python users, this function returns a NiceType, not an int, so that comparisons with the NiceType constants works as expected. This is because, now that NiceType is a scoped enum, Python comparisons between any integer and any NiceType constant will always return that the values are not equal.

Returns: the non-zero integer value of a NiceType constant indicating the role that this bag plays in a nice tree decomposition, or zero if this information is not available.

◆ utf8()

std::string regina::Output< TreeBag, supportsUtf8 >::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.

◆ writeTextLong()

void regina::ShortOutput< TreeBag, false >::writeTextLong ( std::ostream & out ) const

inlineinherited

A default implementation for detailed output.

This routine simply calls T::writeTextShort() and appends a final newline.

Python: Not present. Instead you can call detail() from the subclass T, which returns this output as a string.

Parameters

out	the output stream to which to write.

◆ writeTextShort()

void regina::TreeBag::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

Public Member Functions

Friends

Detailed Description

Constructor & Destructor Documentation

◆ ~TreeBag()

Member Function Documentation

◆ children()

◆ compare()

◆ contains()

◆ detail()

◆ element()

◆ index()

◆ isLeaf()

◆ next()

◆ nextPrefix()

◆ niceIndex()

◆ niceType()

◆ parent()

◆ sibling()

◆ size()

◆ str()

◆ subtype()

◆ type()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()