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

## Constructor & Destructor Documentation

## TreeEnumeration()

template<class LPConstraint , typename BanConstraint , typename IntType >

regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::TreeEnumeration | ( | const Triangulation< 3 > * | tri,
|  | NormalCoords | coords
| ) |  |

inline

Creates a new object for running the tree traversal algorithm.

This prepares the algorithm; in order to run the algorithm and enumerate vertex surfaces, you can either:

- call run(), which enumerates all vertex surfaces with a single function call;
- repeatedly call next(), which will step to the next vertex surface each time you call it.

Warning
  Although it is supported, it is highly recommended that you do not run a full vertex enumeration in standard normal or almost normal coordinates (this is for performance reasons). See the class notes for further discussion and better alternatives. In normal circumstances you should run a full vertex enumeration in quadrilateral or quadrilateral-octagon coordinates only.

Precondition
  The given triangulation is non-empty.
  Both the trianglation and the given coordinate system adhere to any preconditions required by the template parameters LPConstraint and BanConstraint.

Parameters

  tri | the triangulation in which we wish to enumerate vertex surfaces.
  coords | the coordinate system in which wish to enumerate vertex surfaces. This must be one of NS_QUAD, NS_STANDARD, NS_AN_QUAD_OCT, or NS_AN_STANDARD.

## Member Function Documentation

## buildStructure()

template<class LPConstraint , typename BanConstraint , typename IntType >

AngleStructure* regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::buildStructure | ( |  | ) | const

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

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; that is, the coordinate system passed to the TreeTraversal constructor was NS_ANGLE.

Returns
  the taut angle structure that has been found at the current stage of the search.

## buildSurface()

template<class LPConstraint , typename BanConstraint , typename IntType >

NormalSurface* regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::buildSurface | ( |  | ) | const

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.

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. That is, the coordinate system passed to the TreeTraversal constructor was not NS_ANGLE.

Returns
  a normal surface that has been found at the current stage of the search.

## constraintsBroken()

template<class LPConstraint , typename BanConstraint , typename IntType >

bool regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::constraintsBroken | ( |  | ) | const

inline inherited

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

Returns
  `true` if the constraints were not added successfully, or `false` if the constraints were added successfully.

## dumpTypes()

template<class LPConstraint , typename BanConstraint , typename IntType >

void regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::dumpTypes | ( | std::ostream & | out | ) | const

inline inherited

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.

Parameters

  out | the output stream to which to write.

## feasibleBranches()

template<class LPConstraint , typename BanConstraint , typename IntType >

int regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::feasibleBranches | ( | int | quadType | ) |

protected inherited

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.

## next()

template<class LPConstraint = LPConstraintNone, typename BanConstraint = BanNone, typename IntType = Integer>

bool regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::next | ( | ProgressTracker * | tracker = `0` | ) |

An incremental step in the tree traversal algorithm that runs forward until it finds the next solution.

Specifically: this continues the tree traversal from the current point until either it finds the next vertex normal or almost normal surface (in which case it returns `true`), or until the tree traversal is completely finished with no more solutions to be found (in which case it returns `false`).

If you simply wish to find and process all vertex surfaces, you may wish to consider the all-in-one routine run() instead. By using next() to step through one solution at a time however, you obtain more fine-grained control: for instance, you can "pause" and restart the search, or have tighter control over multithreading.

If next() does return `true` because it found a solution, you can extract details of the solution directly from this tree enumeration object: for instance, you can dump the type vector using dumpTypes(), or you can reconstruct the full normal or almost normal surface using buildSurface() and perform some other operations upon it. If you do call buildSurface(), remember to delete the normal surface once you are finished with it.

An optional progress tracker may be passed. If so, this routine will update the percentage progress and poll for cancellation requests. It will be assumed that an appropriate stage has already been declared via ProgressTracker::newStage() before this routine is called, and that ProgressTracker::setFinished() will be called after this routine returns (and presumably not until the entire search tree is exhausted). The percentage progress will be given in the context of a complete enumeration of the entire search tree (i.e., it will typically start at a percentage greater than 0, and end at a percentage less than 100).

Precondition
  The tree traversal algorithm has not yet finished. That is, you have not called run() before, and if you have called next() then it has always returned `true` (indicating that it has not yet finished the search).

