regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer > Class Template Reference
Vertex Enumeration

The main entry point for the tree traversal / branching algorithm to locate a single non-trivial normal surface satisfying given constraints within a 3-manifold triangulation. More...

`#include <enumerate/ntreetraversal.h>`

Inheritance diagram for regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer >:

## Public Member Functions

| NTreeSingleSoln (NTriangulation *tri, NormalCoords coords)
| Creates a new object for running the tree traversal / branching algorithm to locate a non-trivial surface that satisfies the chosen constraints. More...
bool | find ()
| Runs the tree traversal algorithm until it finds some non-trivial surface that satisfies the chosen constraints, or else proves that no such solution exists. More...
void | cancel ()
| Cancels the current find() operation. More...
Public Member Functions inherited from regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >
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...
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...

## Additional Inherited Members

Static Public Member Functions inherited from regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >
static bool | supported (NormalCoords coords)
| Indicates whether the given coordinate system is supported by this tree traversal infrastructure. More...
Protected Member Functions inherited from regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >
| NTreeTraversal (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 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 inherited from regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >
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 or almost normal surfaces. 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 have good potential for pruning the search tree. More...

## Detailed Description

### template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename Integer = NInteger>
class regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer >

The main entry point for the tree traversal / branching algorithm to locate a single non-trivial normal surface satisfying given constraints within a 3-manifold triangulation.

The constraints are passed using a combination of the template arguments LPConstraint and BanConstraint.

A common application of this algorithm is to find a surface of positive Euler characteristic, using the template argument LPConstraintEuler. This is useful for tasks such as 0-efficiency testing and prime decomposition (when this is done in standard normal coordinates), and also 3-sphere recognition (when this is done in standard almost normal coordinates). Indeed, the underlying algorithm is optimised for precisely this application.

By a "non-trivial" surface, we mean that at least one triangle coordinate is zero. Philosophically this is to avoid vertex linking surfaces, though if the triangulation has more than one vertex then this takes on a different meaning. See the warning on this matter below.

Be warned that this routine does not eliminate the zero vector, and so the template argument LPConstraint should include at least one constraint that eliminates the zero vector (e.g., positive Euler characteristic). Otherwise this algorithm may simply return the zero vector, and the information gained will not be very useful.

For any given normal coordinate, this routine will always try setting that coordinate to zero before it tries setting it to non-zero. In other words, if it does find a surface satisfying the given constraints, then it is guaranteed that the set of non-zero coordinate positions will be minimal (though not necessary a global minimum). In many settings (such as when using LPConstraintEuler), this guarantees that the final surface (if it exists) will be a vertex normal or almost normal surface.

The underlying algorithm is described in "A fast branching algorithm for unknot recognition with experimental polynomial-time behaviour", Burton and Ozlen, arXiv:1211.1079, and uses significant material from "A tree traversal algorithm for decision problems in knot theory and 3-manifold topology", Burton and Ozlen, Algorithmica (to appear), DOI 10.1007/s00453-012-9645-3.

To use this class, i.e., to locate a non-trivial normal or almost normal surface under the given constraints or to prove that no such surface exists, you can simply construct a NTreeSingleSoln object and call find(). You can then call buildSurface() to extract the details of the surface that was found.

If you wish to enumerate all vertex surfaces in a 3-manifold triangulation (instead of finding just one), you should use the class NTreeEnumeration instead.

This tree traversal can only enumerate surfaces in quadrilateral normal coordinates (NS_QUAD), standard normal coordinates (NS_STANDARD), quadrilateral-octagon almost normal coordinates (NS_AN_QUAD_OCT), or standard almost normal coordinates (NS_AN_STANDARD). For almost normal surfaces, we allow any number of octagons (including zero), but we only allow at most one octagon type in the entire triangulation. No coordinate systems other than these are supported.

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).

Warning
  Typically one should only use this class with one-vertex triangulations (since otherwise, setting at least one triangle coordinate to zero is not enough to rule out trivial vertex linking surfaces). Of course there may be settings in which multiple vertices make sense (for instance, in ideal triangulations with multiple cusps, or when using ban constraints), and in such settings this class will still work precisely as described.
  If you examine the type vector (for instance, by calling dumpTypes()), be aware that this class merges the old types 0 and 1 together into a single branch of the search tree. This means that type 0 never appears, and that type 1 could indicate either positive quadrilaterals in the first position, or else no quadrilaterals at all.

Precondition
  The parameters LPConstraint and BanConstraint must be subclasses of LPConstraintBase and BanConstraintBase respectively. See the LPConstraintBase and BanConstraintBase class notes for further details.

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.

Python:
  Not present.

The documentation for this class was generated from the following file:

- enumerate/ntreetraversal.h

Copyright © 1999-2013, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).