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

#include <enumerate/treetraversal.h>

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

Public Member Functions
template<typename... BanArgs>
	TreeEnumeration (const Triangulation< 3 > &tri, NormalEncoding enc, BanArgs &&... banArgs)
	Creates a new object for running the tree traversal algorithm. More...

size_t	solutions () const
	Returns the total number of vertex normal or almost normal surfaces found thus far in the tree traversal search. More...

template<typename Action , typename... Args>
bool	run (Action &&action, Args &&... args)
	Runs the complete tree traversal algorithm to enumerate vertex normal or almost normal surfaces. More...

bool	next (ProgressTracker *tracker=nullptr)
	An incremental step in the tree traversal algorithm that runs forward until it finds the next solution. More...

	TreeEnumeration (const TreeEnumeration &)=delete

TreeEnumeration &	operator= (const TreeEnumeration &)=delete

size_t	visited () const
	Returns the total number of nodes in the search tree that we have visited thus far in the tree traversal. More...

void	dumpTypes (std::ostream &out) const
	Writes the current type vector to the given output stream. More...

std::string	typeString () const
	Returns the current type vector in string form. More...

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream. More...

NormalSurface	buildSurface () const
	Reconstructs the full normal surface that is represented by the type vector at the current stage of the search. More...

AngleStructure	buildStructure () const
	Reconstructs the full taut angle structure that is represented by the type vector at the current stage of the search. More...

void	writeTextLong (std::ostream &out) const
	A default implementation for detailed output. More...

std::string	str () const
	Returns a short text representation of this object. More...

std::string	utf8 () const
	Returns a short text representation of this object using unicode characters. More...

std::string	detail () const
	Returns a detailed text representation of this object. More...

Static Public Member Functions
static bool	writeTypes (const TreeEnumeration &tree)
	A callback function that writes to standard output the type vector at the current point in the given tree traversal search. More...

static bool	writeSurface (const TreeEnumeration &tree)
	A callback function that writes to standard output the full triangle-quadrilateral coordinates of the vertex normal or almost normal surface at the current point in the given tree traversal search. More...

static bool	supported (NormalEncoding enc)
	Indicates whether the given normal surface or angle structure vector encoding is supported by this tree traversal infrastructure. More...

Protected Member Functions
void	setNext (size_t nextType)
	Rearranges the search tree so that nextType becomes the next type that we process. More...

ssize_t	nextUnmarkedTriangleType (size_t startFrom)
	Returns the next unmarked triangle type from a given starting point. More...

int	feasibleBranches (size_t quadType)
	Determines how many different values we could assign to the given quadrilateral or angle type and still obtain a feasible system. More...

double	percent () const
	Gives a rough estimate as to what percentage of the way the current type vector is through a full enumeration of the search tree. More...

Protected Attributes
const LPInitialTableaux< LPConstraintNone >	origTableaux_
	The original starting tableaux that holds the adjusted matrix of matching equations, before the tree traversal algorithm begins. More...

const NormalEncoding	enc_
	The normal surface or angle structure vector encoding that we are using for our enumeration task. More...

const BanNone	ban_
	Details of any banning/marking constraints that are in use. More...

const size_t	nTets_
	The number of tetrahedra in the underlying triangulation. More...

const size_t	nTypes_
	The total length of a type vector. More...

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

char *	type_
	The current working type vector. More...

size_t *	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...

ssize_t	level_
	The current level in the search tree. More...

ssize_t	octLevel_
	The level at which we are enforcing an octagon type (with a strictly positive number of octagons). More...

LPData< LPConstraintNone, Integer > *	lp_
	Stores tableaux for linear programming at various nodes in the search tree. More...

LPData< LPConstraintNone, 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< LPConstraintNone, Integer > **	nextSlot_
	Points to the next available tableaux in lp_ that is free to use at each level of the search tree. More...

size_t	nVisited_
	Counts the total number of nodes in the search tree that we have visited thus far. More...

LPData< LPConstraintNone, 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

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

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

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

This class essentially implements the algorithm from "A tree traversal algorithm for decision problems in knot theory and 3-manifold topology", Burton and Ozlen, Algorithmica 65:4 (2013), pp. 772-801.

To enumerate all vertex surfaces for a given 3-manifold triangulation, simply construct a TreeEnumeration object and call run().

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

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

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

By using appropriate template parameters LPConstraint and/or BanConstraint, it is possible to impose additional linear constraints on the normal surface solution cone, and/or explicitly force particular normal coordinates to zero. In this case, the notion of "vertex surface" is modified to mean a normal surface whose coordinates lie on an extreme ray of the restricted solution cone under these additional constraints (and whose coordinates are integers with no common divisor). See the LPConstraintBase and BanConstraintBase class notes for details.