Parameters

  tracker | a progress tracker through which progress will be reported, or 0 if no progress reporting is required.

Returns
  `true` if we found another vertex surface, or `false` if the search has now finished and no more vertex surfaces were found.

## nextUnmarkedTriangleType()

template<class LPConstraint , typename BanConstraint , typename IntType >

int regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::nextUnmarkedTriangleType | ( | int | startFrom | ) |

inline protected inherited

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.

## nSolns()

template<class LPConstraint , typename BanConstraint , typename IntType >

unsigned long regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::nSolns | ( |  | ) | const

inline

Returns the total number of vertex normal or almost normal surfaces found thus far in the tree traversal search.

If you called run(), then this will simply be the total number of vertex surfaces. If you are calling next() one surface at time, this will be the partial count of how many vertex surfaces have been found until now.

Returns
  the number of solutions found so far.

## nVisited()

template<class LPConstraint , typename BanConstraint , typename IntType >

unsigned long regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::nVisited | ( |  | ) | const

inline inherited

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.

## percent()

template<class LPConstraint , typename BanConstraint , typename IntType >

double regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::percent | ( |  | ) | const

protected inherited

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.

## run()

template<class LPConstraint , typename BanConstraint , typename IntType >

void regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::run | ( | bool(*)(const TreeEnumeration< LPConstraint, BanConstraint, IntType > &, void *) | useSoln,
|  | void * | arg = `0`
| ) |  |

inline

Runs the complete tree traversal algorithm to enumerate vertex normal or almost normal surfaces.

For each vertex surface that is found, this routine will call the function useSoln. It will pass two arguments to this function: (i) this tree enumeration object, and (ii) an arbitrary piece of data that you can supply via the argument arg.

You can extract details of the solution directly from the tree enumeration object: for instance, you can dump the type vector using dumpTypes(), or you can reconstruct the full normal or almost normal surface using buildSurface() and perform some other operations upon it. If you do call buildSurface(), remember to delete the normal surface once you are finished with it.

The tree traversal will block until your callback function useSoln returns. If the callback function returns `true`, then run() will continue the tree traversal. If it returns `false`, then run() will abort the search and return immediately.

The usual way of using this routine is to construct a TreeEnumeration object and then immediately call run(). However, if you prefer, you may call run() after one or more calls to next(). In this case, run() will continue the search from the current point and run it to its completion. In other words, run() will locate and call useSoln for all vertex surfaces that had not yet been found, but it will not call useSoln on those surfaces that had previously been found during earlier calls to next().

Precondition
  The tree traversal algorithm has not yet finished. That is, you have not called run() before, and if you have called next() then it has always returned `true` (indicating that it has not yet finished the search).

Parameters

  useSoln | a callback function that will be called each time we locate a vertex surface, as described above.
  arg | the second argument to pass to the callback function; this may be any type of data that you like.

## setNext()

template<class LPConstraint , typename BanConstraint , typename IntType >

void regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::setNext | ( | int | nextType | ) |

protected inherited

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.

## supported()

template<class LPConstraint , typename BanConstraint , typename IntType >

bool regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::supported | ( | NormalCoords | coords | ) |

inline static inherited

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.

Parameters

  coords | the coordinate system being queried.

Returns
  `true` if and only if this coordinate system is supported.

## verify() [1/2]

template<class LPConstraint , typename BanConstraint , typename IntType >

bool regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::verify | ( | const NormalSurface * | s,
|  | const MatrixInt * | matchingEqns = `0`
| ) |  | const

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.

Precondition
  The normal or almost normal surface s uses the same coordinate system as was passed to the TreeTraversal constructor. Moreover, this coordinate system is in fact a normal or almost normal coordinate system (i.e., not NS_ANGLE).
  If matchingEqns is non-null, then the number of columns in matchingEqns is equal to the number of coordinates in the underlying normal or almost normal coordinate system.

Parameters

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

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

## verify() [2/2]

template<class LPConstraint , typename BanConstraint , typename IntType >

bool regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::verify | ( | const AngleStructure * | s,
|  | const MatrixInt * | angleEqns = `0`
| ) |  | const

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.

Precondition
  The coordinate system passed to the TreeTraversal constructor was NS_ANGLE.
  If angleEqns is non-null, then the number of columns in angleEqns is equal to the number of coordinates in the underlying angle structure coordinate system.

