regina::TreeBag Class Reference
Treewidth

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. More...
int | size () const
| Returns the number of graph nodes stored in this bag. More...
int | element (int which) const
| Used to query the individual graph nodes stored in this bag. More...
bool | contains (int element) const
| Queries whether a given graph node is contained in this bag. More...
int | index () const
| Returns the index of this bag within the full tree decomposition. More...
int | type () const
| Returns auxiliary information associated with bags in special classes of tree decompositions. More...
int | subtype () const
| Returns a secondary level of auxiliary information associated with bags in special classes of tree decompositions. More...
BagComparison | compare (const TreeBag &rhs) const
| Determines if there is a subset/superset relationship between this and the given bag. More...
const TreeBag * | next () const
| Used for a postfix iteration through all of the bags in a tree decomposition. More...
const TreeBag * | nextPrefix () const
| Used for a prefix iteration through all of the bags in a tree decomposition. More...
const TreeBag * | parent () const
| Returns the parent of this bag in the underlying rooted tree. More...
const TreeBag * | children () const
| Returns the first child of this bag in the underlying rooted tree. More...
const TreeBag * | sibling () const
| Returns the next sibling of this bag in the underlying rooted tree. More...
bool | isLeaf () const
| Determines if this is a leaf bag. 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
| A default implementation for detailed output. 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...

## 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 tree decomposition is of a special type (such as a nice tree decomposition), then each bag may be adorned with some additional information; you can access this through the member functions type() and subtype().

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

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

- 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

  rhs | the bag to compare with this.

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

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

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

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

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

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 scheme. In other words, for any non-root bag b we have `b.index() < b.parent()->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.

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

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.

## 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 fit on a single line, and should not end with a newline. Where possible, it should use plain ASCII characters.

Python:
  In addition to str(), this is also used as the Python "stringification" function `__str__()`.

Returns
  a short text representation of this object.

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

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

## 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 fit on a single line, and should not end with a newline. In addition, it may use unicode characters to make the output more pleasant to read. This string 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

inline inherited

A default implementation for detailed output.

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

Python:
  Not present.

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.

Parameters

  out | the output stream to which to write.

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

- treewidth/treedecomposition.h

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