Note that some constraint classes may cause the TreeEnumeration class constructor to throw an exception; see the constructor documentation for details.

The template argument IntType indicates the integer type that will be used throughout the underlying linear programming machinery. Unless you have a good reason to do otherwise, you should use the arbitrary-precision Integer class (in which integers can grow arbitrarily large, and overflow can never occur).

This class is designed to manage the execution of a significant enumeration operation, and so it does not support copying, moving or swapping.

Precondition: The parameter LPConstraint must be a subclass of LPConstraintSubspace, and BanConstraint must be either BanNone or a subclass of BanConstraintBase. Note in particular that the base class LPConstraintBase is not enough here. See the LPConstraintBase, LPConstraintSubspace and BanConstraintBase class notes for further details.; The default constructor for the template class IntType must intialise each new integer to zero. The classes Integer and NativeInteger, for instance, have this property.

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

Headers: Parts of this template class are implemented in a separate header (treetraversal-impl.h), which is not included automatically by this file. Most end users should not need this extra header, since Regina's calculation engine already includes explicit instantiations for common combinations of template arguments.

Python: This is a heavily templated class; nevertheless, many variants are now made available to Python users. Each class name is of the form TreeEnumeration_LPConstraint_BanConstraint, where the suffixes LPConstraint and BanConstraint are abbreviated versions of the corresponding template parameters; these suffixes are omitted entirely for the common cases LPConstraintNone and BanNone. As an example, to enumerate non-spun normal surfaces in an ideal 3-manifold triangulation, you would use the Python class TreeEnumeration_NonSpun. You are encouraged to look through the Regina namespace to see which combinations of constraint classes are supported under Python. In all cases, the IntType parameter is taken to be regina::Integer.

Warning: The API for this class or function has not yet been finalised. This means that the interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please check the detailed changelog with each new release to see if you need to make changes to your code.

Constructor & Destructor Documentation

◆ TreeEnumeration()

template<class LPConstraint , typename BanConstraint , typename IntType >

template<typename... BanArgs>

regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::TreeEnumeration	(	const Triangulation< 3 > &	tri,
		NormalEncoding	enc,
		BanArgs &&...	banArgs
	)

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 vector encoding adhere to any preconditions required by the template parameters LPConstraint and BanConstraint.

Exceptions

InvalidArgument	It was not possible to add the extra constraints from the LPConstraint template argument, due to an error which should have been preventable with the right checks in advance. Such exceptions are generated by the LPConstraint class, and so you should consult the class documentation for your chosen LPConstraint template argument to see if this is a possibility.
InvalidArgument	It was not possible to add the extra constraints from the LPConstraint template argument, due to an error that was "genuinely" unforseeable. Again, such exceptions are generated by your chosen LPConstraint class, and you should consult its documentation to see if this is a possibility.

Parameters

tri	the triangulation in which we wish to enumerate vertex surfaces.
enc	the normal (or almost normal) surface vector encoding that we are working with.
banArgs	any additional arguments to be passed to the BanConstraint constructor, after the initial starting tableaux. For most ban constrainst classes, this list of arguments is empty.

Member Function Documentation

◆ buildStructure()

AngleStructure regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::buildStructure ( ) const

inherited

Reconstructs the full taut angle structure that is represented by the type vector at the current stage of the search.

This routine is for use only with taut angle structures, not normal or almost normal surfaces.

There will always be a unique taut angle structure corresponding to this type vector (this follows from the preconditions below).

Precondition: This tree traversal is at a point in the search where it has found a feasible solution that represents a taut angle structure. This condition is always true after TautEnumeration::next() returns true, or any time that TautEnumeration::run() calls its callback function.; We are working with angle structure coordinates. This will be checked (see the exception details below).

Exceptions

FailedPrecondition We are not working with angle structure coordinates (i.e., the coordinate system passed to the TreeTraversal constructor was not NS_ANGLE).

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

◆ buildSurface()

NormalSurface regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::buildSurface ( ) const

inherited

Reconstructs the full normal surface that is represented by the type vector at the current stage of the search.

This routine is for use only with normal (or almost normal) surfaces, not taut angle structures.

If the current type vector does not represent a vertex normal surface (which may be the case when calling TreeSingleSoln::find()), then there may be many normal surfaces all represented by the same type vector; in this case there are no further guarantees about which of these normal surfaces you will get.

The surface that is returned will use the same vector encoding that was passed to the TreeTraversal class constructor.

