Vertex Enumeration

Polytope vertex enumeration algorithms. More...

## Classes

class | regina::NDoubleDescription
| Implements a modified double description method for polytope vertex enumeration. More...
class | regina::NEnumConstraintList
| Represents an individual validity constraint for use with polytope vertex enumeration. More...
class | regina::NHilbertCD
| Implements a modified Contejean-Devie algorithm for enumerating Hilbert bases. More...
class | regina::NHilbertDual
| Implements a modified dual algorithm for enumerating Hilbert bases. More...
class | regina::NHilbertPrimal
| Implements a modified primal algorithm for enumerating Hilbert bases. More...
class | regina::NMaxAdmissible
| Used to enumerate all maximal admissible faces of a polyhedral cone under a given set of admissibility constraints. More...
struct | regina::LPConstraintBase::Coefficients
| Stores the extra coefficients in a single column for the nConstraints additional rows that we add to the tableaux to describe the nConstraints additional linear equations or inequalities. More...
class | regina::LPConstraintBase
| A base class for additional linear constraints that we can add to the tableaux of normal surface or angle structure matching equations. More...
class | regina::LPConstraintSubspace
| A subclass of LPConstraintBase used for constraints defined entirely by homogeneous linear equations. More...
struct | regina::LPConstraintNone::Coefficients
| Stores the extra coefficients in the tableaux associated with this constraint class (which for this class is a no-op, since in this case there are no extra coefficients). More...
class | regina::LPConstraintNone
| A do-nothing class that imposes no additional linear constraints on the tableaux of normal surface or angle structure matching equations. More...
struct | regina::LPConstraintEuler::Coefficients
| Stores the extra coefficients in the tableaux associated with this constraint class (in this case, one extra integer per column). More...
class | regina::LPConstraintEuler
| A class that constraints the tableaux of normal surface matching equations to ensure that Euler characteristic is strictly positive. More...
struct | regina::LPConstraintNonSpun::Coefficients
| Stores the extra coefficients in the tableaux associated with this constraint class (in this case, two extra integers per column). More...
class | regina::LPConstraintNonSpun
| A class that constraints the tableaux of normal surface matching equations to ensure that normal surfaces in an ideal triangulation are compact (thereby avoiding spun normal surfaces with infinitely many triangles). More...
class | regina::BanConstraintBase
| A base class for additional banning and marking constraints that we can place on tree traversal algorithms. More...
class | regina::BanNone
| A do-nothing class that bans no coordinates and marks no coordinates. More...
class | regina::BanBoundary
| A class that bans normal disc types that meet the boundary of the underlying triangulation. More...
class | regina::BanTorusBoundary
| A class that bans and marks disc types associated with torus boundary components. More...
class | regina::LPMatrix< Integer >
| A matrix class for use with linear programming. More...
struct | regina::LPInitialTableaux< LPConstraint >::Col
| Stores a single column of the adjusted matching equation matrix in sparse form. More...
class | regina::LPInitialTableaux< LPConstraint >
| Stores an adjusted matrix of homogeneous linear matching equations based on a given triangulation, in sparse form. More...
class | regina::LPData< LPConstraint, Integer >
| Stores an intermediate tableaux for the dual simplex method, and contains all of the core machinery for using the dual simplex method. More...
class | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >
| A base class for searches that employ the tree traversal algorithm for enumerating and locating vertex normal surfaces and taut angle structures. More...
class | regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >
| The main entry point for the tree traversal algorithm to enumerate all vertex normal or almost normal surfaces in a 3-manifold triangulation. More...
class | regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >
| The main entry point for the tree traversal algorithm to enumerate all taut angle structures in a 3-manifold triangulation. More...
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. More...
class | regina::NTypeTrie< nTypes >
| A trie that stores a set of type vectors of a fixed length. More...
class | regina::NPosOrder
| A comparison object that sorts hyperplanes by position vectors. More...

## Typedefs

typedef NDoubleDescription | regina::NDoubleDescriptor
| A legacy typedef provided for backward compatibility only. More...

## Enumerations

enum | { regina::LPConstraintBase::nConstraints }
enum | { nConstraints = 0 }
enum | { nConstraints = 1 }
enum | { nConstraints = 2 }

## Functions

