Represents a single bag in a tree decomposition. More...
#include <treewidth/treedecomposition.h>
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... | |
| TreeBag & | operator= (const TreeBag &)=delete |
| 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).
Member Function Documentation
◆ writeTextLong()
|
inlineinherited |
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.
The documentation for this class was generated from the following file:
- treewidth/treedecomposition.h