Precondition: This tree traversal is at a point in the search where it has found a feasible solution that represents a normal surface (though this need not be a vertex surface). This condition is always true after TreeEnumeration::next() or TreeSingleSoln::find() returns true, or any time that TreeEnumeration::run() calls its callback function.; We are working with normal or almost normal surfaces. This will be checked (see the exception details below).

Exceptions

FailedPrecondition We are not working with normal or almost normal surfaces (i.e., the coordinate system passed to the TreeTraversal constructor was NS_ANGLE).

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

◆ detail()

std::string regina::Output< TreeTraversal< LPConstraintNone, BanNone, Integer > , supportsUtf8 >::detail ( ) const

inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns: a detailed text representation of this object.

◆ dumpTypes()

void regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::dumpTypes ( std::ostream & out ) const

inlineinherited

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.

This routine outputs the same information that typeString() returns.

Python: Not present. Instead use typeString(), which returns this same information as a string.

Parameters

out	the output stream to which to write.

◆ feasibleBranches()

int regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::feasibleBranches ( size_t quadType )

protectedinherited

Determines how many different values we could assign to the given quadrilateral or angle type and still obtain a feasible system.

This will involve solving three or four linear programs, all based on the current state of the tableaux at the current level of the search tree. These assign 0, 1, 2 and 3 to the given quadrilateral or angle type in turn (here 0 is not used for angle types), and then enforce the corresponding constraints. For quadrilateral types, we count types 0 and 1 separately as in TreeEnumeration, not merged together as in TreeSingleSoln.

Precondition: The given quadrilateral or angle type has not yet been processed in the search tree (i.e., it has not had an explicit value selected).; When using angle structure coordinates, the final scaling coordinate has already been enforced as positive. (This is because, for angle structures, this routine does nothing to eliminate the zero solution.)

Parameters

quadType the quadrilateral or angle type to examine.

Returns: the number of type values 0, 1, 2 or 3 that yield a feasible system; this will be between 0 and 4 inclusive for quadrilateral types, or between 0 and 3 inclusive for angle types.

◆ next()

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

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

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.

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

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

Python: The global interpreter lock will be released while this function runs, so you can use it with Python-based multithreading.

Parameters

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

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

◆ nextUnmarkedTriangleType()

ssize_t regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::nextUnmarkedTriangleType ( size_t startFrom )

inlineprotectedinherited

Returns the next unmarked triangle type from a given starting point.

Specifically, this routine returns the first unmarked triangle type whose type number is greater than or equal to startFrom. For more information on marking, see the BanConstraintBase class notes.

This routine simply searches through types by increasing index into the type vector; in particular, it does not make any use of the reordering defined by the typeOrder_ array.

Precondition: We are working in standard normal or almost normal coordinates. That is, the coordinate system passed to the TreeTraversal constructor was one of NS_STANDARD or NS_AN_STANDARD.; The argument startFrom is at least nTets_ (i.e., it is at least as large as the index of the first triangle type).

Parameters

startFrom the index into the type vector of the triangle type from which we begin searching.

Returns: the index into the type vector of the next unmarked triangle type from startFrom onwards, or -1 if there are no more remaining.

◆ percent()

double regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::percent ( ) const

protectedinherited

Gives a rough estimate as to what percentage of the way the current type vector is through a full enumeration of the search tree.

This is useful for progress tracking.

This routine only attemps to determine the percentage within a reasonable range of error (at the time of writing, 0.01%). This allows it to be more efficient (in particular, by only examining the branches closest to the root of the search tree).

Returns: the percentage, as a number between 0 and 100 inclusive.

◆ run()

template<class LPConstraint , typename BanConstraint , typename IntType >

template<typename Action , typename... Args>

bool regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::run	(	Action &&	action,
		Args &&...	args
	)

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 action (which must be a function or some other callable object).

The first argument to action must be a const reference to a TreeEnumeration object (which will be this object).
If there are any additional arguments supplied in the list args, then these will be passed as subsequent arguments to action.
The tree traversal algorithm will block until action returns.
action must return a bool. A return value of false indicates that run() should continue the tree traversal, and a return value of true indicates that run() should terminate the search immediately.

Your action can extract details of the solution directly from the tree enumeration object: for instance, it can dump the type vector using dumpTypes(), or it can reconstruct the full normal or almost normal surface using buildSurface() and perform some other operations upon it.

The usual way of using this routine is to construct a TreeEnumeration object and then immediately call run(). However, if you prefer, you may call run() after one or more calls to next(). In this case, run() will continue the search from the current point and run it to its completion. In other words, run() will locate and call action for all vertex surfaces that had not yet been found, but it will not call action 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).

