regina::TreeEnumeration< LPConstraint, BanConstraint, IntType > Class Template Reference
Vertex Enumeration

The main entry point for the tree traversal algorithm to enumerate all vertex normal or almost normal surfaces in a 3-manifold triangulation. More...

`#include <enumerate/treetraversal.h>`

Inheritance diagram for regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >:

## Public Member Functions

| TreeEnumeration (const Triangulation< 3 > *tri, NormalCoords coords)
| Creates a new object for running the tree traversal algorithm. More...
unsigned long | nSolns () const
| Returns the total number of vertex normal or almost normal surfaces found thus far in the tree traversal search. More...
void | run (bool(*useSoln)(const TreeEnumeration &, void *), void *arg=0)
| Runs the complete tree traversal algorithm to enumerate vertex normal or almost normal surfaces. More...
bool | next (ProgressTracker *tracker=0)
| An incremental step in the tree traversal 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 TreeEnumeration &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 | writeSurface (const TreeEnumeration &tree, void *)
| A callback function that writes to standard output the full triangle-quadrilateral coordinates of the vertex normal or almost normal surface 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...

## 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, 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...
unsigned long | 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

### template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename IntType = Integer>
class regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >

The main entry point for the tree traversal algorithm to enumerate all vertex normal or almost normal surfaces in a 3-manifold triangulation.

For the analogous algorithm to enumerate taut angle structures, see the class TautEnumeration instead.

This class essentially implements the algorithm from "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 vertex surfaces for a given 3-manifold triangulation, simply construct a TreeEnumeration object and call run().

Alternatively, you can have more fine-grained control over the search. Instead of calling run(), you can construct a TreeEnumeration object and repeatedly call next() to step through each vertex surface one at a time. This allows you to pause and resume the search as you please.

If you simply wish to detect a single non-trivial solution under additional constraints (such as positive Euler characteristic), then use the class TreeSingleSoln instead, which is optimised for this purpose.

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.

By using appropriate template parameters LPConstraint and/or BanConstraint, it is possible to impose additional linear constraints on the normal surface solution cone, and/or explicitly force particular normal coordinates to zero. In this case, the notion of "vertex surface" is modified to mean a normal surface whose coordinates lie on an extreme ray of the restricted solution cone under these additional constraints (and whose coordinates are integers with no common divisor). 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).

Precondition
  The parameters LPConstraint and BanConstraint must be subclasses of LPConstraintSubspace and BanConstraintBase respectively. Note in particular that the base class LPConstraintBase is not enough here. See the LPConstraintBase, LPConstraintSubspace 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.

Warning
  Although the tree traversal algorithm can run in standard normal or almost normal coordinates, this is not recommended: it is likely to be much slower than in quadrilateral or quadrilateral-octagon coordinates respectively. Instead you should enumerate vertex solutions using quadrilateral or quadrilateral-octagon coordinates, and then run the conversion procedure NormalSurfaces::quadToStandard() or NormalSurfaces::quadOctToStandardAN().

Headers:\n 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.

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:\n Not present.

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

- enumerate/treetraversal.h

Copyright © 1999-2016, 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@maths.uq.edu.au).