Regina Calculation Engine
|
The main entry point for the tree traversal algorithm to enumerate all taut angle structures in a 3-manifold triangulation. More...
#include <enumerate/treetraversal.h>
Public Member Functions | |
TautEnumeration (const Triangulation< 3 > *tri) | |
Creates a new object for running the tree traversal algorithm. More... | |
unsigned long | nSolns () const |
Returns the total number of taut angle structures found thus far in the tree traversal search. More... | |
void | run (bool(*useSoln)(const TautEnumeration &, void *), void *arg=0) |
Runs the complete tree traversal algorithm to enumerate all taut angle structures. More... | |
bool | next (ProgressTracker *tracker=0) |
An incremental step in the enumeration algorithm that runs forward until it finds the next solution. More... | |
bool | constraintsBroken () const |
Indicates whether or not the extra constraints from the template parameter LPConstraints were added successfully to the infrastructure for the search tree. More... | |
unsigned long | nVisited () 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... | |
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... | |
bool | verify (const NormalSurface *s, const MatrixInt *matchingEqns=0) const |
Ensures that the given normal or almost normal surface satisfies the matching equations, as well as any additional constraints from the template parameter LPConstraint. More... | |
bool | verify (const AngleStructure *s, const MatrixInt *angleEqns=0) const |
Ensures that the given angle structure satisfies the angle equations, as well as any additional constraints from the template parameter LPConstraint. More... | |
Static Public Member Functions | |
static bool | writeTypes (const TautEnumeration &tree, void *) |
A callback function that writes to standard output the type vector at the current point in the given tree traversal search. More... | |
static bool | writeStructure (const TautEnumeration &tree, void *) |
A callback function that writes to standard output the full angle structure coordinates of the taut angle structure at the current point in the given tree traversal search. More... | |
static bool | supported (NormalCoords coords) |
Indicates whether the given coordinate system is supported by this tree traversal infrastructure. More... | |
Protected Member Functions | |
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... | |
void | init (const int *) |
template<class LPConstraint , typename IntType > | |
void | enforceBans (LPData< LPConstraint, IntType > &lp) const |
Enforces all bans described by this class in the given tableaux. More... | |
Protected Attributes | |
const LPInitialTableaux< LPConstraintNone > | origTableaux_ |
The original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm begins. More... | |
const NormalCoords | coords_ |
The coordinate system in which we are enumerating or searching for normal surfaces, almost normal surfaces, or taut angle structures. 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< LPConstraintNone, Integer > * | lp_ |
Stores tableaux for linear programming at various nodes in the search tree. More... | |
LPData< LPConstraintNone, Integer > ** | 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< LPConstraintNone, Integer > ** | nextSlot_ |
Points to the next available tableaux in lp_ that is free to use at each level of the search tree. More... | |
unsigned long | nVisited_ |
Counts the total number of nodes in the search tree that we have visited thus far. More... | |
LPData< LPConstraintNone, Integer > | 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... | |
const Triangulation< 3 > * | tri_ |
The triangulation with which we are working. More... | |
bool * | banned_ |
Indicates which columns of a tableaux correspond to banned coordinates (e.g., banned normal disc types). More... | |
bool * | marked_ |
Indicates which columns of a tableaux correspond to marked coordinates (e.g., marked normal disc types). More... | |
The main entry point for the tree traversal algorithm to enumerate all taut angle structures in a 3-manifold triangulation.
For the analogous algorithm to enumerate vertex normal or almost normal surfaces, see the class TreeEnumeration instead.
This class follows a similar structure to the enumeration of vertex normal surfaces, as described 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.
To enumerate all taut angle structures on a given 3-manifold triangulation, simply construct a TautEnumeration object and call run().
Alternatively, you can have more fine-grained control over the search. Instead of calling run(), you can construct a TautEnumeration object and repeatedly call next() to step through each taut angle structure one at a time. This allows you to pause and resume the search as you please.
By using appropriate template parameters LPConstraint and/or BanConstraint, it is possible to impose additional linear constraints on the angle structure solution space, and/or explicitly force particular angles to be zero. See the LPConstraintBase and BanConstraintBase class notes for details.
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).
|
inherited |
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.
The angle structure that is returned will be newly constructed, and it is the caller's responsibility to destroy it when it is no longer required.
There will always be a unique taut angle structure corresponding to this type vector (this follows from the preconditions below).
true
, or any time that TautEnumeration::run() calls its callback function.
|
inherited |
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.
The surface that is returned will be newly constructed, and it is the caller's responsibility to destroy it when it is no longer required.
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.
true
, or any time that TreeEnumeration::run() calls its callback function.
|
inlineinherited |
Indicates whether or not the extra constraints from the template parameter LPConstraints were added successfully to the infrastructure for the search tree.
This query function is important because some constraints require additional preconditions on the underlying triangulation, and so these constraints cannot be added in some circumstances. If it is possible that the constraints might not be added successfully, this function should be tested as soon as the TreeTraversal object has been created.
If the extra constraints were not added successfully, the search tree will be left in a consistent state but will give incorrect results (specifically, the extra constraints will be treated as zero functions).
true
if the constraints were not added successfully, or false
if the constraints were added successfully.
|
inlineinherited |
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.
out | the output stream to which to write. |
|
protectedinherited |
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.
quadType | the quadrilateral or angle type to examine. |
|
inlineprotectedinherited |
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.
startFrom | the index into the type vector of the triangle type from which we begin searching. |
|
inlineinherited |
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.
|
protectedinherited |
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).
|
protectedinherited |
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.
nextType | the next type to process. |
|
inlinestaticinherited |
Indicates whether the given coordinate system is supported by this tree traversal infrastructure.
Currently this is true only for NS_STANDARD and NS_QUAD (for normal surfaces), NS_AN_STANDARD and NS_AN_QUAD_OCT (for almost normal surfaces), and NS_ANGLE (for taut angle structures). Any additional restrictions imposed by LPConstraint and BanConstraint will also be taken into account.
coords | the coordinate system being queried. |
true
if and only if this coordinate system is supported.
|
inherited |
Ensures that the given angle structure satisfies the angle equations, as well as any additional constraints from the template parameter LPConstraint.
This routine is for use only with angle structures, not normal (or almost normal) surfaces.
This routine is provided for diagnostic, debugging and verification purposes.
Instead of using the initial tableaux to verify the angle equations, this routine goes back to the original angle equations matrix as constructed by AngleStructureVector::makeAngleEquations(). This ensures that the test is independent of any potential problems with the tableaux. You are not required to pass your own angle equations (if you don't, they will be temporarily reconstructed for you); however, you may pass your own if you wish to use a non-standard angle equation matrix, and/or reuse the same matrix to avoid the overhead of reconstructing it every time this routine is called.
s | the angle structure to verify. |
angleEqns | the angle equations to check against the given angle structure; this may be 0, in which case the angle equations will be temporarily reconstructed for you using AngleStructureVector::makeAngleEquations(). |
true
if the given angle structure passes all of the tests described above, or false
if it fails one or more tests (indicating a problem or error).
|
inherited |
Ensures that the given normal or almost normal surface satisfies the matching equations, as well as any additional constraints from the template parameter LPConstraint.
This routine is for use only with normal (or almost normal) surfaces, not angle structures.
This routine is provided for diagnostic, debugging and verification purposes.
Instead of using the initial tableaux to verify the matching equations, this routine goes back to the original matching equations matrix as constructed by regina::makeMatchingEquations(). This ensures that the test is independent of any potential problems with the tableaux. You are not required to pass your own matching equations (if you don't, they will be temporarily reconstructed for you); however, you may pass your own if you wish to use a non-standard matching equation matrix, and/or reuse the same matrix to avoid the overhead of reconstructing it every time this routine is called.
If you do not pass your own matching equations and Regina is unable to construct them (which can happen when the underlying triangulation is not supported by the normal coordinate system), then this routine will return false
.
s | the normal surface to verify. |
matchingEqns | the matching equations to check against the given surface; this may be 0, in which case the matching equations will be temporarily reconstructed for you using regina::makeMatchingEquations(). |
true
if the given surface passes all of the tests described above, or false
if it fails one or more tests (indicating a problem or error).
|
protectedinherited |
The coordinate system in which we are enumerating or searching for normal surfaces, almost normal surfaces, or taut angle structures.
This must be one of NS_QUAD or NS_STANDARD if we are only supporting normal surfaces, one of NS_AN_QUAD_OCT or NS_AN_STANDARD if we are allowing octagons in almost normal surfaces, or NS_ANGLE if we are searching for taut angle structures.
|
protectedinherited |
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.
|
protectedinherited |
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.
|
protectedinherited |
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.
|
protectedinherited |
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.
|
protectedinherited |
The maximum number of tableaux that we need to keep in memory at any given time during the backtracking search.
|
protectedinherited |
The number of tetrahedra in the underlying triangulation.
|
protectedinherited |
The total length of a type vector.
|
protectedinherited |
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.
|
protectedinherited |
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.
|
protectedinherited |
The original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm begins.
|
protectedinherited |
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.
|
protectedinherited |
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.
|
protectedinherited |
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).