A base class for searches that employ the tree traversal algorithm for enumerating and locating vertex normal surfaces and taut angle structures. More...
#include <enumerate/treetraversal.h>
Public Member Functions | |
| ~TreeTraversal () | |
| Destroys this object. More... | |
| size_t | visited () const |
| Returns the total number of nodes in the search tree that we have visited thus far in the tree traversal. More... | |
| void | dumpTypes (std::ostream &out) const |
| Writes the current type vector to the given output stream. More... | |
| std::string | typeString () const |
| Returns the current type vector in string form. More... | |
| void | writeTextShort (std::ostream &out) const |
| Writes a short text representation of this object to the given output stream. More... | |
| NormalSurface | buildSurface () const |
| Reconstructs the full normal surface that is represented by the type vector at the current stage of the search. More... | |
| AngleStructure | buildStructure () const |
| Reconstructs the full taut angle structure that is represented by the type vector at the current stage of the search. More... | |
| TreeTraversal (const TreeTraversal &)=delete | |
| TreeTraversal & | operator= (const TreeTraversal &)=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... | |
Static Public Member Functions | |
| static bool | supported (NormalEncoding enc) |
| Indicates whether the given normal surface or angle structure vector encoding is supported by this tree traversal infrastructure. More... | |
Protected Member Functions | |
| TreeTraversal (const Triangulation< 3 > &tri, NormalEncoding enc, int branchesPerQuad, int branchesPerTri, bool enumeration) | |
| Initialises a new base object for running the tree traversal algorithm. More... | |
| void | setNext (int nextType) |
| Rearranges the search tree so that nextType becomes the next type that we process. More... | |
| int | nextUnmarkedTriangleType (int startFrom) |
| Returns the next unmarked triangle type from a given starting point. More... | |
| int | feasibleBranches (int quadType) |
| Determines how many different values we could assign to the given quadrilateral or angle type and still obtain a feasible system. More... | |
| double | percent () const |
| Gives a rough estimate as to what percentage of the way the current type vector is through a full enumeration of the search tree. More... | |
Protected Attributes | |
| const LPInitialTableaux< LPConstraint > | origTableaux_ |
| The original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm begins. More... | |
| const NormalEncoding | enc_ |
| The normal surface or angle structure vector encoding that we are using for our enumeration task. More... | |
| const BanConstraint | ban_ |
| Details of any banning/marking constraints that are in use. More... | |
| const int | nTets_ |
| The number of tetrahedra in the underlying triangulation. More... | |
| const int | nTypes_ |
| The total length of a type vector. More... | |
| const int | nTableaux_ |
| The maximum number of tableaux that we need to keep in memory at any given time during the backtracking search. More... | |
| char * | type_ |
| The current working type vector. More... | |
| int * | typeOrder_ |
| A permutation of 0,...,nTypes_-1 that indicates in which order we select types: the first type we select (at the root of the tree) is type_[typeOrder_[0]], and the last type we select (at the leaves of the tree) is type_[typeOrder_[nTypes_-1]]. More... | |
| int | level_ |
| The current level in the search tree. More... | |
| int | octLevel_ |
| The level at which we are enforcing an octagon type (with a strictly positive number of octagons). More... | |
| LPData< LPConstraint, IntType > * | lp_ |
| Stores tableaux for linear programming at various nodes in the search tree. More... | |
| LPData< LPConstraint, IntType > ** | lpSlot_ |
| Recall from above that the array lp_ stores tableaux for the current node in the search tree and all of its ancestors. More... | |
| LPData< LPConstraint, IntType > ** | nextSlot_ |
| Points to the next available tableaux in lp_ that is free to use at each level of the search tree. More... | |
| size_t | nVisited_ |
| Counts the total number of nodes in the search tree that we have visited thus far. More... | |
| LPData< LPConstraint, IntType > | tmpLP_ [4] |
| Temporary tableaux used by the function feasibleBranches() to determine which quadrilateral types or angle types have good potential for pruning the search tree. More... | |
Detailed Description
class regina::TreeTraversal< LPConstraint, BanConstraint, IntType >
A base class for searches that employ the tree traversal algorithm for enumerating and locating vertex normal surfaces and taut angle structures.
Users should not use this base class directly; instead use one of the subclasses TreeEnumeration (for enumerating all vertex normal surfaces), TautEnumeration (for enumerating all taut angle structures), or TreeSingleSoln (for locating a single non-trivial solution under additional constraints, such as positive Euler characteristic).
For normal surfaces, the full algorithms are described respectively in "A tree traversal algorithm for decision problems in knot theory and 3-manifold topology", Burton and Ozlen, Algorithmica 65:4 (2013), pp. 772-801, and "A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour", Burton and Ozlen, arXiv:1211.1079.
This base class provides the infrastructure for the search tree, and the subclasses handle the mechanics of the moving through the tree according to the backtracking search. The domination test is handled separately by the class TypeTrie, and the feasibility test is handled separately by the class LPData.
This class holds the particular state of the tree traversal at any point in time, as described by the current level (indicating our current depth in the search tree) and type vector (indicating which branches of the search tree we have followed). For details on these concepts, see the Algorithmica paper cited above. The key details are summarised below; throughout this discussion n represents the number of tetrahedra in the underlying triangulation.
- In quadrilateral coordinates, the type vector is a sequence of n integers, each equal to 0, 1, 2 or 3, where the ith integer describes the choice of quadrilateral location in the ith tetrahedron.
- In standard coordinates, the type vector begins with the n quadrilateral choices outlined above. This is then followed by an additional 4n integers, each equal to 0 or 1; these correspond to the 4n triangle coordinates, and indicate whether each coordinate is zero or non-zero.
- In angle structure coordinates, this class identifies taut angle structures only. Here the type vector is a sequence of n integers, each equal to 1, 2 or 3, where the ith integer describes the location of the two π angles in the ith tetrahedron.
In the original Algorithmica paper, we choose types in the order type_[0], type_[1] and so on, working from the root of the tree down to the leaves. Here we support a more flexible system: there is an internal permutation typeOrder_, and we choose types in the order type_[typeOrder_[0]], type_[typeOrder_[1]] and so on. This permutation may mix quadrilateral and triangle processing, and may even change as the algorithm runs.
This class can also support octagon types in almost normal surfaces. However, we still do our linear programming in standard or quadrilateral coordinates, where we represent an octagon using two conflicting quadrilaterals in the same tetrahedron (which meet the tetrahedron boundary in the same set of arcs as a single octagon would). As with the almost normal coordinate systems in NormalSurfaces, we allow multiple octagons of the same type, but only one octagon type in the entire tetrahedron. In the type vector, octagons are indicated by setting a quadrilateral type to 4, 5 or 6.
There is optional support for adding extra linear constraints (such as a constraint on Euler characteristic), supplied by the template parameter LPConstraint. If there are no additional constraints, simply use the template parameter LPConstraintNone. Note that some constraint classes may cause the TreeTraveral class constructor to throw an exception; see the constructor documentation for details.
Also, there is optional support for banning coordinates (i.e., insisting that certain coordinates must be set to zero), and/or marking coordinates (for normal and almost normal surfaces this affects what is meant by a "non-trivial" surface for the TreeSingleSoln algorithm; the concept of marking may be expanded further in future versions of Regina). These options are supplied by the template parameter BanConstraint. If there are no coordinates to ban or mark, simply use the template parameter BanNone.
The template argument IntType indicates the integer type that will be used throughout the underlying linear programming machinery. Unless you have a good reason to do otherwise, you should use the arbitrary-precision Integer class (in which integers can grow arbitrarily large, and overflow can never occur).
Subclasses of TreeTraversal are designed to manage the execution of significant enumeration and search operations, and so this class does not support copying, moving or swapping.
- Precondition
- The parameter LPConstraint must be a subclass of LPConstraintBase, and BanConstraint must either BanNone or a subclass of BanConstraintBase. See the LPConstraintBase and BanConstraintBase class notes for further details.
- The default constructor for the template class IntType must intialise each new integer to zero. The classes Integer and NativeInteger, for instance, have this property.
- Headers
- Parts of this template class are implemented in a separate header (treetraversal-impl.h), which is not included automatically by this file. Most end users should not need this extra header, since Regina's calculation engine already includes explicit instantiations for common combinations of template arguments.
- Python
- This is a heavily templated class; moreover, it only serves as a base class, and you will most likely not need to access this class directly. Instead see the subclasses TreeEnumeration, TautEnumeration and TreeSingleSoln, each of which offers a more useful interface for solving different type of problems. The variants of this TreeTraversal base class that are available in Python have Python names of the form TreeTraversal_LPConstraint_BanConstraint, where the suffixes LPConstraint and BanConstraint are abbreviated versions of the corresponding template parameters; these suffixes are omitted entirely for the common cases LPConstraintNone and BanNone. In all cases, the IntType parameter is taken to be regina::Integer.
- Warning
- The API for this class has not yet been finalised. This means that the class interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please watch the detailed changelogs upon new releases to see if you need to make changes to your code.
Constructor & Destructor Documentation
◆ ~TreeTraversal()
| regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::~TreeTraversal | ( | ) |
Destroys this object.
◆ TreeTraversal()
|
protected |
Initialises a new base object for running the tree traversal algorithm.
This routine may only be called by subclass constructors; for more information on how to create and run a tree traversal, see subclasses such as TreeEnumeration, TautEnumeration or TreeSingleSoln instead.
- Precondition
- The given triangulation is non-empty.
- Exceptions
-
InvalidArgument it was not possible to add the extra constraints from the LPConstraint template argument, due to an error which should have been preventable with the right checks in advance. Such exceptions are generated by the LPConstraint class, and so you should consult the class documentation for your chosen LPConstraint template argument to see if this is a possibility. InvalidArgument it was not possible to add the extra constraints from the LPConstraint template argument, due to an error that was "genuinely" unforseeable. Again, such exceptions are generated by your chosen LPConstraint class, and you should consult its documentation to see if this is a possibility.
- Parameters
-
tri the triangulation in which we wish to search for normal surfaces or taut angle structures. enc the normal surface or angle structure vector encoding that we are working with; in particular, this may be the special angle structure encoding. branchesPerQuad the maximum number of branches we spawn in the search tree for each quadrilateral or angle type (e.g., 4 for a vanilla normal surface tree traversal algorithm, or 3 for enumerating taut angle structures). branchesPerTri the maximum number of branches we spawn in the search tree for each triangle type (e.g., 2 for a vanilla normal surface tree traversal algorithm). If the underlying coordinate system does not support triangles then this argument will be ignored. enumeration trueif we should optimise the tableaux for a full enumeration of vertex surfaces or taut angle structures, orfalseif we should optimise the tableaux for an existence test (such as searching for a non-trivial normal disc or sphere).
Member Function Documentation
◆ buildStructure()
| AngleStructure regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::buildStructure | ( | ) | const |
Reconstructs the full taut angle structure that is represented by the type vector at the current stage of the search.
This routine is for use only with taut angle structures, not normal or almost normal surfaces.
There will always be a unique taut angle structure corresponding to this type vector (this follows from the preconditions below).
- Precondition
- This tree traversal is at a point in the search where it has found a feasible solution that represents a taut angle structure. This condition is always true after TautEnumeration::next() returns
true, or any time that TautEnumeration::run() calls its callback function. - We are working with angle structure coordinates. This will be checked (see the exception details below).
- Exceptions
-
FailedPrecondition we are not working with angle structure coordinates (i.e., the coordinate system passed to the TreeTraversal constructor was not NS_ANGLE).
- Returns
- the taut angle structure that has been found at the current stage of the search.
◆ buildSurface()
| NormalSurface regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::buildSurface | ( | ) | const |
Reconstructs the full normal surface that is represented by the type vector at the current stage of the search.
This routine is for use only with normal (or almost normal) surfaces, not taut angle structures.
If the current type vector does not represent a vertex normal surface (which may be the case when calling TreeSingleSoln::find()), then there may be many normal surfaces all represented by the same type vector; in this case there are no further guarantees about which of these normal surfaces you will get.
The surface that is returned will use the same vector encoding that was passed to the TreeTraversal class constructor.
- Precondition
- This tree traversal is at a point in the search where it has found a feasible solution that represents a normal surface (though this need not be a vertex surface). This condition is always true after TreeEnumeration::next() or TreeSingleSoln::find() returns
true, or any time that TreeEnumeration::run() calls its callback function. - We are working with normal or almost normal surfaces. This will be checked (see the exception details below).
- Exceptions
-
FailedPrecondition we are not working with normal or almost normal surfaces (i.e., the coordinate system passed to the TreeTraversal constructor was NS_ANGLE).
- Returns
- a normal surface that has been found at the current stage of the search.
◆ detail()
|
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.
◆ dumpTypes()
|
inline |
Writes the current type vector to the given output stream.
There will be no spaces between the types, and there will be no final newline.
This routine outputs the same information that typeString() returns.
- Python
- Not rpesent; instead use typeString(), which returns this same information as a string.
- Parameters
-
out the output stream to which to write.
◆ feasibleBranches()
|
protected |
Determines how many different values we could assign to the given quadrilateral or angle type and still obtain a feasible system.
This will involve solving three or four linear programs, all based on the current state of the tableaux at the current level of the search tree. These assign 0, 1, 2 and 3 to the given quadrilateral or angle type in turn (here 0 is not used for angle types), and then enforce the corresponding constraints. For quadrilateral types, we count types 0 and 1 separately as in TreeEnumeration, not merged together as in TreeSingleSoln.
- Precondition
- The given quadrilateral or angle type has not yet been processed in the search tree (i.e., it has not had an explicit value selected).
- When using angle structure coordinates, the final scaling coordinate has already been enforced as positive. (This is because, for angle structures, this routine does nothing to eliminate the zero solution.)
- Parameters
-
quadType the quadrilateral or angle type to examine.
- Returns
- the number of type values 0, 1, 2 or 3 that yield a feasible system; this will be between 0 and 4 inclusive for quadrilateral types, or between 0 and 3 inclusive for angle types.
◆ nextUnmarkedTriangleType()
|
inlineprotected |
Returns the next unmarked triangle type from a given starting point.
Specifically, this routine returns the first unmarked triangle type whose type number is greater than or equal to startFrom. For more information on marking, see the BanConstraintBase class notes.
This routine simply searches through types by increasing index into the type vector; in particular, it does not make any use of the reordering defined by the typeOrder_ array.
- Precondition
- We are working in standard normal or almost normal coordinates. That is, the coordinate system passed to the TreeTraversal constructor was one of NS_STANDARD or NS_AN_STANDARD.
- The argument startFrom is at least nTets_ (i.e., it is at least as large as the index of the first triangle type).
- Parameters
-
startFrom the index into the type vector of the triangle type from which we begin searching.
- Returns
- the index into the type vector of the next unmarked triangle type from startFrom onwards, or -1 if there are no more remaining.
◆ percent()
|
protected |
Gives a rough estimate as to what percentage of the way the current type vector is through a full enumeration of the search tree.
This is useful for progress tracking.
This routine only attemps to determine the percentage within a reasonable range of error (at the time of writing, 0.01%). This allows it to be more efficient (in particular, by only examining the branches closest to the root of the search tree).
- Returns
- the percentage, as a number between 0 and 100 inclusive.
◆ setNext()
|
protected |
Rearranges the search tree so that nextType becomes the next type that we process.
Specifically, this routine will set typeOrder_[level_ + 1] to nextType_, and will move other elements of typeOrder_ back by one position to make space as required.
- Precondition
- nextType is in the range 0,...,nTypes-1 inclusive.
- nextType is still waiting to be processed; that is, nextType does not appear in the list typeOrder_[0,...,level_].
- Parameters
-
nextType the next type to process.
◆ str()
|
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 Pythonrepr()function will incorporate this into its output.
- Returns
- a short text representation of this object.
◆ supported()
|
inlinestatic |
Indicates whether the given normal surface or angle structure vector encoding is supported by this tree traversal infrastructure.
Any restrictions imposed by LPConstraint and BanConstraint will be taken into account.
Note that, even if an encoding is supported, this does not mean that the underlying tableaux will use the same encoding internally. See LPInitialTableaux for more details on this.
- Parameters
-
enc the vector encoding being queried. In particular, this may be the special angle structure encoding.
- Returns
trueif and only if the given vector encoding is supported.
◆ typeString()
|
inline |
Returns the current type vector in string form.
There will be no spaces between the types.
This routine returns the same information that dumpTypes() writes.
- Parameters
-
the type vector in string form.
◆ utf8()
|
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.
◆ visited()
|
inline |
Returns the total number of nodes in the search tree that we have visited thus far in the tree traversal.
This figure might grow much faster than the number of solutions, since it also counts traversals through "dead ends" in the search tree.
This counts all nodes that we visit, including those that fail any or all of the domination, feasibility and zero tests. The precise way that this number is calculated is subject to change in future versions of Regina.
If you called an "all at once" routine such as TreeEnumeration::run() or TreeSingleSoln::find(), then this will be the total number of nodes that were visited in the entire tree traversal. If you are calling an "incremental" routine such as TreeEnumeration::next() (i.e., you are generating one solution at time), then this will be the partial count of how many nodes have been visited so far.
- Returns
- the number of nodes visited so far.
◆ writeTextLong()
|
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::TreeTraversal< LPConstraint, BanConstraint, IntType >::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.
Member Data Documentation
◆ ban_
|
protected |
Details of any banning/marking constraints that are in use.
◆ enc_
|
protected |
The normal surface or angle structure vector encoding that we are using for our enumeration task.
Note that the tableaux will not necessarily use this same encoding; see LPInitialTableaux for details.
◆ level_
|
protected |
The current level in the search tree.
As the search runs, this holds the index into typeOrder_ corresponding to the last type that we chose.
◆ lp_
|
protected |
Stores tableaux for linear programming at various nodes in the search tree.
We only store a limited number of tableaux at any given time, and as the search progresses we overwrite old tableaux with new tableaux.
More precisely, we store a linear number of tableaux, essentially corresponding to the current node in the search tree and all of its ancestores, all the way up to the root node. In addition to these tableaux, we also store other immediate children of these ancestores that we have pre-prepared for future processing. See the documentation within routines such as TreeEnumeration::next() for details of when and how these tableaux are constructed.
◆ lpSlot_
|
protected |
Recall from above that the array lp_ stores tableaux for the current node in the search tree and all of its ancestors.
This means we have one tableaux for the root node, as well as additional tableaux at each level 0,1,...,level_.
The array lpSlot_ indicates which element of the array lp_ holds each of these tableaux. Specifically: lpSlot_[0] points to the tableaux for the root node, and for each level i in the range 0,...,level_, the corresponding tableaux is *lpSlot_[i+1]. Again, see the documentation within routines such as TreeEnumeration::next() for details of when and how these tableaux are constructed and later overwritten.
◆ nextSlot_
|
protected |
Points to the next available tableaux in lp_ that is free to use at each level of the search tree.
Specifically: nextSlot_[0] points to the next free tableaux at the root node, and for each level i in the range 0,...,level_, the corresponding next free tableaux is *nextSlot_[i+1].
The precise layout of the nextSlot_ array depends on the order in which we process quadrilateral, triangle and/or angle types.
◆ nTableaux_
|
protected |
The maximum number of tableaux that we need to keep in memory at any given time during the backtracking search.
◆ nTets_
|
protected |
The number of tetrahedra in the underlying triangulation.
◆ nTypes_
|
protected |
The total length of a type vector.
◆ nVisited_
|
protected |
Counts the total number of nodes in the search tree that we have visited thus far.
This may grow much faster than the number of solutions, since it also counts traversals through "dead ends" in the search tree.
◆ octLevel_
|
protected |
The level at which we are enforcing an octagon type (with a strictly positive number of octagons).
If we are working with angle structures or normal surfaces only (and so we do not allow octagons at all), then octLevel_ = nTypes_. If we are allowing almost normal surfaces but we have not yet chosen an octagon type, then octLevel_ = -1.
◆ origTableaux_
|
protected |
The original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm begins.
◆ tmpLP_
|
protected |
Temporary tableaux used by the function feasibleBranches() to determine which quadrilateral types or angle types have good potential for pruning the search tree.
Other routines are welcome to use these temporary tableaux also (as "scratch space"); however, be aware that any call to feasibleBranches() will overwrite them.
◆ type_
|
protected |
The current working type vector.
As the search runs, we modify this type vector in-place. Any types beyond the current level in the search tree will always be set to zero.
◆ typeOrder_
|
protected |
A permutation of 0,...,nTypes_-1 that indicates in which order we select types: the first type we select (at the root of the tree) is type_[typeOrder_[0]], and the last type we select (at the leaves of the tree) is type_[typeOrder_[nTypes_-1]].
This permutation is allowed to change as the algorithm runs (though of course you can only change sections of the permutation that correspond to types not yet selected).
The documentation for this class was generated from the following file:
- enumerate/treetraversal.h