Regina Calculation Engine
|
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/ntreetraversal.h>
Public Member Functions | |
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... | |
NNormalSurface * | buildSurface () const |
Reconstructs the full normal surface that is represented by the type vector at the current stage of the search. More... | |
NAngleStructure * | 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 NNormalSurface *s, const NMatrixInt *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 NAngleStructure *s, const NMatrixInt *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 | supported (NormalCoords coords) |
Indicates whether the given coordinate system is supported by this tree traversal infrastructure. More... | |
Protected Member Functions | |
NTreeTraversal (const NTriangulation *tri, NormalCoords coords, int branchesPerQuad, int branchesPerTri, bool enumeration) | |
Initialises a new base object for running the tree traversal algorithm. More... | |
~NTreeTraversal () | |
Destroys this object. 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 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< LPConstraint, Integer > * | lp_ |
Stores tableaux for linear programming at various nodes in the search tree. More... | |
LPData< LPConstraint, 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< LPConstraint, 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< LPConstraint, 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... | |
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 NTreeEnumeration (for enumerating all vertex normal surfaces), NTautEnumeration (for enumerating all taut angle structures), or NTreeSingleSoln (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 NTypeTrie, 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 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 NNormalSurfaceList, 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.
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 NTreeSingleSoln 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.
In some cases, it is impossible to add the extra linear constraints that we would like (for instance, if they require additional preconditions on the underlying triangulation). If this is a possibility in your setting, you should call constraintsBroken() to test for this once the NTreeTraversal object has been constructed.
The template argument Integer 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 NInteger class (in which integers can grow arbitrarily large, and overflow can never occur).