Parameters

  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::makeMatchingEquations().

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

## writeSurface()

template<class LPConstraint , typename BanConstraint , typename IntType >

bool regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::writeSurface | ( | const TreeEnumeration< LPConstraint, BanConstraint, IntType > & | tree,
|  | void * |
| ) |  |

inline static

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.

You can use this as the callback function useSoln that is passed to run().

The normal surface coordinates will be written on a single line, with spaces and punctuation separating them, a prefix indicating which solution we are up to, and a final newline appended. This output format is subject to change in future versions of Regina.

The second (void*) argument is ignored. It is only present for compatibility with run().

Precondition
  The given tree traversal is at a point in the search where it has reached the deepest level of the search tree and found a feasible solution that represents a vertex normal or almost normal surface. This is always the case any time after next() returns `true`, or any time that run() calls its callback function.

Parameters

  tree | the tree traversal object from which we are extracting the current vertex normal or almost normal surface.

Returns
  `true` (which indicates to run() that we should continue the tree traversal).

## writeTypes()

template<class LPConstraint , typename BanConstraint , typename IntType >

bool regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::writeTypes | ( | const TreeEnumeration< LPConstraint, BanConstraint, IntType > & | tree,
|  | void * |
| ) |  |

inline static

A callback function that writes to standard output the type vector at the current point in the given tree traversal search.

You can use this as the callback function useSoln that is passed to run().

The type vector will be written on a single line, with no spaces between types, with a prefix indicating which solution we are up to, and with a final newline appended. This output format is subject to change in future versions of Regina.

The second (void*) argument is ignored. It is only present for compatibility with run().

Precondition
  The given tree traversal is at a point in the search where it has reached the deepest level of the search tree and found a feasible solution that represents a vertex normal or almost normal surface. This is always the case any time after next() returns `true`, or any time that run() calls its callback function.

Parameters

  tree | the tree traversal object from which we are extracting the current type vector.

Returns
  `true` (which indicates to run() that we should continue the tree traversal).

## Member Data Documentation

## coords_

template<class LPConstraint , typename BanConstraint , typename IntType >

const NormalCoords regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::coords_

protected inherited

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.

## level_

template<class LPConstraint , typename BanConstraint , typename IntType >

int regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::level_

protected inherited

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_

template<class LPConstraint , typename BanConstraint , typename IntType >

LPData<LPConstraint, IntType>* regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::lp_

protected inherited

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_

template<class LPConstraint , typename BanConstraint , typename IntType >

LPData<LPConstraint, IntType>** regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::lpSlot_

protected inherited

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_

template<class LPConstraint , typename BanConstraint , typename IntType >

LPData<LPConstraint, IntType>** regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::nextSlot_

protected inherited

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_

template<class LPConstraint , typename BanConstraint , typename IntType >

const int regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::nTableaux_

protected inherited

The maximum number of tableaux that we need to keep in memory at any given time during the backtracking search.

## nTets_

template<class LPConstraint , typename BanConstraint , typename IntType >

const int regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::nTets_

protected inherited

The number of tetrahedra in the underlying triangulation.

## nTypes_

template<class LPConstraint , typename BanConstraint , typename IntType >

const int regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::nTypes_

protected inherited

The total length of a type vector.

## nVisited_

template<class LPConstraint , typename BanConstraint , typename IntType >

unsigned long regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::nVisited_

protected inherited

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_

template<class LPConstraint , typename BanConstraint , typename IntType >

int regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::octLevel_

protected inherited

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_

template<class LPConstraint , typename BanConstraint , typename IntType >

const LPInitialTableaux<LPConstraint> regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::origTableaux_

protected inherited

The original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm begins.

## tmpLP_

template<class LPConstraint , typename BanConstraint , typename IntType >

LPData<LPConstraint, IntType> regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::tmpLP_[4]

protected inherited

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_

template<class LPConstraint , typename BanConstraint , typename IntType >

char* regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::type_

protected inherited

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_

template<class LPConstraint , typename BanConstraint , typename IntType >

int* regina::TreeTraversal< LPConstraint, BanConstraint, IntType >::typeOrder_

protected inherited

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

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