Regina Calculation Engine
|
Classes | |
class | regina::TreeBag |
Represents a single bag in a tree decomposition. More... | |
struct | regina::TreeDecomposition::Graph |
Represents a graph, which may be directed or undirected. More... | |
class | regina::TreeDecomposition |
Represents a tree decomposition of a graph. More... | |
Typedefs | |
typedef TreeBag | regina::NTreeBag |
Deprecated typedef for backward compatibility. More... | |
typedef TreeDecomposition | regina::NTreeDecomposition |
Deprecated typedef for backward compatibility. 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 | |
regina::TreeBag::~TreeBag () | |
Destroys this bag. More... | |
int | regina::TreeBag::size () const |
Returns the number of graph nodes stored in this bag. More... | |
int | regina::TreeBag::element (int which) const |
Used to query the individual graph nodes stored in this bag. More... | |
bool | regina::TreeBag::contains (int element) const |
Queries whether a given graph node is contained in this bag. More... | |
int | regina::TreeBag::index () const |
Returns the index of this bag within the full tree decomposition. More... | |
int | regina::TreeBag::type () const |
Returns auxiliary information associated with bags in special classes of tree decompositions. More... | |
int | regina::TreeBag::subtype () const |
Returns a secondary level of auxiliary information associated with bags in special classes of tree decompositions. More... | |
BagComparison | regina::TreeBag::compare (const TreeBag &rhs) const |
Determines if there is a subset/superset relationship between this and the given bag. More... | |
const TreeBag * | regina::TreeBag::next () const |
Used for a postfix iteration through all of the bags in a tree decomposition. More... | |
const TreeBag * | regina::TreeBag::nextPrefix () const |
Used for a prefix iteration through all of the bags in a tree decomposition. More... | |
const TreeBag * | regina::TreeBag::parent () const |
Returns the parent of this bag in the underlying rooted tree. More... | |
const TreeBag * | regina::TreeBag::children () const |
Returns the first child of this bag in the underlying rooted tree. More... | |
const TreeBag * | regina::TreeBag::sibling () const |
Returns the next sibling of this bag in the underlying rooted tree. More... | |
bool | regina::TreeBag::isLeaf () const |
Determines if this is a leaf bag. More... | |
void | regina::TreeBag::writeTextShort (std::ostream &out) const |
Writes a short text representation of this object to the given output stream. More... | |
regina::TreeDecomposition::Graph::Graph (int order) | |
Constructs a new graph with no arcs. More... | |
regina::TreeDecomposition::Graph::~Graph () | |
Destroys this graph. More... | |
void | regina::TreeDecomposition::Graph::dump (std::ostream &out) const |
Writes the adjacency matrix of this graph in a compact format to the given output stream. More... | |
template<int dim> | |
regina::TreeDecomposition::TreeDecomposition (const Triangulation< dim > &triangulation, TreeDecompositionAlg alg=TD_UPPER) | |
Builds a tree decomposition of the facet pairing graph of the given triangulation. More... | |
template<int dim> | |
regina::TreeDecomposition::TreeDecomposition (const FacetPairing< dim > &pairing, TreeDecompositionAlg alg=TD_UPPER) | |
Builds a tree decomposition of the given facet pairing graph. More... | |
template<typename T > | |
regina::TreeDecomposition::TreeDecomposition (unsigned order, T const **const graph, TreeDecompositionAlg alg=TD_UPPER) | |
Builds a tree decomposition of an arbitrary graph. More... | |
regina::TreeDecomposition::~TreeDecomposition () | |
Destroys this tree decomposition and all of its bags. More... | |
int | regina::TreeDecomposition::width () const |
Returns the width of this tree decomposition. More... | |
int | regina::TreeDecomposition::size () const |
Returns the number of bags in this tree decomposition. More... | |
const TreeBag * | regina::TreeDecomposition::root () const |
Returns the bag at the root of the underlying tree. More... | |
const TreeBag * | regina::TreeDecomposition::first () const |
Used for a postfix iteration through all of the bags in the tree decomposition. More... | |
const TreeBag * | regina::TreeDecomposition::firstPrefix () const |
Used for a prefix iteration through all of the bags in the tree decomposition. More... | |
bool | regina::TreeDecomposition::compress () |
Removes redundant bags from this tree decomposition. More... | |
void | regina::TreeDecomposition::makeNice () |
Converts this into a nice tree decomposition. More... | |
void | regina::TreeDecomposition::writeDot (std::ostream &out) const |
Outputs this tree decomposition in the Graphviz DOT language. More... | |
std::string | regina::TreeDecomposition::dot () const |
Returns a Graphviz DOT representation of this tree decomposition. More... | |
void | regina::TreeDecomposition::writeTextShort (std::ostream &out) const |
Writes a short text representation of this object to the given output stream. More... | |
void | regina::TreeDecomposition::writeTextLong (std::ostream &out) const |
Writes a detailed text representation of this object to the given output stream. More... | |
Variables | |
int | regina::TreeDecomposition::Graph::order_ |
The number of nodes in the graph. More... | |
bool ** | regina::TreeDecomposition::Graph::adj_ |
The adjacency matrix for the graph. More... | |
Friends | |
class | regina::TreeBag::TreeDecomposition |
Treewidth and tree decompositions.
typedef TreeBag regina::NTreeBag |
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
Deprecated typedef for backward compatibility.
This typedef will be removed in a future release of Regina.
Indicates the relationship between two bags in a tree decomposition.
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:
See TreeDecomposition::makeNice() for further details, including how TreeBag::type() and TreeBag::subtype() are defined for a nice tree decomposition.
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.
|
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.
null
if this is a leaf bag (i.e., it has no children). 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:
rhs | the bag to compare with this. |
bool regina::TreeDecomposition::compress | ( | ) |
Removes redundant bags from this tree decomposition.
Specifically, this routine "compresses" the tree decomposition as follows: whenever two bags are adjacent in the underlying tree and one is a subset of the other, these bags will be merged.
Note that some TreeBag objects may be destroyed (thereby invalidating pointers or references to them), and for those bags that are not destroyed, their indices (as returned by TreeBag::index()) may change.
true
if and only if the tree decomposition was changed. 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.
element | the number of some node in the graph G. |
true
if and only if the given node is in this bag. std::string regina::TreeDecomposition::dot | ( | ) | const |
Returns a Graphviz DOT representation of this tree decomposition.
This routine simply returns the output of writeDot() as a string, instead of dumping it to an output stream.
See the writeDot() notes for further details.
void regina::TreeDecomposition::Graph::dump | ( | std::ostream & | out | ) | const |
Writes the adjacency matrix of this graph in a compact format to the given output stream.
The output will be formatted as a matrix, and will be spread across multiple lines.
out | the output stream to which to write. |
|
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) < ...
.
which | indicates which node should be returned; this must be between 0 and size()-1 inclusive. |
const TreeBag* regina::TreeDecomposition::first | ( | ) | const |
Used for a postfix iteration through all of the bags in the 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:
d.first()
;b.next()
;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).
This postfix iteration is equivalent to iterating through bags numbered 0,1,2,...; that is, following the order of TreeBag::index().
null
if there are no bags (which means the underlying graph G is empty).
|
inline |
Used for a prefix iteration through all of the bags in the 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:
d.firstPrefix()
;b.nextPrefix()
;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).
Since the first bag in a prefix iteration must be the root bag, this function is identical to calling root().
null
if there are no bags (which means the underlying graph G is empty).
|
inline |
Constructs a new graph with no arcs.
order | the number of nodes in the new graph. |
|
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()
.
d.size()-1
inclusive.
|
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
.
true
if and only if this is a leaf bag. void regina::TreeDecomposition::makeNice | ( | ) |
Converts this into a nice tree decomposition.
A nice tree decomposition is one in which every bag is one of the following types:
As a special case, each leaf bag (which has no child bags at all) is also considered to be an introduce bag, and will contain exactly one node.
This routine will also ensure that the root bag is a forget bag, containing no nodes at all.
This routine will set TreeBag::type() and TreeBag::subtype() for each bag as follows:
b.element(b.subtype())
.b.children()->element(b.subtype())
.If the underlying graph is empty, then this routine will produce a tree decomposition with no bags at all.
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:
d.first()
;b.next()
;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.
null
if this is the final bag in such an iteration (i.e., the root bag). 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:
d.firstPrefix()
(or equivalently, d.root()
);b.nextPrefix()
;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).
null
if this is the final bag in such an iteration.
|
inline |
Returns the parent of this bag in the underlying rooted tree.
null
if this bag is at the root of the tree.
|
inline |
Returns the bag at the root of the underlying tree.
null
if there are no bags (which means the underlying graph G is empty).
|
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.
null
if either (i) this is the final child of the parent bag, or (ii) this is the root bag.
|
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.
|
inline |
Returns the number of bags in this tree decomposition.
|
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().
At present, types and subtypes are only stored for nice tree decompositions. See TreeDecomposition::makeNice() for details on what type() and subtype() represent.
regina::TreeDecomposition::TreeDecomposition | ( | const FacetPairing< dim > & | pairing, |
TreeDecompositionAlg | alg = TD_UPPER |
||
) |
Builds a tree decomposition of the given facet pairing graph.
The nodes of the graph will be numbered in the same way as the top-dimensional simplices of the given triangulation.
pairing | the facet pairing graph that we are working with. |
alg | the algorithm that should be used to compute the tree decomposition; in particular, this specifies whether to use a slow exact algorithm or a fast greedy algorithm. |
regina::TreeDecomposition::TreeDecomposition | ( | const Triangulation< dim > & | triangulation, |
TreeDecompositionAlg | alg = TD_UPPER |
||
) |
Builds a tree decomposition of the facet pairing graph of the given triangulation.
The nodes of the graph will be numbered in the same way as the top-dimensional simplices of the given triangulation.
triangulation | the triangulation whose facet pairing graph we are working with. |
alg | the algorithm that should be used to compute the tree decomposition; in particular, this specifies whether to use a slow exact algorithm or a fast greedy algorithm. |
regina::TreeDecomposition::TreeDecomposition | ( | unsigned | order, |
T const **const | graph, | ||
TreeDecompositionAlg | alg = TD_UPPER |
||
) |
Builds a tree decomposition of an arbitrary graph.
The graph may be directed or undirected.
The graph is specified by an adjacency matrix. The matrix may contain any data type (this is the template argument T). However, the contents of this matrix will be interpreted as booleans: an arc runs from node i to node j if and only if graph[i][j] is true
when interpreted as a boolean.
bool
and int
, but for other types you will need to include treedecomposition-impl.h along with this header.order | the number of nodes in the graph. |
graph | the adjacency matrix of the graph. |
alg | the algorithm that should be used to compute the tree decomposition; in particular, this specifies whether to use a slow exact algorithm or a fast greedy algorithm. |
|
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().
At present, types and subtypes are only stored for nice tree decompositions. See TreeDecomposition::makeNice() for details on what type() and subtype() represent.
|
inline |
Returns the width of this tree decomposition.
This is one less than the size of the largest bag.
void regina::TreeDecomposition::writeDot | ( | std::ostream & | out | ) | const |
Outputs this tree decomposition in the Graphviz DOT language.
This produces a standalone DOT file that can be run through Graphviz in order to visualise the tree decomposition.
This routine generates a directed graph (with arrows running from parent bags to their children). The nodes of this graph will be labelled in a way that indicates the tetrahedra contained in each bag. The resulting DOT file should be used with the dot program shipped with Graphviz.
out | the output stream to which to write. |
void regina::TreeDecomposition::writeTextLong | ( | std::ostream & | out | ) | const |
Writes a detailed text representation of this object to the given output stream.
out | the output stream to which to write. |
void regina::TreeBag::writeTextShort | ( | std::ostream & | out | ) | const |
Writes a short text representation of this object to the given output stream.
out | the output stream to which to write. |
void regina::TreeDecomposition::writeTextShort | ( | std::ostream & | out | ) | const |
Writes a short text representation of this object to the given output stream.
out | the output stream to which to write. |
|
inline |
Destroys this graph.
|
inline |
Destroys this bag.
|
inline |
Destroys this tree decomposition and all of its bags.
bool** regina::TreeDecomposition::Graph::adj_ |
The adjacency matrix for the graph.
Specifically, adj_[i][j] is true
if and only if there is an arc from node i to node j.
int regina::TreeDecomposition::Graph::order_ |
The number of nodes in the graph.