| regina::LPConstraintBase::Coefficients::Coefficients ()
| Creates an uninitialised set of coefficients for a single column. More...
template<typename Integer >
void | regina::LPConstraintBase::Coefficients::fillFinalRows (LPMatrix< Integer > &m, unsigned col) const
| Explicitly fills the final row(s) of the given tableaux matrix with the coefficients stored in this Coefficients structure. More...
template<typename Integer >
Integer | regina::LPConstraintBase::Coefficients::innerProduct (const LPMatrix< Integer > &m, unsigned mRow) const
| Computes the inner product of (i) the final nConstraints entries in the given row of the given matrix with (ii) the nConstraints column coefficients stored in this data structure. More...
template<typename Integer >
Integer | regina::LPConstraintBase::Coefficients::innerProductOct (const LPMatrix< Integer > &m, unsigned mRow) const
| A variant of innerProduct() that takes into account any adjustments to these linear constraint(s) that are required when this is a quadrilateral column being used to represent an octagon type. More...
static bool | regina::LPConstraintBase::addRows (LPInitialTableaux< LPConstraintBase >::Col *col, const int *columnPerm, const NTriangulation *tri)
| Explicitly constructs equations for the linear function(s) constrained by this class. More...
template<typename Integer >
static void | regina::LPConstraintBase::constrain (LPData< LPConstraintNone, Integer > &lp, unsigned numCols)
| Explicitly constraints each of these linear functions to an equality or inequality in the underlying tableaux. More...
static bool | regina::LPConstraintBase::verify (const NNormalSurface *s)
| Ensures that the given normal surface satisfies the extra constraints described by this class. More...
static bool | regina::LPConstraintBase::verify (const NAngleStructure *s)
| Ensures that the given angle structure satisfies the extra constraints described by this class. More...
static bool | regina::LPConstraintBase::supported (NormalCoords coords)
| Indicates whether the given coordinate system is supported by this constraint class. More...
template<typename Integer >
void | regina::LPConstraintNone::Coefficients::fillFinalRows (LPMatrix< Integer > &m, unsigned col) const
template<typename Integer >
Integer | regina::LPConstraintNone::Coefficients::innerProduct (const LPMatrix< Integer > &, unsigned) const
template<typename Integer >
Integer | regina::LPConstraintNone::Coefficients::innerProductOct (const LPMatrix< Integer > &, unsigned) const
static bool | regina::LPConstraintNone::addRows (LPInitialTableaux< regina::LPConstraintNone >::Col *, const int *, const NTriangulation *)
template<typename Integer >
static void | regina::LPConstraintNone::constrain (LPData< regina::LPConstraintNone, Integer > &, unsigned)
static bool | regina::LPConstraintNone::verify (const NNormalSurface *)
static bool | regina::LPConstraintNone::verify (const NAngleStructure *)
static bool | regina::LPConstraintNone::supported (NormalCoords coords)
template<typename Integer >
void | regina::LPConstraintEuler::Coefficients::fillFinalRows (LPMatrix< Integer > &m, unsigned col) const
template<typename Integer >
Integer | regina::LPConstraintEuler::Coefficients::innerProduct (const LPMatrix< Integer > &m, unsigned mRow) const
template<typename Integer >
Integer | regina::LPConstraintEuler::Coefficients::innerProductOct (const LPMatrix< Integer > &m, unsigned mRow) const
static bool | regina::LPConstraintEuler::addRows (LPInitialTableaux< regina::LPConstraintEuler >::Col *col, const int *columnPerm, const NTriangulation *tri)
template<typename Integer >
static void | regina::LPConstraintEuler::constrain (LPData< regina::LPConstraintEuler, Integer > &lp, unsigned numCols)
static bool | regina::LPConstraintEuler::verify (const NNormalSurface *s)
static bool | regina::LPConstraintEuler::verify (const NAngleStructure *)
static bool | regina::LPConstraintEuler::supported (NormalCoords coords)
template<typename Integer >
void | regina::LPConstraintNonSpun::Coefficients::fillFinalRows (LPMatrix< Integer > &m, unsigned col) const
template<typename Integer >
Integer | regina::LPConstraintNonSpun::Coefficients::innerProduct (const LPMatrix< Integer > &m, unsigned mRow) const
template<typename Integer >
Integer | regina::LPConstraintNonSpun::Coefficients::innerProductOct (const LPMatrix< Integer > &m, unsigned mRow) const
static bool | regina::LPConstraintNonSpun::addRows (LPInitialTableaux< regina::LPConstraintNonSpun >::Col *col, const int *columnPerm, const NTriangulation *tri)
template<typename Integer >
static void | regina::LPConstraintNonSpun::constrain (LPData< regina::LPConstraintNonSpun, Integer > &lp, unsigned numCols)
static bool | regina::LPConstraintNonSpun::verify (const NNormalSurface *s)
static bool | regina::LPConstraintNonSpun::verify (const NAngleStructure *)
static bool | regina::LPConstraintNonSpun::supported (NormalCoords coords)
| regina::BanConstraintBase::BanConstraintBase (const NTriangulation *tri, int coords)
| Constructs and initialises the banned_ and marked_ arrays to be entirely `false`. More...
| regina::BanConstraintBase::~BanConstraintBase ()
| Destroys this object and all associated data. More...
template<class LPConstraint , typename Integer >
void | regina::BanConstraintBase::enforceBans (LPData< LPConstraint, Integer > &lp) const
| Enforces all bans described by this class in the given tableaux. More...
void | regina::BanConstraintBase::init (const int *columnPerm)
| Identifies which coordinates to ban and mark, and records the corresponding tableaux columns in the banned_ and marked_ arrays respectively. More...
static bool | regina::BanConstraintBase::supported (NormalCoords coords)
| Indicates whether the given coordinate system is supported by this constraint class. More...
| regina::BanNone::BanNone (const NTriangulation *tri, int coords)
| Constructs and initialises the banned_ and marked_ arrays to be entirely `false`, as described in the BanConstraintBase superclass constructor. More...
void | regina::BanNone::init (const int *)
static bool | regina::BanNone::supported (NormalCoords coords)
| regina::BanBoundary::BanBoundary (const NTriangulation *tri, int coords)
| Constructs and initialises the banned_ and marked_ arrays to be entirely `false`, as described in the BanConstraintBase superclass constructor. More...
void | regina::BanBoundary::init (const int *columnPerm)
static bool | regina::BanBoundary::supported (NormalCoords coords)
| regina::BanTorusBoundary::BanTorusBoundary (const NTriangulation *tri, int coords)
| Constructs and initialises the banned_ and marked_ arrays to be entirely `false`, as described in the BanConstraintBase superclass constructor. More...
void | regina::BanTorusBoundary::init (const int *columnPerm)
static bool | regina::BanTorusBoundary::supported (NormalCoords coords)
| regina::LPMatrix< Integer >::LPMatrix ()
| Creates an uninitialised matrix with no memory storage. More...
| regina::LPMatrix< Integer >::LPMatrix (unsigned rows, unsigned cols)
| Creates a fully initialised rows by cols matrix with all elements set to zero. More...
| regina::LPMatrix< Integer >::~LPMatrix ()
| Destroys this matrix and all of the data it contains. More...
void | regina::LPMatrix< Integer >::reserve (unsigned maxRows, unsigned maxCols)
| Reserves enough space to store the elements of a maxRows by maxCols matrix. More...
void | regina::LPMatrix< Integer >::initClone (const LPMatrix &clone)
| Initialises this matrix to a copy of the given matrix. More...
void | regina::LPMatrix< Integer >::initIdentity (unsigned size)
| Initialises this matrix to the identity matrix of the given size. More...
Integer & | regina::LPMatrix< Integer >::entry (unsigned row, unsigned col)
| Returns a read-write reference to the given element of this matrix. More...
const Integer & | regina::LPMatrix< Integer >::entry (unsigned row, unsigned col) const
| Returns a read-only reference to the given element of this matrix. More...
unsigned | regina::LPMatrix< Integer >::rows () const
| Returns the number of rows in this matrix. More...
unsigned | regina::LPMatrix< Integer >::columns () const
| Returns the number of columns in this matrix. More...
void | regina::LPMatrix< Integer >::swapRows (unsigned r1, unsigned r2)
| Swaps the two given rows of this matrix. More...
void | regina::LPMatrix< Integer >::combRow (const Integer &destCoeff, unsigned dest, const Integer &srcCoeff, unsigned src, const Integer &div)
| Applies a particular row operation to this matrix. More...
Integer | regina::LPMatrix< Integer >::combRowAndNorm (const Integer &destCoeff, unsigned dest, const Integer &srcCoeff, unsigned src)
| Applies a particular row operation to this matrix, and then normalises. More...
void | regina::LPMatrix< Integer >::negateRow (unsigned row)
| Negates all elements in the given row of this matrix. More...
void | regina::LPMatrix< Integer >::dump (std::ostream &out) const
| Writes this matrix to the given output stream. More...
| regina::LPInitialTableaux< LPConstraint >::Col::Col ()
| Initialises an empty column. More...
void | regina::LPInitialTableaux< LPConstraint >::Col::push (unsigned row, int val)
| Adds the given entry in the given row to this column. More...
| regina::LPInitialTableaux< LPConstraint >::LPInitialTableaux (const NTriangulation *tri, NormalCoords coords, bool enumeration)
| Construts this adjusted sparse matrix of matching equations. More...
| regina::LPInitialTableaux< LPConstraint >::~LPInitialTableaux ()
| Destroys this matrix. More...
const NTriangulation * | regina::LPInitialTableaux< LPConstraint >::tri () const
| Returns the underlying 3-manifold triangulation from which the matching equations were derived. More...
NormalCoords | regina::LPInitialTableaux< LPConstraint >::coords () const
| Returns the coordinate system that is used for the matrix of matching equations. More...
unsigned | regina::LPInitialTableaux< LPConstraint >::rank () const
| Returns the rank of this matrix. More...
unsigned | regina::LPInitialTableaux< LPConstraint >::columns () const
| Returns the number of columns in this matrix. More...
unsigned | regina::LPInitialTableaux< LPConstraint >::coordinateColumns () const
| Returns the number of columns that correspond to normal coordinates or angle structure coordinates. More...
bool | regina::LPInitialTableaux< LPConstraint >::constraintsBroken () const
| Indicates whether or not the extra constraints from the template parameter LPConstraints were added successfully. More...
const int * | regina::LPInitialTableaux< LPConstraint >::columnPerm () const
| Returns the permutation that describes how the columns of the matching equation matrix were reordered. More...
template<typename Integer >
Integer | regina::LPInitialTableaux< LPConstraint >::multColByRow (const LPMatrix< Integer > &m, unsigned mRow, unsigned thisCol) const
| Computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix. More...
template<typename Integer >
Integer | regina::LPInitialTableaux< LPConstraint >::multColByRowOct (const LPMatrix< Integer > &m, unsigned mRow, unsigned thisCol) const
| A variant of multColByRow() that takes into account any adjustments to the tableaux that are required when this is a quadrilateral column being used to represent an octagon type. More...
template<typename Integer >
void | regina::LPInitialTableaux< LPConstraint >::fillInitialTableaux (LPMatrix< Integer > &m) const
| Fills the given matrix with the contents of this matrix. More...
| regina::LPData< LPConstraint, Integer >::LPData ()
| Constructs a new tableaux. More...
| regina::LPData< LPConstraint, Integer >::~LPData ()
| Destroys this tableaux. More...
void | regina::LPData< LPConstraint, Integer >::reserve (const LPInitialTableaux< LPConstraint > *origTableaux)
| Reserves enough memory for this tableaux to work with. More...
void | regina::LPData< LPConstraint, Integer >::initStart ()
| Initialises this tableaux by beginning at the original starting tableaux and working our way to any feasible basis. More...
void | regina::LPData< LPConstraint, Integer >::initClone (const LPData &parent)
| Initialises this tableaux to be a clone of the given tableaux. More...
unsigned | regina::LPData< LPConstraint, Integer >::columns () const
| Returns the number of columns in this tableaux. More...
unsigned | regina::LPData< LPConstraint, Integer >::coordinateColumns () const
| Returns the number of columns in this tableaux that correspond to normal coordinates or angle structure coordinates. More...
bool | regina::LPData< LPConstraint, Integer >::isFeasible () const
| Returns whether or not this system is feasible. More...
bool | regina::LPData< LPConstraint, Integer >::isActive (unsigned pos) const
| Determines whether the given variable is currently active. More...
int | regina::LPData< LPConstraint, Integer >::sign (unsigned pos) const
| Returns the sign of the given variable under the current basis. More...
void | regina::LPData< LPConstraint, Integer >::constrainZero (unsigned pos)
| Constrains this system further by setting the given variable to zero and deactivating it. More...
void | regina::LPData< LPConstraint, Integer >::constrainPositive (unsigned pos)
| Constrains this system further by constraining the given variable to be strictly positive. More...
void | regina::LPData< LPConstraint, Integer >::constrainOct (unsigned quad1, unsigned quad2)
| Declares that two quadrilateral coordinates within a tetrahedron are to be combined into a single octagon coordinate, for use with almost normal surfaces, and constrains the system accordingly. More...
void | regina::LPData< LPConstraint, Integer >::dump (std::ostream &out) const
| Writes details of this tableaux to the given output stream. More...
void | regina::LPData< LPConstraint, Integer >::extractSolution (NRay &v, const char *type) const
| Extracts the values of the individual variables from the current basis, with some modifications (as described below). More...
static bool | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::supported (NormalCoords coords)
| Indicates whether the given coordinate system is supported by this tree traversal infrastructure. More...
bool | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::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 | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nVisited () const
| Returns the total number of nodes in the search tree that we have visited thus far in the tree traversal. More...
void | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::dumpTypes (std::ostream &out) const
| Writes the current type vector to the given output stream. More...
NNormalSurface * | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::buildSurface () const
| Reconstructs the full normal surface that is represented by the type vector at the current stage of the search. More...
NAngleStructure * | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::buildStructure () const
| Reconstructs the full taut angle structure that is represented by the type vector at the current stage of the search. More...
bool | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::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 | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::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...
| regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::NTreeTraversal (const NTriangulation *tri, NormalCoords coords, int branchesPerQuad, int branchesPerTri, bool enumeration)
| Initialises a new base object for running the tree traversal algorithm. More...
| regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::~NTreeTraversal ()
| Destroys this object. More...
void | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::setNext (int nextType)
| Rearranges the search tree so that nextType becomes the next type that we process. More...
int | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nextUnmarkedTriangleType (int startFrom)
| Returns the next unmarked triangle type from a given starting point. More...
int | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::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 | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::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...
| regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::NTreeEnumeration (const NTriangulation *tri, NormalCoords coords)
| Creates a new object for running the tree traversal algorithm. More...
unsigned long | regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::nSolns () const
| Returns the total number of vertex normal or almost normal surfaces found thus far in the tree traversal search. More...
void | regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::run (bool(*useSoln)(const NTreeEnumeration &, void *), void *arg=0)
| Runs the complete tree traversal algorithm to enumerate vertex normal or almost normal surfaces. More...
bool | regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::next (NProgressTracker *tracker=0)
| An incremental step in the tree traversal algorithm that runs forward until it finds the next solution. More...
static bool | regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::writeTypes (const NTreeEnumeration &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 | regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::writeSurface (const NTreeEnumeration &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...
| regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::NTautEnumeration (const NTriangulation *tri)
| Creates a new object for running the tree traversal algorithm. More...
unsigned long | regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::nSolns () const
| Returns the total number of taut angle structures found thus far in the tree traversal search. More...
void | regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::run (bool(*useSoln)(const NTautEnumeration &, void *), void *arg=0)
| Runs the complete tree traversal algorithm to enumerate all taut angle structures. More...
bool | regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::next (NProgressTracker *tracker=0)
| An incremental step in the enumeration algorithm that runs forward until it finds the next solution. More...
static bool | regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::writeTypes (const NTautEnumeration &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 | regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::writeStructure (const NTautEnumeration &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...
| regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer >::NTreeSingleSoln (const 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 | regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer >::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 | regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer >::cancel ()
| Cancels the current find() operation. More...
| regina::NTypeTrie< nTypes >::NTypeTrie ()
| Initialises an empty trie. More...
| regina::NTypeTrie< nTypes >::~NTypeTrie ()
| Destroys this trie. More...
void | regina::NTypeTrie< nTypes >::clear ()
| Resets this to the empty trie. More...
void | regina::NTypeTrie< nTypes >::insert (const char *entry, unsigned len)
| Inserts the given type vector into this trie. More...
bool | regina::NTypeTrie< nTypes >::dominates (const char *vec, unsigned len) const
| Determines whether the given type vector dominates any vector in this trie. More...

## Variables

int | regina::LPConstraintEuler::Coefficients::euler
| The coefficient of the Euler characteristic function for the corresponding column of the matching equation matrix. More...
int | regina::LPConstraintNonSpun::Coefficients::meridian
| The coefficient of the meridian equation for the corresponding column of the matching equation matrix. More...
int | regina::LPConstraintNonSpun::Coefficients::longitude
| The coefficient of the longitude equation for the corresponding column of the matching equation matrix. More...
const NTriangulation * | regina::BanConstraintBase::tri_
| The triangulation with which we are working. More...
int | regina::BanConstraintBase::coords_
| The normal or almost normal coordinate system in which we are working. More...
bool * | regina::BanConstraintBase::banned_
| Indicates which columns of a tableaux correspond to banned coordinates (e.g., banned normal disc types). More...
bool * | regina::BanConstraintBase::marked_
| Indicates which columns of a tableaux correspond to marked coordinates (e.g., marked normal disc types). More...
unsigned | regina::LPInitialTableaux< LPConstraint >::Col::nPlus
| The total number of +1 entries in this column. More...
unsigned | regina::LPInitialTableaux< LPConstraint >::Col::plus [4]
| The rows containing these +1 entries, in any order. More...
unsigned | regina::LPInitialTableaux< LPConstraint >::Col::nMinus
| The total number of -1 entries in this column. More...
unsigned | regina::LPInitialTableaux< LPConstraint >::Col::minus [4]
| The rows containing these -1 entries, in any order. More...
const LPInitialTableaux< LPConstraint > | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::origTableaux_
| The original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm begins. More...
const NormalCoords | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::coords_
| The coordinate system in which we are enumerating or searching for normal surfaces, almost normal surfaces, or taut angle structures. More...
const int | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nTets_
| The number of tetrahedra in the underlying triangulation. More...
const int | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nTypes_
| The total length of a type vector. More...
const int | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nTableaux_
| The maximum number of tableaux that we need to keep in memory at any given time during the backtracking search. More...
char * | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::type_
| The current working type vector. More...
int * | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::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 | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::level_
| The current level in the search tree. More...
int | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::octLevel_
| The level at which we are enforcing an octagon type (with a strictly positive number of octagons). More...
LPData< LPConstraint, Integer > * | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::lp_
| Stores tableaux for linear programming at various nodes in the search tree. More...
LPData< LPConstraint, Integer > ** | regina::NTreeTraversal< LPConstraint, BanConstraint, 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 > ** | regina::NTreeTraversal< LPConstraint, BanConstraint, 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 | regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nVisited_
| Counts the total number of nodes in the search tree that we have visited thus far. More...
LPData< LPConstraint, Integer > | regina::NTreeTraversal< LPConstraint, BanConstraint, 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...

## Detailed Description

Polytope vertex enumeration algorithms.

## Typedef Documentation

typedef NDoubleDescription regina::NDoubleDescriptor

A legacy typedef provided for backward compatibility only.

Deprecated:
  As of Regina 4.6, the class NDoubleDescriptor has been renamed as NDoubleDescription. This renaming is merely for consistency in documentation and nomenclature; the functionality of the new NDoubleDescription class is identical to the old NDoubleDescriptor class as it was in Regina 4.5.1. This typedef is provided for backward compatibility, and will be removed in some future version of Regina.

## Enumeration Type Documentation

anonymous enum

Enumerator
nConstraints | The number of additional linear constraints that we impose. Each constraint will generate one new variable (column) and one new equation (row) in the tableaux.

## Function Documentation

static bool regina::LPConstraintBase::addRows | ( | LPInitialTableaux< LPConstraintBase >::Col * | col,
|  | const int * | columnPerm,
|  | const NTriangulation * | tri
| ) |  |

static

Explicitly constructs equations for the linear function(s) constrained by this class.

Specifically, this routine takes an array of Coefficients objects (one for each column of the initial tableaux) and fills in the necessary coefficient data.

The precise form of the linear function(s) will typically depend upon the underlying triangulation. For this reason, the triangulation is explicitly passed, along with the permutation that indicates which columns of the initial tableaux correspond to which normal or angle structure coordinates.

More precisely: recall that, for each linear function, the initial tableaux acquires one new variable x_i that evaluates this linear function f(x). This routine must create the corresponding row that sets `f(x) - x_i = 0`. Thus it must construct the coefficients of f(x) in the columns corresponding to normal coordinates, and it must also set a coefficient of -1 in the column for the corresponding new variable.

For each subclass S of LPConstraintBase, the array col must be an array of objects of type LPInitialTableaux<S>::Col. The class LPInitialTableaux<S>::Col is itself a larger subclass of the Coefficients class. This exact type must be used because the compiler must know how large each column object is in order to correct access each element of the given array.

As described in the LPInitialTableaux class notes, it might not be possible to construct the linear functions (since the triangulation might not satisfy the necessary requirements). In this case, this routine should ensure that the linear functions are in fact the zero functions, and should return `false` (but it must still set -1 coefficients for the new variables as described above). Otherwise (if the linear function were successfully constructed) this routine should return `true`.

If you are implementing this routine in a subclass that works with angle structure coordinates, remember that your linear constraints must not interact with the scaling coordinate (the final angle structure coordinate that is used to projectivise the angle structure polytope into a polyhedral cone). Your implementation of this routine must ensure that your linear constraints all have coefficient zero in this column.

Precondition
  For all coefficients in the array col, the Coefficients substructures have all been initialised with the default constructor and not modified since.

Parameters

  col | the array of columns as stored in the initial tableaux (i.e., the data member LPInitialTableaux::col_).
  columnPerm | the corresponding permutation of columns that describes how columns of the tableaux correspond to normal or angle structure coordinates in the underlying triangulation (i.e., the data member LPInitialTableaux::columnPerm_).
  tri | the underlying triangulation.

Returns
  `true` if the linear functions were successfully constructed, or `false` if not (in which case they will be replaced with the zero functions instead).

regina::BanBoundary::BanBoundary | ( | const NTriangulation * | tri,
|  | int | coords
| ) |  |

inline protected

Constructs and initialises the banned_ and marked_ arrays to be entirely `false`, as described in the BanConstraintBase superclass constructor.

Warning
  Before you use this object, the routine init() must be called to fill in the banned_ and marked_ arrays with the correct data. Otherwise you will have no banned or marked disc types at all.

Parameters

  tri | the triangulation with which we are working.
  coords | the normal or almost normal coordinate system in which we are working. This must be one of NS_QUAD, NS_STANDARD, NS_AN_QUAD_OCT, or NS_AN_STANDARD.

regina::BanConstraintBase::BanConstraintBase | ( | const NTriangulation * | tri,
|  | int | coords
| ) |  |

protected

Constructs and initialises the banned_ and marked_ arrays to be entirely `false`.

The only purpose of passing the triangulation and coordinate system is to determine how many normal or angle structure coordinates we are dealing with.

Warning
  Before you use this object, the routine init() must be called to fill in the banned_ and marked_ arrays with the correct data. Otherwise you will have no banned or marked disc types at all.

Parameters

  tri | the triangulation with which we are working.
  coords | the coordinate system in which we are working. This must be one of NS_QUAD, NS_STANDARD, NS_AN_QUAD_OCT, NS_AN_STANDARD, or NS_ANGLE.

regina::BanNone::BanNone | ( | const NTriangulation * | tri,
|  | int | coords
| ) |  |

inline protected

Constructs and initialises the banned_ and marked_ arrays to be entirely `false`, as described in the BanConstraintBase superclass constructor.

Although one should normally call the routine init() before using this object, for BanNone this is not strictly necessary since there are no coordinates to ban or mark.

Parameters

  tri | the triangulation with which we are working.
  coords | the coordinate system in which we are working. This must be one of NS_QUAD, NS_STANDARD, NS_AN_QUAD_OCT, NS_AN_STANDARD, or NS_ANGLE.

regina::BanTorusBoundary::BanTorusBoundary | ( | const NTriangulation * | tri,
|  | int | coords
| ) |  |

inline protected

Constructs and initialises the banned_ and marked_ arrays to be entirely `false`, as described in the BanConstraintBase superclass constructor.

Warning
  Before you use this object, the routine init() must be called to fill in the banned_ and marked_ arrays with the correct data. Otherwise you will have no banned or marked disc types at all.

Parameters

  tri | the triangulation with which we are working.
  coords | the normal or almost normal coordinate system in which we are working. This must be one of NS_QUAD, NS_STANDARD, NS_AN_QUAD_OCT, or NS_AN_STANDARD.

template<class LPConstraint , typename BanConstraint , typename Integer >

NAngleStructure* regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::buildStructure | ( |  | ) | const

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 NTautEnumeration::next() returns `true`, or any time that NTautEnumeration::run() calls its callback function.
  We are working with angle structure coordinates; that is, the coordinate system passed to the NTreeTraversal constructor was NS_ANGLE.

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

template<class LPConstraint , typename BanConstraint , typename Integer >

NNormalSurface* regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::buildSurface | ( |  | ) | const

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 NTreeSingleSoln::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 NTreeEnumeration::next() or NTreeSingleSoln::find() returns `true`, or any time that NTreeEnumeration::run() calls its callback function.
  We are working with normal or almost normal surfaces. That is, the coordinate system passed to the NTreeTraversal constructor was not NS_ANGLE.

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

template<class LPConstraint , typename BanConstraint , typename Integer >

void regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer >::cancel | ( |  | ) |

inline

Cancels the current find() operation.

This may be called from another thread (it is thread-safe). If called, it signals that if find() is currently running then it should be cancelled at the earliest convenient opportunity.

template<int nTypes>

void regina::NTypeTrie< nTypes >::clear | ( |  | ) |

inline

Resets this to the empty trie.

regina::LPConstraintBase::Coefficients::Coefficients | ( |  | ) |

Creates an uninitialised set of coefficients for a single column.

These cofficients must be initialised through a call to addRows() before they can be used.

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::Col::Col | ( |  | ) |

inline

Initialises an empty column.

template<class LPConstraint >

const int * regina::LPInitialTableaux< LPConstraint >::columnPerm | ( |  | ) | const

inline

Returns the permutation that describes how the columns of the matching equation matrix were reordered.

This permutation maps column numbers in this adjusted matching equation matrix to column numbers in the original (unmodified) matching equation matrix that was originally derived from the triangulation.

The permutation is returned as an array of columns() integers, such that column i of this adjusted matrix corresponds to column `columnPerm()[i]` of the original matrix.

If you are imposing additional constraints through the template parameter LPConstraint, then the corresponding extra variables will be included in the permutation; however, these are never moved and will always remain the rightmost variables in this system (i.e., the columns of highest index).

As well as the requirement that this is a genuine permutation of 0,...,columns()-1, this array will also adhere to the following constraints. In the following discussion, n refers to the number of tetrahedra in the underlying triangulation.

- The quadrilateral coordinate columns must appear as the first 3n columns of the adjusted matrix. In particular, when working in the 7n-dimensional standard normal coordinate system, the remaining 4n triangle coordinate columns must appear last.
- The quadrilateral coordinate columns must be grouped by tetrahedron and ordered by quadrilateral type. In other words, for each i = 0,...,n-1, there will be some tetrahedron j for which the three columns 3i, 3i+1 and 3i+2 refer to the quadrilaterals in tetrahedron j of types 0, 1 and 2 respectively. Phrased loosely, we are allowed to reorder the tetrahedra, but not the quadrilateral coordinates within each tetrahedron.
- The triangle coordinate columns (if we are working in standard normal coordinates) must likewise be grouped by tetrahedron, and these tetrahedra must appear in the same order as for the quadrilateral types. In other words, for each i = 0,...,n-1, the quadrilateral columns 3i, 3i+1 and 3i+2 and the triangle columns 3n+4i, 3n+4i+1, 3n+4i+2 and 3n+4i+3 all refer to the same tetrahedron.
- For angle structure coordinates, the constraints are analogous to those for quadrilateral coordinates: the angle coordinates must be grouped by tetrahedron and ordered by angle type, and the final scaling coordinate must remain last.

Returns
  details of the permutation describing how columns were reordered.

template<typename Integer >

unsigned regina::LPMatrix< Integer >::columns | ( |  | ) | const

inline

Returns the number of columns in this matrix.

This relates to the currently assigned matrix size, not the total amount of memory that was originally reserved.

Returns
  the number of columns.

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::columns | ( |  | ) | const

inline

Returns the number of columns in this matrix.

Note that, if we are imposing extra constraints through the template parameter LPConstraint, then there will be extra variables to enforce these, and so the number of columns will be larger than in the original matching equation matrix.

Returns
  the number of columns.

template<class LPConstraint , typename Integer >

unsigned regina::LPData< LPConstraint, Integer >::columns | ( |  | ) | const

inline

Returns the number of columns in this tableaux.

Note that, if we are imposing extra constraints through the template parameter LPConstraint, then there will be extra variables to enforce these, and so the number of columns will be larger than in the original matching equation matrix.

Returns
  the number of columns.

template<typename Integer >

void regina::LPMatrix< Integer >::combRow | ( | const Integer & | destCoeff,
|  | unsigned | dest,
|  | const Integer & | srcCoeff,
|  | unsigned | src,
|  | const Integer & | div
| ) |  |

inline

Applies a particular row operation to this matrix.

Specifically, row dest will be replaced with the linear combination: (destCoeff * row dest - srcCoeff * row src) / div.

Precondition
  dest and src are not equal.
  It is known in advance that every integer in (destCoeff * row dest - srcCoeff * row src) will be divisible by div. In other words, it is known in advance that we can use exact integer division without remainders.

Parameters

  destCoeff | the coefficient applied to row dest in the linear combination.
  dest | the index of the row to replace. This must be between 0 and rows()-1 inclusive.
  srcCoeff | the coefficient applied to row src in the linear combination.
  src | the index of the other row used in this linear combination. This must be between 0 and rows()-1 inclusive.
  div | the integer to divide the final row by. This must be non-zero.

template<typename Integer >

Integer regina::LPMatrix< Integer >::combRowAndNorm | ( | const Integer & | destCoeff,
|  | unsigned | dest,
|  | const Integer & | srcCoeff,
|  | unsigned | src
| ) |  |

inline

Applies a particular row operation to this matrix, and then normalises.

Specifically, row dest will be replaced with the linear combination: (destCoeff * row dest - srcCoeff * row src); then, if row dest is non-zero, it will be normalised by dividing through by the gcd of its elements. Note that this gcd is always taken to be positive (i.e., the final normalisation will never change the signs of the elements in the row).

Precondition
  dest and src are not equal.

Parameters

  destCoeff | the coefficient applied to row dest in the linear combination.
  dest | the index of the row to replace. This must be between 0 and rows()-1 inclusive.
  srcCoeff | the coefficient applied to row src in the linear combination.
  src | the index of the other row used in this linear combination. This must be between 0 and rows()-1 inclusive.

Returns
  the positive gcd that row dest was scaled down by, or 0 if row dest is entirely zero.

template<typename Integer >

static void regina::LPConstraintBase::constrain | ( | LPData< LPConstraintNone, Integer > & | lp,
|  | unsigned | numCols
| ) |  |

static

Explicitly constraints each of these linear functions to an equality or inequality in the underlying tableaux.

This will typically consist of a series of calls to LPData::constrainZero() and/or LPData::constrainPositive().

The variables for these extra linear functions are stored in columns `numCols - nConstraints`, ..., `numCols - 1` of the given tableaux, and so your calls to LPData::constrainZero() and/or LPData::constrainPositive() should operate on these (and only these) columns.

Precondition
  These column coefficients belong to the initial starting tableaux (LPInitialTableaux) from which the given tableaux is derived.

Parameters

  lp | the tableaux in which to constrain these linear functions.
  numCols | the number of columns in the given tableaux.

template<class LPConstraint , typename Integer >

void regina::LPData< LPConstraint, Integer >::constrainOct | ( | unsigned | quad1,
|  | unsigned | quad2
| ) |  |

Declares that two quadrilateral coordinates within a tetrahedron are to be combined into a single octagon coordinate, for use with almost normal surfaces, and constrains the system accordingly.

This constrains the system in several ways, as discussed in detail in the LPData class notes. In theory, we set the two quadrilateral coordinates to be equal, and also insist that the number of octagons be strictly positive. In practice, we do this through several changes of variable; see the LPData class notes for a detailed discussion of precisely how the variables and tableaux will change.

This routine will work even if one of the given quadrilateral variables has already been deactivated, but in this case the routine will immediately set the system to infeasible and return.

This routine is not used with angle structure coordinates.

Precondition
  This is the first time constrainOct() has been called on this tableaux. This is because this class can only handle one octagon type in the entire system.
  Variables quad1 and quad2 represent different quadrilateral coordinates in the same tetrahedron of the underlying triangulation.

Warning
  If you have previously called constrainPositive() or constrainOct() on one of the given variables, then these prior routines will have performed a change of variable. Any new call to constrainOct() involving this same variable will constrain the new variable, not the original, and so might not have the intended effect.

Parameters

  quad1 | one of the two quadrilateral types that we combine to form the new octagon type.
  quad2 | the other of the two quadrilateral types that we combine to form the new octagon type.

template<class LPConstraint , typename Integer >

void regina::LPData< LPConstraint, Integer >::constrainPositive | ( | unsigned | pos | ) |

Constrains this system further by constraining the given variable to be strictly positive.

We do this using a change of variable that effectively replaces x_pos with the new variable x'_pos = x_pos - 1 (which we simply constrain to be non-negative as usual). See the LPData class notes for details.

This routine will work even if the given variable has already been deactivated, but in this case the routine will immediately set the system to infeasible and return.

Warning
  If you have previously called constrainPositive() or constrainOct() on this variable, then these prior routines will have performed a change of variable. Any new call to constrainPositive() on this same variable will constrain the new variable, not the original, and so might not have the intended effect.

Parameters

  pos | the index of the variable that is to be constrained as positive. This must be between 0 and origTableaux_->columns()-1 inclusive.

template<class LPConstraint , typename BanConstraint , typename Integer >

bool regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::constraintsBroken | ( |  | ) | const

inline

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

template<class LPConstraint >

bool regina::LPInitialTableaux< LPConstraint >::constraintsBroken | ( |  | ) | const

inline

Indicates whether or not the extra constraints from the template parameter LPConstraints were added successfully.

This query function is important because some constraints require additional preconditions on the underlying triangulation, and cannot be added if these preconditions are not satisfied.

Even if the extra constraints were not added successfully, this tableaux will be left in a consistent state (the extra constraints will be treated as zero functions). See the LPInitialTableaux class notes for further details.

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

template<class LPConstraint , typename Integer >

void regina::LPData< LPConstraint, Integer >::constrainZero | ( | unsigned | pos | ) |

Constrains this system further by setting the given variable to zero and deactivating it.

See the LPData class notes for details.

This routine will work even if the given variable has already been deactivated (and it will do nothing in this case).

Warning
  If you have previously called constrainPositive() or constrainOct() on this variable, then these prior routines will have performed a change of variable. Any new call to constraintZero() on this same variable will constraint the new variable, not the original, and so might not have the intended effect.

Parameters

  pos | the index of the variable that is to be set to zero. This must be between 0 and origTableaux_->columns()-1 inclusive.

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::coordinateColumns | ( |  | ) | const

inline

Returns the number of columns that correspond to normal coordinates or angle structure coordinates.

This is precisely the number of columns in the original matrix of matching equations.

Returns
  the number of normal or angle structure coordinate columns.

template<class LPConstraint , typename Integer >

unsigned regina::LPData< LPConstraint, Integer >::coordinateColumns | ( |  | ) | const

inline

Returns the number of columns in this tableaux that correspond to normal coordinates or angle structure coordinates.

This is precisely the number of columns in the original matrix of matching equations.

Returns
  the number of normal or angle structure coordinate columns.

template<class LPConstraint >

NormalCoords regina::LPInitialTableaux< LPConstraint >::coords | ( |  | ) | const

inline

Returns the coordinate system that is used for the matrix of matching equations.

This will be the same coordinate system that was passed to the LPInitialTableaux constructor; in particular, it will always be one of NS_QUAD, NS_STANDARD, or NS_ANGLE.

Returns
  the coordinate system.

template<int nTypes>

bool regina::NTypeTrie< nTypes >::dominates | ( | const char * | vec,
|  | unsigned | len
| ) |  | const

Determines whether the given type vector dominates any vector in this trie.

Precondition
  The given length len is non-zero, and is fixed throughout the life of this trie; that is, it is the same every time insert() or dominates() is called.

Parameters

  vec | the type vector to test.
  len | the number of elements in the given type vector.

Returns
  `true` if and only if vec dominates some type vector stored in this trie.

template<typename Integer >

void regina::LPMatrix< Integer >::dump | ( | std::ostream & | out | ) | const

Writes this matrix to the given output stream.

The output is "rough" and wasteful, and is intended for debugging purposes only. The precise output format is subject to change in future versions of Regina.

Parameters

  out | the output stream to write to.

template<class LPConstraint , typename Integer >

void regina::LPData< LPConstraint, Integer >::dump | ( | std::ostream & | out | ) | const

Writes details of this tableaux to the given output stream.

The output is "rough" and wasteful, and is intended for debugging purposes only.

The precise output is subject to change in future versions of Regina.

Parameters

  out | the output stream to write to.

template<class LPConstraint , typename BanConstraint , typename Integer >

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

inline

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.

template<class LPConstraint , typename Integer >

void regina::BanConstraintBase::enforceBans | ( | LPData< LPConstraint, Integer > & | lp | ) | const

inline protected

Enforces all bans described by this class in the given tableaux.

Specifically, for each banned coordinate, this routine calls LPData::constrainZero() on the corresponding coordinate column.

Parameters

  lp | the tableaux in which to enforce the bans.

template<typename Integer >

Integer & regina::LPMatrix< Integer >::entry | ( | unsigned | row,
|  | unsigned | col
| ) |  |

inline

Returns a read-write reference to the given element of this matrix.

Parameters

  row | the row of the requested element. This must be between 0 and rows()-1 inclusive.
  col | the column of the requested element. This must be between 0 and columns()-1 inclusive.

template<typename Integer >

const Integer & regina::LPMatrix< Integer >::entry | ( | unsigned | row,
|  | unsigned | col
| ) |  | const

inline

Returns a read-only reference to the given element of this matrix.

Parameters

  row | the row of the requested element. This must be between 0 and rows()-1 inclusive.
  col | the column of the requested element. This must be between 0 and columns()-1 inclusive.

template<class LPConstraint , typename Integer >

void regina::LPData< LPConstraint, Integer >::extractSolution | ( | NRay & | v,
|  | const char * | type
| ) |  | const

Extracts the values of the individual variables from the current basis, with some modifications (as described below).

The values of the variables are store in the given vector v.

The modifications are as follows:

- We extract variables that correspond to the original matching equations obtained from the underlying triangulation, not the current tableaux and not even the original starting tableaux stored in origTableaux_. In other words, when we fill the vector v we undo the column permutation described by LPInitialTableaux::columnPerm(), and we undo any changes of variable that were caused by calls to constrainPositive() and/or constrainOct().
- To ensure that the variables are all integers, we scale the final vector by the smallest positive rational multiple for which all elements of the vector are integers. (This is why the output class is NRay and not NVector.)

This routine is not used as an internal part of the tree traversal algorithm; instead it is offered as a helper routine for reconstructing the normal surfaces or angle structures that result.

Precondition
  The given vector v has been initialised to the zero vector of length origTableaux_->columns(). Note that the NRay constructor will automatically initialise all elements to zero as required.
  No individual coordinate column has had more than one call to either of constrainPositive() or constrainOct() (otherwise the coordinate will not be correctly reconstructed). Any additional columns arising from LPConstraint are exempt from this requirement.

Parameters

  v | the vector into which the values of the variables will be placed.

  type

  the type vector corresponding to the current state of this tableaux, indicating which variables were previously fixed as positive via calls to constrainPositive(). This is necessary because LPData does not keep such historical data on its own. As a special case, when extracting a strict angle structure one may pass type = 0, in which case this routine will assume that every coordinate was constrained as positive.

template<class LPConstraint , typename BanConstraint , typename Integer >

int regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::feasibleBranches | ( | int | quadType | ) |

protected

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 NTreeEnumeration, not merged together as in NTreeSingleSoln.

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.

template<typename Integer >

void regina::LPConstraintBase::Coefficients::fillFinalRows | ( | LPMatrix< Integer > & | m,
|  | unsigned | col
| ) |  | const

Explicitly fills the final row(s) of the given tableaux matrix with the coefficients stored in this Coefficients structure.

In essence, this routine simply copies this sparse and/or specialised representation of the final row(s) into a more standard dense matrix representation.

This routine should only affect the final nConstraints entries in the given column of the matrix. It may assume that these final row(s) have already been initialised to zero.

Precondition
  The given matrix has at least nConstraints rows and at least col + 1 columns.
  The final nConstraints entries in column col of the given matrix have already been set to zero.

Parameters

  m | the matrix in which to place these column coefficients.
  col | the column of the given matrix in which to place these coefficients.

template<class LPConstraint >
template<typename Integer >

void regina::LPInitialTableaux< LPConstraint >::fillInitialTableaux | ( | LPMatrix< Integer > & | m | ) | const

inline

Fills the given matrix with the contents of this matrix.

This effectively copies this sparse but highly specialised matrix representation into a dense but more flexible matrix representation.

Precondition
  The given matrix has already been initialised to size rank() * columns(), and all of its elements have already been set to zero. Note that this can all be arranged by calling the constructor LPMatrix::LPMatrix(unsigned, unsigned).

Parameters

  m | the matrix to fill.

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

bool regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer >::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.

Note that, if a solution is found, it will have a maximal (but not necessarily maximum) set of zero coordinates, which in some settings is enough to guarantee a vertex normal surface. See the NTreeSingleSoln class notes for details.

If find() does return `true`, you can extract details of the corresponding surface directly from this tree enumeration object: for instance, you can dump the type vector using dumpTypes(), or you can reconstruct the full surface using buildSurface(). Be warned that this class defines the type vector in an unusual way (see the NTreeSingleSoln class notes for details). If you call buildSurface(), remember to delete the surface once you are finished with it.

Precondition
  The algorithm has not yet been run, i.e., you have not called find() before.

Returns
  `true` if we found a non-trivial solution as described in the class notes, or `false` if no such solution exists.

void regina::BanConstraintBase::init | ( | const int * | columnPerm | ) |

protected

Identifies which coordinates to ban and mark, and records the corresponding tableaux columns in the banned_ and marked_ arrays respectively.

Parameters

  columnPerm | the permutation of columns that describes how columns of the tableaux correspond to normal or angle strutcure coordinates in the underlying triangulation. Specifically, this permutation must be the same permutation returned by LPInitialTableaux::columnPerm().

template<typename Integer >

void regina::LPMatrix< Integer >::initClone | ( | const LPMatrix< Integer > & | clone | ) |

inline

Initialises this matrix to a copy of the given matrix.

This matrix does not yet need to be initialised, but it does need to have enough space reserved.

You may call this routine on an already-initialised matrix, and you may use this routine to assign it a different size (as long as enough space was originally reserved).

Precondition
  If this matrix has not been initialised before, then reserve() must have already been called.
  This matrix has enough space reserved for at least clone.rows() * clone.columns() elements.

Parameters

  clone | the matrix to copy.

template<class LPConstraint , typename Integer >

void regina::LPData< LPConstraint, Integer >::initClone | ( | const LPData< LPConstraint, Integer > & | parent | ) |

Initialises this tableaux to be a clone of the given tableaux.

This is used in the tree traversal algorithm as we work our way down the search tree, and child nodes "inherit" tableaux from their parent nodes.

Precondition
  reserve() has already been called.

Parameters

  parent | the tableaux to clone.

template<typename Integer >

void regina::LPMatrix< Integer >::initIdentity | ( | unsigned | size | ) |

inline

Initialises this matrix to the identity matrix of the given size.

This matrix does not yet need to be initialised, but it does need to have enough space reserved.

You may call this routine on an already-initialised matrix, and you may use this routine to assign it a different size (as long as enough space was originally reserved).

Precondition
  If this matrix has not been initialised before, then reserve() must have already been called.
  This matrix has enough space reserved for at least size * size elements.

Parameters

  size | the number of rows, and also the number of columns, that will be assigned to this matrix. This must be strictly positive.

template<class LPConstraint , typename Integer >

void regina::LPData< LPConstraint, Integer >::initStart | ( |  | ) |

Initialises this tableaux by beginning at the original starting tableaux and working our way to any feasible basis.

This routine also explicitly enforces the additional constraints from the template parameter LPConstraint (i.e., this routine is responsible for forcing the corresponding linear function(s) to be zero or strictly positive as appropriate).

It is possible that a feasible basis cannot be found; you should test isFeasible() after running this routine to see whether this is the case.

Precondition
  reserve() has already been called.

template<typename Integer >

Integer regina::LPConstraintBase::Coefficients::innerProduct | ( | const LPMatrix< Integer > & | m,
|  | unsigned | mRow
| ) |  | const

Computes the inner product of (i) the final nConstraints entries in the given row of the given matrix with (ii) the nConstraints column coefficients stored in this data structure.

Precondition
  The given matrix has at least nConstraints columns and at least mRow + 1 rows.

Parameters

  m | the matrix whose row we will use in the inner product.
  mRow | the row of the matrix m to use in the inner product.

Returns
  the resulting portion of the inner product.

template<typename Integer >

Integer regina::LPConstraintBase::Coefficients::innerProductOct | ( | const LPMatrix< Integer > & | m,
|  | unsigned | mRow
| ) |  | const

A variant of innerProduct() that takes into account any adjustments to these linear constraint(s) that are required when this is a quadrilateral column being used to represent an octagon type.

The LPData class offers support for octagonal almost normal surfaces, in which exactly one tetrahedron is allowed to have exactly one octagon type. We represent such an octagon as a pair of incompatible quadrilaterals within the same tetrahedron. See the LPData class notes for details on how this works.

In some settings, our extra linear constraints must behave differently in the presence of octagons (i.e., the coefficient of the octagon type is not just the sum of coefficients of the two constituent quadrilateral types). This routine effectively allows us to adjust the tableaux accordingly.

Specifically: this routine computes the inner product of (i) the final nConstraints entries in the given row of the given matrix with (ii) the nConstraints column coefficients stored in this data structure. We assume that this column in the underlying tableaux describes one of the two quadrilateral coordinates in some tetrahedron that together form an octagon type, and if necessary we implicitly adjust the coefficients stored in this data structure accordingly.

This routine is not used with angle structure coordinates.

Precondition
  The given matrix has at least nConstraints columns and at least mRow + 1 rows.
  This column of the underlying tableaux describes one of the two quadrilateral coordinates that are being combined to form an octagon type within some tetrahedron.

Parameters

  m | the matrix whose row we will use in the inner product.
  mRow | the row of the matrix m to use in the inner product.

Returns
  the resulting portion of the inner product.

template<int nTypes>

void regina::NTypeTrie< nTypes >::insert | ( | const char * | entry,
|  | unsigned | len
| ) |  |

Inserts the given type vector into this trie.

Precondition
  The given length len is non-zero, and is fixed throughout the life of this trie; that is, it is the same every time insert() or dominates() is called.

Parameters

  entry | the type vector to insert.
  len | the number of elements in the given type vector.

template<class LPConstraint , typename Integer >

bool regina::LPData< LPConstraint, Integer >::isActive | ( | unsigned | pos | ) | const

inline

Determines whether the given variable is currently active.

See the LPData class notes for details.

Parameters

  pos | the index of the variable to query. This must be between 0 and origTableaux_->columns()-1 inclusive.

template<class LPConstraint , typename Integer >

bool regina::LPData< LPConstraint, Integer >::isFeasible | ( |  | ) | const

inline

Returns whether or not this system is feasible.

A system may become infeasible when we add too many extra constraints on the variables (such as forcing them to be positive, or setting them to zero); see the LPData class notes for details on these constraints.

Warning
  As explained in the class notes, if this system is infeasible then any queries or operations (other than calling isFeasible() itself) are undefined.

Returns
  `true` if this system is feasible, or `false` if it is infeasible.

template<class LPConstraint , typename Integer >

regina::LPData< LPConstraint, Integer >::LPData | ( |  | ) |

inline

Constructs a new tableaux.

You must call reserve() before doing anything else with this tableaux.

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::LPInitialTableaux | ( | const NTriangulation * | tri,
|  | NormalCoords | coords,
|  | bool | enumeration
| ) |  |

Construts this adjusted sparse matrix of matching equations.

Precondition
  The given triangulation is non-empty.

Parameters

  tri | the underlying 3-manifold triangulation.
  coords | the coordinate system to use for the matrix of matching equations; this must be one of NS_QUAD, NS_STANDARD, or NS_ANGLE.
  enumeration | `true` if we should optimise the tableaux for a full enumeration of vertex surfaces or taut angle structures, or `false` if we should optimise the tableaux for an existence test (such as searching for a non-trivial normal disc or sphere, or a strict angle structure).

template<typename Integer >

regina::LPMatrix< Integer >::LPMatrix | ( |  | ) |

inline

Creates an uninitialised matrix with no memory storage.

You must call reserve() and then either initClone() or initIdentity() before this matrix will become initialised.

template<typename Integer >

regina::LPMatrix< Integer >::LPMatrix | ( | unsigned | rows,
|  | unsigned | cols
| ) |  |

inline

Creates a fully initialised rows by cols matrix with all elements set to zero.

This routine reserves space for precisely rows * cols elements. In other words, you may later re-initialise the matrix to become smaller if you like, but you cannot re-initialise the matrix to become larger.

Parameters

  rows | the number of rows in the new matrix. This must be strictly positive.
  cols | the number of columns in the new matrix. This must be strictly positive.

template<class LPConstraint >
template<typename Integer >

Integer regina::LPInitialTableaux< LPConstraint >::multColByRow | ( | const LPMatrix< Integer > & | m,
|  | unsigned | mRow,
|  | unsigned | thisCol
| ) |  | const

inline

Computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix.

This routine is optimised to use the sparse representation of columns in this matrix.

Precondition
  The given matrix m has precisely rank() columns.

Parameters

  m | the matrix whose row we will use in the inner product.
  mRow | the row of the matrix m to use in the inner product.
  thisCol | the column of this matrix to use in the inner product.

Returns
  the resulting inner product.

template<class LPConstraint >
template<typename Integer >

Integer regina::LPInitialTableaux< LPConstraint >::multColByRowOct | ( | const LPMatrix< Integer > & | m,
|  | unsigned | mRow,
|  | unsigned | thisCol
| ) |  | const

inline

A variant of multColByRow() that takes into account any adjustments to the tableaux that are required when this is a quadrilateral column being used to represent an octagon type.

The LPData class offers support for octagonal almost normal surfaces, in which exactly one tetrahedron is allowed to have exactly one octagon type. We represent such an octagon as a pair of incompatible quadrilaterals within the same tetrahedron. See the LPData class notes for details on how this works.

In some settings where we are using additional constraints through the template parameter LPConstraint, these extra constraints behave differently in the presence of octagons (i.e., the coefficient of the octagon type is not just the sum of coefficients of the two constituent quadrilateral types). This routine effectively allows us to adjust the tableaux accordingly.

Specifically: this routine computes the inner product of (i) the given row of the given matrix with (ii) the given column of this matrix. We assume that the given column of this matrix describes one of the two quadrilateral coordinates in some tetrahedron that together form an octagon type, and (via the helper routine LPConstraint::Coefficients::innerProductOct) we implicitly adjust the coefficients of our extra constraints accordingly.

This routine is optimised to use the sparse representation of columns in this matrix.

This routine is not used with angle structure coordinates.

Precondition
  The given matrix m has precisely rank() columns.
  Column thisCol of this matrix describes one of the two quadrilateral coordinates that are being combined to form an octagon type within some tetrahedron.

Parameters

  m | the matrix whose row we will use in the adjusted inner product.
  mRow | the row of the matrix m to use in the adjusted inner product.
  thisCol | the column of this matrix to use in the adjusted inner product.

Returns
  the resulting adjusted inner product.

template<typename Integer >

void regina::LPMatrix< Integer >::negateRow | ( | unsigned | row | ) |

inline

Negates all elements in the given row of this matrix.

Parameters

  row | the row whose elements should be negated. This must be between 0 and rows()-1 inclusive.

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

bool regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::next | ( | NProgressTracker * | 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 NProgressTracker::newStage() before this routine is called, and that NProgressTracker::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.

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

bool regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::next | ( | NProgressTracker * | tracker = `0` | ) |

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

Specifically: this continues the enumeration from the current point until either it finds the next taut angle structure (in which case it returns `true`), or until the enumeration algorithm 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 taut angle structures, 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 enumeration object: for instance, you can dump the type vector using dumpTypes(), or you can reconstruct the full taut angle structure using buildStructure() and perform some other operations upon it. If you do call buildStructure(), remember to delete the angle structure 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 NProgressTracker::newStage() before this routine is called, and that NProgressTracker::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 enumeration 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 taut angle strutures were found.

template<class LPConstraint , typename BanConstraint , typename Integer >

int regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nextUnmarkedTriangleType | ( | int | startFrom | ) |

inline protected

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

template<class LPConstraint , typename BanConstraint , typename Integer >

unsigned long regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::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.

template<class LPConstraint , typename BanConstraint , typename Integer >

unsigned long regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::nSolns | ( |  | ) | const

inline

Returns the total number of taut angle structures found thus far in the tree traversal search.

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

Returns
  the number of solutions found so far.

template<class LPConstraint , typename BanConstraint , typename Integer >

regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::NTautEnumeration | ( | const NTriangulation * | tri | ) |

inline

Creates a new object for running the tree traversal algorithm.

This prepares the algorithm; in order to run the algorithm and enumerate taut angle structures, you can either:

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

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

Parameters

  tri | the triangulation in which we wish to enumerate taut angle structures.

template<class LPConstraint , typename BanConstraint , typename Integer >

regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::NTreeEnumeration | ( | const NTriangulation * | 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.

template<class LPConstraint , typename BanConstraint , typename Integer >

regina::NTreeSingleSoln< LPConstraint, BanConstraint, Integer >::NTreeSingleSoln | ( | const NTriangulation * | tri,
|  | NormalCoords | coords
| ) |  |

inline

Creates a new object for running the tree traversal / branching algorithm to locate a non-trivial surface that satisfies the chosen constraints.

This constructor prepares the algorithm; in order to run the algorithm you should call find(), which returns `true` or `false` according to whether or not such a surface was found.

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 search for a non-trivial surface.
  coords | the normal or almost normal coordinate system in which to work. This must be one of NS_QUAD, NS_STANDARD, NS_AN_QUAD_OCT, or NS_AN_STANDARD.

template<class LPConstraint , typename BanConstraint , typename Integer >

regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::NTreeTraversal | ( | const NTriangulation * | tri,
|  | NormalCoords | coords,
|  | int | branchesPerQuad,
|  | int | branchesPerTri,
|  | bool | enumeration
| ) |  |

protected

Initialises a new base object for running the tree traversal algorithm.

This routine may only be called by subclass constructors; for more information on how to create and run a tree traversal, see subclasses such as NTreeEnumeration, NTautEnumeration or NTreeSingleSoln instead.

Precondition
  The given triangulation is non-empty.

Parameters

  tri | the triangulation in which we wish to search for normal surfaces or taut angle structures.
  coords | the coordinate system in which wish to search for normal surfaces or taut angle structures. This must be one of NS_QUAD, NS_STANDARD, NS_AN_QUAD_OCT, NS_AN_STANDARD, or NS_ANGLE.
  branchesPerQuad | the maximum number of branches we spawn in the search tree for each quadrilateral or angle type (e.g., 4 for a vanilla normal surface tree traversal algorithm, or 3 for enumerating taut angle structures).
  branchesPerTri | the maximum number of branches we spawn in the search tree for each triangle type (e.g., 2 for a vanilla normal surface tree traversal algorithm). If the underlying coordinate system does not support triangles then this argument will be ignored.
  enumeration | `true` if we should optimise the tableaux for a full enumeration of vertex surfaces or taut angle structures, or `false` if we should optimise the tableaux for an existence test (such as searching for a non-trivial normal disc or sphere).

template<int nTypes>

regina::NTypeTrie< nTypes >::NTypeTrie | ( |  | ) |

inline

Initialises an empty trie.

template<class LPConstraint , typename BanConstraint , typename Integer >

unsigned long regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nVisited | ( |  | ) | const

inline

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 NTreeEnumeration::run() or NTreeSingleSoln::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 NTreeEnumeration::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.

template<class LPConstraint , typename BanConstraint , typename Integer >

double regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::percent | ( |  | ) | const

protected

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.

template<class LPConstraint >

void regina::LPInitialTableaux< LPConstraint >::Col::push | ( | unsigned | row,
|  | int | val
| ) |  |

inline

Adds the given entry in the given row to this column.

Precondition
  No entry in the given row has been added to this column yet.
  The sum of absolute values of all entries in this column must never exceed 4.

Parameters

  row | the row containing the given value.
  val | the value at this location in the matrix.

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::rank | ( |  | ) | const

inline

Returns the rank of this matrix.

Note that, if we are imposing extra constraints through the template parameter LPConstraint, then there will be extra variables to enforce these, and so the rank will be larger than the rank of the original matching equation matrix.

Returns
  the matrix rank.

template<typename Integer >

void regina::LPMatrix< Integer >::reserve | ( | unsigned | maxRows,
|  | unsigned | maxCols
| ) |  |

inline

Reserves enough space to store the elements of a maxRows by maxCols matrix.

This is just an upper bound: your matrix may end up using fewer elements than this, but it cannot use more.

This matrix will still not be initialised until you call either initClone() or initIdentity(). See the class notes for details.

Precondition
  This matrix was created using the default (no-argument) constructor, and you have not called any other routines on this matrix since.

Warning
  To elaborate on the precondition above: you can only call reserve() once, and if you did not use the default LPMatrix constructor then you cannot call it at all. Any additional calls to reserve() will result in a memory leak.

Parameters

  maxRows | an upper bound on the number of rows that you will need for this matrix. This must be strictly positive.
  maxCols | an upper bound on the number of columns that you will need for this matrix. This must be strictly positive.

template<class LPConstraint , typename Integer >

void regina::LPData< LPConstraint, Integer >::reserve | ( | const LPInitialTableaux< LPConstraint > * | origTableaux | ) |

inline

Reserves enough memory for this tableaux to work with.

You must call this routine before doing anything else with this tableaux.

The data in this tableaux will not be initialised, and the contents and behaviour of this tableaux will remain undefined until you call one of the initialisation routines initStart() or initClone().

Parameters

  origTableaux | the original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm began.

template<typename Integer >

unsigned regina::LPMatrix< Integer >::rows | ( |  | ) | const

inline

Returns the number of rows in this matrix.

This relates to the currently assigned matrix size, not the total amount of memory that was originally reserved.

Returns
  the number of rows.

template<class LPConstraint , typename BanConstraint , typename Integer >

void regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::run | ( | bool(*)(const NTreeEnumeration< LPConstraint, BanConstraint, Integer > &, 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 NTreeEnumeration 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.

template<class LPConstraint , typename BanConstraint , typename Integer >

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

inline

Runs the complete tree traversal algorithm to enumerate all taut angle structures.

For each taut angle structure that is found, this routine will call the function useSoln. It will pass two arguments to this function: (i) this 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 enumeration object: for instance, you can dump the type vector using dumpTypes(), or you can reconstruct the full taut angle structure using buildStructure() and perform some other operations upon it. If you do call buildStructure(), remember to delete the angle structure once you are finished with it.

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

The usual way of using this routine is to construct an NTautEnumeration 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 taut angle structures that had not yet been found, but it will not call useSoln on those solutions that had previously been found during earlier calls to next().

Precondition
  The enumeration 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 taut angle structure, as described above.
  arg | the second argument to pass to the callback function; this may be any type of data that you like.

template<class LPConstraint , typename BanConstraint , typename Integer >

void regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::setNext | ( | int | nextType | ) |

protected

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.

template<class LPConstraint , typename Integer >

int regina::LPData< LPConstraint, Integer >::sign | ( | unsigned | pos | ) | const

inline

Returns the sign of the given variable under the current basis.

This does not attempt to "undo" any changes of variable caused by prior calls to constrainPositive() or constrainOct(); it simply tests the sign of the variable in the given column of the tableaux in its current form.

Specifically: if the given variable is inactive or non-basic, this routine returns zero. If the given variable is in the basis, this routine returns the sign of the corresponding integer on the right-hand side of the tableaux.

Parameters

  pos | the index of the variable to query. This must be between 0 and origTableaux_->columns()-1 inclusive.

Returns
  the sign of the variable as described above; this will be either 1, 0 or -1.

template<class LPConstraint , typename BanConstraint , typename Integer >

bool regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::supported | ( | NormalCoords | coords | ) |

inline static

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.

static bool regina::LPConstraintBase::supported | ( | NormalCoords | coords | ) |

static

Indicates whether the given coordinate system is supported by this constraint class.

This routine assumes that the given system is already known to be supported by the generic tree traversal infrastructure, and only returns `false` if there are additional prerequisites imposed by this particular constraint class that the given system does not satisfy. If this constraint class does not impose any of its own additional conditions, this routine may simply return `true`.

Parameters

  coords | the coordinate system being queried; this must be one of the coordinate systems known to be supported by the generic NTreeTraversal infrastructure.

Returns
  `true` if and only if this coordinate system is also supported by this specific constraint class.

static bool regina::BanConstraintBase::supported | ( | NormalCoords | coords | ) |

static protected

Indicates whether the given coordinate system is supported by this constraint class.

This routine assumes that the given system is already known to be supported by the generic tree traversal infrastructure, and only returns `false` if there are additional prerequisites imposed by this particular constraint class that the given system does not satisfy. If this constraint class does not impose any of its own additional conditions, this routine may simply return `true`.

Parameters

  coords | the coordinate system being queried; this must be one of the coordinate systems known to be supported by the generic NTreeTraversal infrastructure.

Returns
  `true` if and only if this coordinate system is also supported by this specific constraint class.

template<typename Integer >

void regina::LPMatrix< Integer >::swapRows | ( | unsigned | r1,
|  | unsigned | r2
| ) |  |

inline

Swaps the two given rows of this matrix.

The two arguments r1 and r2 may be equal (in which case the matrix will be left unchanged).

Parameters

  r1 | the index of the first row to swap. This must be between 0 and rows()-1 inclusive.
  r2 | the index of the second row to swap. This must be between 0 and rows()-1 inclusive.

template<class LPConstraint >

const NTriangulation * regina::LPInitialTableaux< LPConstraint >::tri | ( |  | ) | const

inline

Returns the underlying 3-manifold triangulation from which the matching equations were derived.

Returns
  the underlying triangulation.

static bool regina::LPConstraintBase::verify | ( | const NNormalSurface * | s | ) |

static

Ensures that the given normal surface satisfies the extra constraints described by this class.

Ideally this test is not based on explicitly recomputing the linear function(s), but instead runs independent tests. For instance, if this class is used to constraint Euler characteristic, then ideally this routine would call s->getEulerChar() and test the return value of that routine instead.

If these linear constraints work with angle structure coordinates (not normal or almost normal surfaces), then this routine should return `false`.

Parameters

  s | the surface to test.

Returns
  `true` if the given surface satisfies these linear constraints, or `false` if it does not.

static bool regina::LPConstraintBase::verify | ( | const NAngleStructure * | s | ) |

static

Ensures that the given angle structure satisfies the extra constraints described by this class.

Ideally this test is not based on explicitly recomputing the linear function(s), but instead runs independent tests; see the related routine verify(const NNormalSurface*) for examples.

If these linear constraints work with normal or almost normal surfaces (not angle structure coordinates), then this routine should return `false`.

Parameters

  s | the angle structure to test.

Returns
  `true` if the given angle structure satisfies these linear constraints, or `false` if it does not.

template<class LPConstraint , typename BanConstraint , typename Integer >

bool regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::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.

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

template<class LPConstraint , typename BanConstraint , typename Integer >

bool regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::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.

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 NAngleStructureVector::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 NTreeTraversal 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 NAngleStructureVector::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).

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

static bool regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::writeStructure | ( | const NTautEnumeration< LPConstraint, BanConstraint, Integer > & | tree,
|  | void * |
| ) |  |

static

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.

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

The angle structure 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. The final scaling coordinate (used to projectivise the angle structure polytope) will also be written. 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 taut angle structure. 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 taut angle structure.

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

template<class LPConstraint , typename BanConstraint , typename Integer >

bool regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::writeSurface | ( | const NTreeEnumeration< LPConstraint, BanConstraint, Integer > & | 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).

template<class LPConstraint , typename BanConstraint , typename Integer >

bool regina::NTreeEnumeration< LPConstraint, BanConstraint, Integer >::writeTypes | ( | const NTreeEnumeration< LPConstraint, BanConstraint, Integer > & | 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).

template<class LPConstraint , typename BanConstraint , typename Integer >

bool regina::NTautEnumeration< LPConstraint, BanConstraint, Integer >::writeTypes | ( | const NTautEnumeration< LPConstraint, BanConstraint, Integer > & | 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 taut angle structure. 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).

regina::BanConstraintBase::~BanConstraintBase | ( |  | ) |

inline protected

Destroys this object and all associated data.

template<class LPConstraint , typename Integer >

regina::LPData< LPConstraint, Integer >::~LPData | ( |  | ) |

inline

Destroys this tableaux.

This is safe even if reserve() was never called.

template<class LPConstraint >

regina::LPInitialTableaux< LPConstraint >::~LPInitialTableaux | ( |  | ) |

inline

Destroys this matrix.

template<typename Integer >

regina::LPMatrix< Integer >::~LPMatrix | ( |  | ) |

inline

Destroys this matrix and all of the data it contains.

You can safely destroy a matrix that is uninitialised or only partially initialised (i.e., space has been reserved but the matrix size is not set).

template<class LPConstraint , typename BanConstraint , typename Integer >

regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::~NTreeTraversal | ( |  | ) |

protected

Destroys this object.

template<int nTypes>

regina::NTypeTrie< nTypes >::~NTypeTrie | ( |  | ) |

inline

Destroys this trie.

## Variable Documentation

bool* regina::BanConstraintBase::banned_

protected

Indicates which columns of a tableaux correspond to banned coordinates (e.g., banned normal disc types).

The size of this array is the number of normal or angle structure coordinates (so we explicitly exclude extra columns that arise from the template parameter LPConstraint.

template<class LPConstraint , typename BanConstraint , typename Integer >

const NormalCoords regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::coords_

protected

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.

int regina::BanConstraintBase::coords_

protected

The normal or almost normal coordinate system in which we are working.

This must be one of NS_QUAD, NS_STANDARD, NS_AN_QUAD_OCT, NS_AN_STANDARD, or NS_ANGLE.

int regina::LPConstraintEuler::Coefficients::euler

The coefficient of the Euler characteristic function for the corresponding column of the matching equation matrix.

template<class LPConstraint , typename BanConstraint , typename Integer >

int regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::level_

protected

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.

int regina::LPConstraintNonSpun::Coefficients::longitude

The coefficient of the longitude equation for the corresponding column of the matching equation matrix.

template<class LPConstraint , typename BanConstraint , typename Integer >

LPData<LPConstraint, Integer>* regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::lp_

protected

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 NTreeEnumeration::next() for details of when and how these tableaux are constructed.

template<class LPConstraint , typename BanConstraint , typename Integer >

LPData<LPConstraint, Integer>** regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::lpSlot_

protected

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 NTreeEnumeration::next() for details of when and how these tableaux are constructed and later overwritten.

bool* regina::BanConstraintBase::marked_

protected

Indicates which columns of a tableaux correspond to marked coordinates (e.g., marked normal disc types).

The size of this array is the number of normal or angle structure coordinates (so we explicitly exclude extra columns that arise from the template parameter LPConstraint.

int regina::LPConstraintNonSpun::Coefficients::meridian

The coefficient of the meridian equation for the corresponding column of the matching equation matrix.

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::Col::minus[4]

The rows containing these -1 entries, in any order.

The same row may appear in this list more than once (indicating a -2, -3 or -4 entry in the matrix).

template<class LPConstraint , typename BanConstraint , typename Integer >

LPData<LPConstraint, Integer>** regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nextSlot_

protected

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.

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::Col::nMinus

The total number of -1 entries in this column.

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::Col::nPlus

The total number of +1 entries in this column.

template<class LPConstraint , typename BanConstraint , typename Integer >

const int regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nTableaux_

protected

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

template<class LPConstraint , typename BanConstraint , typename Integer >

const int regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nTets_

protected

The number of tetrahedra in the underlying triangulation.

template<class LPConstraint , typename BanConstraint , typename Integer >

const int regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nTypes_

protected

The total length of a type vector.

template<class LPConstraint , typename BanConstraint , typename Integer >

unsigned long regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::nVisited_

protected

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.

template<class LPConstraint , typename BanConstraint , typename Integer >

int regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::octLevel_

protected

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.

template<class LPConstraint , typename BanConstraint , typename Integer >

const LPInitialTableaux<LPConstraint> regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::origTableaux_

protected

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

template<class LPConstraint >

unsigned regina::LPInitialTableaux< LPConstraint >::Col::plus[4]

The rows containing these +1 entries, in any order.

The same row may appear in this list more than once (indicating a +2, +3 or +4 entry in the matrix).

template<class LPConstraint , typename BanConstraint , typename Integer >

LPData<LPConstraint, Integer> regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::tmpLP_[4]

protected

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.

const NTriangulation* regina::BanConstraintBase::tri_

protected

The triangulation with which we are working.

template<class LPConstraint , typename BanConstraint , typename Integer >

char* regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::type_

protected

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.

template<class LPConstraint , typename BanConstraint , typename Integer >

int* regina::NTreeTraversal< LPConstraint, BanConstraint, Integer >::typeOrder_

protected

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

Copyright © 1999-2014, 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).