Python: This function is available, and action may be a pure Python function. However, action cannot take any additional arguments beyond the initial TreeEnumeration object (and therefore the additional args list is omitted here).

Parameters

action	a function (or some other callable object) to call for each vertex surface that is found.
args	any additional arguments that should be passed to action, following the initial tree enumeration argument.

Returns: true if action ever terminated the search by returning true, or false if the search was allowed to run to completion.

◆ setNext()

void regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::setNext ( size_t nextType )

protectedinherited

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.

◆ solutions()

template<class LPConstraint , typename BanConstraint , typename IntType >

size_t regina::TreeEnumeration< LPConstraint, BanConstraint, IntType >::solutions

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 that were found. 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.

◆ str()

std::string regina::Output< TreeTraversal< LPConstraintNone, BanNone, Integer > , supportsUtf8 >::str ( ) const

inherited

Returns a short text representation of this object.

This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python __str__() and __repr__() functions.

Python: The Python "stringification" function __str__() will use precisely this function, and for most classes the Python __repr__() function will incorporate this into its output.

Returns: a short text representation of this object.

◆ supported()

bool regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::supported ( NormalEncoding enc )

inlinestaticinherited

Indicates whether the given normal surface or angle structure vector encoding is supported by this tree traversal infrastructure.

Any restrictions imposed by LPConstraint and BanConstraint will be taken into account.

Note that, even if an encoding is supported, this does not mean that the underlying tableaux will use the same encoding internally. See LPInitialTableaux for more details on this.

Parameters

enc	the vector encoding being queried. In particular, this may be the special angle structure encoding.

Returns: true if and only if the given vector encoding is supported.

◆ typeString()

std::string regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::typeString

inlineinherited

Returns the current type vector in string form.

There will be no spaces between the types.

This routine returns the same information that dumpTypes() writes.

Parameters

the	type vector in string form.

◆ utf8()

std::string regina::Output< TreeTraversal< LPConstraintNone, BanNone, Integer > , supportsUtf8 >::utf8 ( ) const

inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.

Returns: a short text representation of this object.

◆ visited()

size_t regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::visited

inlineinherited

Returns the total number of nodes in the search tree that we have visited thus far in the tree traversal.

This figure might grow much faster than the number of solutions, since it also counts traversals through "dead ends" in the search tree.

This counts all nodes that we visit, including those that fail any or all of the domination, feasibility and zero tests. The precise way that this number is calculated is subject to change in future versions of Regina.

If you called an "all at once" routine such as TreeEnumeration::run() or TreeSingleSoln::find(), then this will be the total number of nodes that were visited in the entire tree traversal. If you are calling an "incremental" routine such as TreeEnumeration::next() (i.e., you are generating one solution at time), then this will be the partial count of how many nodes have been visited so far.

Returns: the number of nodes visited so far.

◆ writeSurface()

template<class LPConstraint , typename BanConstraint , typename IntType >

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

inlinestatic

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

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.

Python: This function is available and can be used directly, but you should not use it as a callback with run(). Currently this causes a crash in Python, most likely coming from some confusion in passing a C++ function as a C++ callback via a Python wrapper. Instead you can use a pure python function f as a callback, where f(tree) just calls tree.writeSurface().

Parameters

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

Returns: false (which indicates to run() that we should continue the tree traversal).

◆ writeTextLong()

void regina::ShortOutput< TreeTraversal< LPConstraintNone, BanNone, Integer > , false >::writeTextLong ( std::ostream & out ) const

inlineinherited

A default implementation for detailed output.

This routine simply calls T::writeTextShort() and appends a final newline.

Python: Not present. Instead you can call detail() from the subclass T, which returns this output as a string.

Parameters

out	the output stream to which to write.

◆ writeTextShort()

void regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::writeTextShort ( std::ostream & out ) const

inherited

Writes a short text representation of this object to the given output stream.

Python: Not present. Use str() instead.

Parameters

out	the output stream to which to write.

◆ writeTypes()

template<class LPConstraint , typename BanConstraint , typename IntType >

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

inlinestatic

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

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: false (which indicates to run() that we should continue the tree traversal).

Member Data Documentation

◆ ban_

const BanNone regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::ban_

protectedinherited

Details of any banning/marking constraints that are in use.

◆ enc_

const NormalEncoding regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::enc_

protectedinherited

The normal surface or angle structure vector encoding that we are using for our enumeration task.

Note that the tableaux will not necessarily use this same encoding; see LPInitialTableaux for details.

◆ level_

ssize_t regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::level_

protectedinherited

The current level in the search tree.

As the search runs, this holds the index into typeOrder_ corresponding to the last type that we chose.

◆ lp_

LPData<LPConstraintNone , Integer >* regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::lp_

protectedinherited

Stores tableaux for linear programming at various nodes in the search tree.

We only store a limited number of tableaux at any given time, and as the search progresses we overwrite old tableaux with new tableaux.

More precisely, we store a linear number of tableaux, essentially corresponding to the current node in the search tree and all of its ancestores, all the way up to the root node. In addition to these tableaux, we also store other immediate children of these ancestores that we have pre-prepared for future processing. See the documentation within routines such as TreeEnumeration::next() for details of when and how these tableaux are constructed.

◆ lpSlot_

LPData<LPConstraintNone , Integer >** regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::lpSlot_

protectedinherited

Recall from above that the array lp_ stores tableaux for the current node in the search tree and all of its ancestors.

This means we have one tableaux for the root node, as well as additional tableaux at each level 0,1,...,level_.

The array lpSlot_ indicates which element of the array lp_ holds each of these tableaux. Specifically: lpSlot_[0] points to the tableaux for the root node, and for each level i in the range 0,...,level_, the corresponding tableaux is *lpSlot_[i+1]. Again, see the documentation within routines such as TreeEnumeration::next() for details of when and how these tableaux are constructed and later overwritten.

◆ nextSlot_

LPData<LPConstraintNone , Integer >** regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::nextSlot_

protectedinherited

Points to the next available tableaux in lp_ that is free to use at each level of the search tree.

Specifically: nextSlot_[0] points to the next free tableaux at the root node, and for each level i in the range 0,...,level_, the corresponding next free tableaux is *nextSlot_[i+1].

The precise layout of the nextSlot_ array depends on the order in which we process quadrilateral, triangle and/or angle types.

◆ nTableaux_

const size_t regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::nTableaux_

protectedinherited

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

◆ nTets_

const size_t regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::nTets_

protectedinherited

The number of tetrahedra in the underlying triangulation.

◆ nTypes_

const size_t regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::nTypes_

protectedinherited

The total length of a type vector.

◆ nVisited_

size_t regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::nVisited_

protectedinherited

Counts the total number of nodes in the search tree that we have visited thus far.

This may grow much faster than the number of solutions, since it also counts traversals through "dead ends" in the search tree.

◆ octLevel_

ssize_t regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::octLevel_

protectedinherited

The level at which we are enforcing an octagon type (with a strictly positive number of octagons).

If we are working with angle structures or normal surfaces only (and so we do not allow octagons at all), then octLevel_ = nTypes_. If we are allowing almost normal surfaces but we have not yet chosen an octagon type, then octLevel_ = -1.

◆ origTableaux_

const LPInitialTableaux<LPConstraintNone > regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::origTableaux_

protectedinherited

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

◆ tmpLP_

LPData<LPConstraintNone , Integer > regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::tmpLP_[4]

protectedinherited

Temporary tableaux used by the function feasibleBranches() to determine which quadrilateral types or angle types have good potential for pruning the search tree.

Other routines are welcome to use these temporary tableaux also (as "scratch space"); however, be aware that any call to feasibleBranches() will overwrite them.

◆ type_

char* regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::type_

protectedinherited

The current working type vector.

As the search runs, we modify this type vector in-place. Any types beyond the current level in the search tree will always be set to zero.

◆ typeOrder_

size_t* regina::TreeTraversal< LPConstraintNone , BanNone , Integer >::typeOrder_

protectedinherited

A permutation of 0,...,nTypes_-1 that indicates in which order we select types: the first type we select (at the root of the tree) is type_[typeOrder_[0]], and the last type we select (at the leaves of the tree) is type_[typeOrder_[nTypes_-1]].

This permutation is allowed to change as the algorithm runs (though of course you can only change sections of the permutation that correspond to types not yet selected).

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

enumerate/treetraversal.h

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ TreeEnumeration()

Member Function Documentation

◆ buildStructure()

◆ buildSurface()

◆ detail()

◆ dumpTypes()

◆ feasibleBranches()

◆ next()

◆ nextUnmarkedTriangleType()

◆ percent()

◆ run()

◆ setNext()

◆ solutions()

◆ str()

◆ supported()

◆ typeString()

◆ utf8()

◆ visited()

◆ writeSurface()

◆ writeTextLong()

◆ writeTextShort()

◆ writeTypes()

Member Data Documentation

◆ ban_

◆ enc_

◆ level_

◆ lp_

◆ lpSlot_

◆ nextSlot_

◆ nTableaux_

◆ nTets_

◆ nTypes_

◆ nVisited_

◆ octLevel_

◆ origTableaux_

◆ tmpLP_

◆ type_

◆ typeOrder_