A gluing permutation search class that offers a specialised search algorithm for when only compact (finite) 3-manifold triangulations are required. More...

#include <census/gluingpermsearcher3.h>

Inheritance diagram for regina::CompactSearcher:

Classes
struct	TetEdgeState
	A structure used to track equivalence classes of tetrahedron edges as the gluing permutation set is constructed. More...

struct	TetVertexState
	A structure used to track equivalence classes of tetrahedron vertices as the gluing permutation set is constructed. More...

Public Types
using	PurgeFlags = CensusPurgeFlags
	Deprecated type alias for flags that indicate that our enumeration may ignore certain classes of triangulations. More...

Public Member Functions
	CompactSearcher (FacetPairing< 3 > pairing, FacetPairing< 3 >::IsoList autos, bool orientableOnly, CensusPurge whichPurge)
	Creates a new search manager for use when only compact 3-manifold triangulations are required. More...

	CompactSearcher (std::istream &in)
	Initialises a new search manager based on data read from the given input stream. More...

	~CompactSearcher () override
	Destroys this search manager and all supporting data structures. More...

void	dumpData (std::ostream &out) const override
	Dumps all internal data in a plain text format to the given output stream. More...

template<typename Action , typename... Args>
void	runSearch (Action &&action, Args &&... args)
	Generates all possible gluing permutation sets that satisfy the current search criteria. More...

template<typename Action , typename... Args>
void	partialSearch (long maxDepth, Action &&action, Args &&... args)
	Runs a partial search for all possible gluing permutations that satisfy the search criteria, branching only to the given depth and no further. More...

bool	isComplete () const
	Determines whether this search manager holds a complete gluing permutation set or just a partially completed search state. More...

bool	completePermSet () const
	Deprecated function that determines whether this search manager holds a complete gluing permutation set or just a partially completed search state. More...

void	dumpTaggedData (std::ostream &out) const
	Dumps all internal data in a plain text format, along with a marker to signify which precise class the data belongs to. More...

std::string	taggedData () const
	Returns all internal data in a plain text format, along with a marker to signify which precise class the data belongs to. More...

std::string	data () const
	Returns all internal data in a plain text format. More...

void	writeTextShort (std::ostream &out) const
	Writes a short text representation of this object to the given output stream. 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
template<typename Action , typename... Args>
static void	findAllPerms (FacetPairing< 3 > pairing, FacetPairing< 3 >::IsoList autos, bool orientableOnly, bool finiteOnly, CensusPurge whichPurge, Action &&action, Args &&... args)
	The main entry routine for running a search for all gluing permutation sets that complement a given face pairing. More...

static std::unique_ptr< GluingPermSearcher< 3 > >	bestSearcher (FacetPairing< 3 > pairing, FacetPairing< 3 >::IsoList autos, bool orientableOnly, bool finiteOnly, CensusPurge whichPurge)
	Constructs a search manager of the best possible class for the given search parameters. More...

static std::unique_ptr< GluingPermSearcher< 3 > >	fromTaggedData (std::istream &in)
	Creates a new search manager based on tagged data read from the given input stream. More...

static std::unique_ptr< GluingPermSearcher< 3 > >	fromTaggedData (const std::string &data)
	Creates a new search manager based on tagged data stored in the given string. More...

Static Public Attributes
static constexpr char	dataTag = 'f'
	A character used to identify this class when reading and writing tagged data in text format. More...

Protected Types
using	ActionWrapper = std::function< void(const GluingPerms< 3 > &)>
	The type used to hold the user's action function and arguments when enumerating gluing permutations. More...

Protected Member Functions
void	searchImpl (long maxDepth, ActionWrapper &&action) override
	A de-templatised implementation of runSearch() and partialSearch(). More...

char	dataTagInternal () const override
	Returns the character used to identify this class when storing tagged data in text format. More...

int	findEdgeClass (int edgeID) const
	Returns the representative of the equivalence class containing the given tetrahedron edge. More...

int	findEdgeClass (int edgeID, char &twisted) const
	Returns the representative of the equivalence class containing the given tetrahedron edge. More...

int	mergeVertexClasses ()
	Merge the classes of tetrahedron vertices as required by the new gluing made at stage orderElt of the search. More...

bool	mergeEdgeClasses ()
	Merge the classes of tetrahedron edges as required by the new gluing made at stage orderElt of the search. More...

void	splitVertexClasses ()
	Split the classes of tetrahedron vertices to mirror the undoing of the gluing at stage orderElt of the search. More...

void	splitEdgeClasses ()
	Split the classes of tetrahedron edges to mirror the undoing of the gluing at stage orderElt of the search. More...

void	vtxBdryJoin (int vertexID, char end, int adjVertexID, char twist)
	Signifies that the boundary edges supplied by the vertex linking triangles for the two given tetrahedron vertices should be marked as adjacent. More...

void	vtxBdryFixAdj (int vertexID)
	Adjusts the bdryNext and bdryTwist arrays for nearby tetrahedron vertices, to ensure that these arrays are consistent with the bdryNext and bdryTwist arrays stored with the given vertex. More...

void	vtxBdryBackup (int vertexID)
	Copies the bdryNext and bdryTwist arrays to the bdryNextOld and bdryTwistOld arrays for the given tetrahedron vertex. More...

void	vtxBdryRestore (int vertexID)
	Copies the bdryNextOld and bdryTwistOld arrays to the bdryNext and bdryTwist arrays for the given tetrahedron vertex. More...

void	vtxBdryNext (int vertexID, int tet, int vertex, int bdryFace, int next[2], char twist[2])
	Assuming the given edge of the vertex linking triangle for the given tetrahedron vertex lies on the boundary of the vertex link, this routine identifies the adjacent boundary edges of the vertex link in each direction. More...

bool	vtxBdryLength1 (int vertexID)
	Determines whether one of the edges of the vertex linking triangle for the given tetrahedron vertex in fact forms an entire one-edge boundary component of the overall vertex link. More...

bool	vtxBdryLength2 (int vertexID1, int vertexID2)
	Determines whether edges of the vertex linking triangles for each of the given tetrahedron vertices combine to form an entire two-edge boundary component of the overall vertex link, with one edge from each triangle. More...

void	vtxBdryConsistencyCheck ()
	Runs a number of tests on all tetrahedron vertices to locate consistency errors in the bdryEdges, bdryNext and bdryTwist members of the TetVertexState class. More...

void	vtxBdryDump (std::ostream &out)
	Dumps a summary of bdryNext, bdryTwist and bdryEdges for every vertex of every tetrahedron to the given output stream. More...

bool	isCanonical () const
	Compares the current set of gluing permutations with its preimage under each automorphism of the underlying face pairing, in order to see whether the current set is in canonical form (i.e., is lexicographically smallest). More...

bool	badEdgeLink (const FacetSpec< 3 > &face) const
	Determines whether the permutations already constructed model a triangulation with an edge identified with itself in reverse. More...

bool	lowDegreeEdge (const FacetSpec< 3 > &face, bool testDegree12, bool testDegree3) const
	Determines whether the permutations already constructed model a triangulation with a low degree edge. More...

Protected Attributes
unsigned	nVertexClasses
	The number of equivalence classes of identified tetrahedron vertices. More...

TetVertexState *	vertexState
	Used for tracking equivalence classes of identified tetrahedron vertices. More...

int *	vertexStateChanged
	Tracks the way in which the vertexState[] array has been updated over time. More...

unsigned	nEdgeClasses
	The number of equivalence classes of identified tetrahedron edges. More...

TetEdgeState *	edgeState
	Used for tracking equivalence classes of identified tetrahedron edges. More...

int *	edgeStateChanged
	Tracks the way in which the edgeState[] array has been updated over time. More...

GluingPerms< 3 >	perms_
	The set of gluing permutations under construction. More...

const FacetPairing< 3 >::IsoList	autos_
	The set of isomorphisms that define equivalence of gluing permutation sets. More...

bool	orientableOnly_
	Are we only searching for gluing permutations that correspond to orientable triangulations? More...

bool	finiteOnly_
	Are we only searching for gluing permutations that correspond to finite triangulations? More...

CensusPurge	whichPurge_
	Are there any types of triangulation that we may optionally avoid constructing? This should be a bitwise OR of constants from the CensusPurgeFlags enumeration. More...

bool	started
	Has the search started yet? This helps distinguish between a new search and the resumption of a partially completed search. More...

int *	orientation
	Keeps track of the orientation of each tetrahedron in the underlying triangulation. More...

FacetSpec< 3 > *	order
	Describes the order in which gluing permutations are assigned to faces. More...

int	orderSize
	The total number of edges in the face pairing graph, i.e., the number of elements of interest in the order[] array. More...

int	orderElt
	Marks which element of order[] we are currently examining at this stage of the search. More...

Static Protected Attributes
static constexpr char	VLINK_CLOSED = 1
	Signifies that a vertex link has been closed off (i.e., the link has no remaining boundary edges). More...

static constexpr char	VLINK_NON_SPHERE = 2
	Signifies that a vertex link has been made into something other than a 2-sphere with zero or more punctures. More...

static const int	vertexLinkNextFace [4][4]
	Maintains an ordering of the three tetrahedron faces surrounding a vertex in a tetrahedron. More...

static const int	vertexLinkPrevFace [4][4]
	Provides backwards links for the ordering described by vertexLinkNextFace. More...

Detailed Description

A gluing permutation search class that offers a specialised search algorithm for when only compact (finite) 3-manifold triangulations are required.

The only constraints placed upon a triangulation are that every edge must be valid (i.e., not identified with itself in reverse), and that the link of every vertex must be a disk or a sphere.

The search algorithm uses modified union-find structures on both edge and vertex equivalence classes to prune searches that are guaranteed to lead to bad edge or vertex links. For details see "Enumeration of non-orientable 3-manifolds using face-pairing graphs and union-find", Benjamin A. Burton, Discrete Comput. Geom. 38 (2007), no. 3, 527–571; and "Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations", Benjamin A. Burton, in "ISSAC 2011: Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation", ACM, 2011, pp. 59-66.

No additional unwanted triangulations will be produced by this search (in contrast to other search classes, such as ClosedPrimeMinSearcher). That is, only compact 3-manifolds will be produced.

This class is designed to manage the construction of a large census of triangulations, and so it does not support copying, moving or swapping.

Member Typedef Documentation

◆ ActionWrapper

using regina::GluingPermSearcher< 3 >::ActionWrapper = std::function<void(const GluingPerms<3>&)>

protectedinherited

The type used to hold the user's action function and arguments when enumerating gluing permutations.

◆ PurgeFlags

using regina::GluingPermSearcher< 3 >::PurgeFlags = CensusPurgeFlags

inherited

Deprecated type alias for flags that indicate that our enumeration may ignore certain classes of triangulations.

Deprecated:: This enumeration has now been renamed to regina::CensusPurgeFlags (and it now lives at the namespace level). Bitwise combinations of flags are now represented by regina::CensusPurge (not raw integers).

Python: The enumeration constants (but not the PurgeFlags type itself) are still available through the GluingPermSearcher<3> class for backward compatibility.

Constructor & Destructor Documentation

◆ CompactSearcher() [1/2]

regina::CompactSearcher::CompactSearcher	(	FacetPairing< 3 >	pairing,
		FacetPairing< 3 >::IsoList	autos,
		bool	orientableOnly,
		CensusPurge	whichPurge
	)

Creates a new search manager for use when only compact 3-manifold triangulations are required.

For details on how a search manager is used, see the GluingPermSearcher<3> documentation. Note in particular that this class will be automatically used by GluingPermSearcher<3>::findAllPerms() if possible, so there is often no need for an end user to instantiate this class directly.

All constructor arguments are the same as for the GluingPermSearcher<3> constructor, though some arguments (such as finiteOnly) are not needed here since they are already implied by the specialised search context.

Precondition: The given face pairing is connected, i.e., it is possible to reach any tetrahedron from any other tetrahedron via a series of matched face pairs.; The given face pairing is in canonical form as described by FacetPairing<3>::isCanonical(). Note that all face pairings constructed by FacetPairing<3>::findAllPairings() are of this form.

◆ CompactSearcher() [2/2]

regina::CompactSearcher::CompactSearcher ( std::istream & in )

Initialises a new search manager based on data read from the given input stream.

This may be a new search or a partially completed search.

This routine reads data in the format written by dumpData(). If you wish to read data whose precise class is unknown, consider using dumpTaggedData() and fromTaggedData() instead.

Warning: The data format is liable to change between Regina releases. Data in this format should be used on a short-term temporary basis only.

Exceptions

InvalidInput the data found in the input stream is invalid, incomplete, or incorrectly formatted.

Python: Not present, since this constructor is fundamentally designed around working through a single input stream as we make our way from base class constructors down to subclass constructors. Python users should use taggedData() and fromTaggedData() instead, which incorporate this same text data as part of their richer text format.

Parameters

in	the input stream from which to read.

◆ ~CompactSearcher()

regina::CompactSearcher::~CompactSearcher ( )

inlineoverride

Destroys this search manager and all supporting data structures.

Member Function Documentation

◆ badEdgeLink()

bool regina::GluingPermSearcher< 3 >::badEdgeLink ( const FacetSpec< 3 > & face ) const

protectedinherited

Determines whether the permutations already constructed model a triangulation with an edge identified with itself in reverse.

Note that such edges can only occur in non-orientable triangulations.

Tests that do not refer to the gluing permutation for the given face will not be run.

This routine is not fussy about the order in which gluing permutations are selected, as long as permutations not yet selected have the corresponding element of permIndices[] set to -1.

If finiteOnly_ is true in the search criteria, additional tests will be run that can eliminate triangulations with non-orientable vertex links. Although these tests are not searching for bad edge links per se, they can be performed within this routine with very little additional work needing to be done.

Parameters

face	the specific tetrahedron face upon which tests will be based.

Returns: true if the permutations under construction will lead to an edge identified with itself in reverse, or false if no such edge is found.

◆ bestSearcher()

std::unique_ptr< GluingPermSearcher< 3 > > regina::GluingPermSearcher< 3 >::bestSearcher	(	FacetPairing< 3 >	pairing,
		FacetPairing< 3 >::IsoList	autos,
		bool	orientableOnly,
		bool	finiteOnly,
		CensusPurge	whichPurge
	)

inlinestaticinherited

Constructs a search manager of the best possible class for the given search parameters.

Different subclasses of GluingPermSearcher<3> provide optimised search algorithms for different types of search.

Calling this routine and then calling runSearch() on the result has the same effect as the all-in-one routine findAllPerms(). Unless you have specialised requirements (such as partial searching), you are probably better calling findAllPerms() instead.

See the GluingPermSearcher<3> constructor for documentation on the arguments to this routine.

Precondition: The given face pairing is connected, i.e., it is possible to reach any tetrahedron from any other tetrahedron via a series of matched face pairs.; The given face pairing is in canonical form as described by FacetPairing<3>::isCanonical(). Note that all face pairings constructed by FacetPairing<3>::findAllPairings() are of this form.

Returns: the new search manager.

◆ completePermSet()

bool regina::GluingPermSearcher< 3 >::completePermSet ( ) const

inlineinherited

Deprecated function that determines whether this search manager holds a complete gluing permutation set or just a partially completed search state.

Deprecated:: This routine has been renamed to isComplete().

Returns: true if a complete gluing permutation set is held, or false otherwise.

◆ data()

std::string regina::GluingPermSearcher< 3 >::data ( ) const

inlineinherited

Returns all internal data in a plain text format.

This object can be recreated from this text data by calling the input stream constructor for the appropriate class.

This routine may be useful for transferring objects from one processor to another.

If subclasses override this function, they should write subclass data after superclass data. This means it is safe to dump data from a subclass and then recreate a new superclass object from that data (though subclass-specific information will be lost).

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

The key difference between data() and taggedData() is that taggedData() preserves all internal information even if this object belongs to a subclass of GluingPermSearcher, whereas data() only writes information pertaining to this base class.

Warning: The data format is liable to change between Regina releases. Data in this format should be used on a short-term temporary basis only.

Python: This routine is available, but the matching input stream constructor is not. Python users should use taggedData() and fromTaggedData() instead.

Parameters

all	of this object's internal data in plain text format.

◆ dataTagInternal()

char regina::CompactSearcher::dataTagInternal ( ) const

inlineoverrideprotectedvirtual

Returns the character used to identify this class when storing tagged data in text format.

Returns: the class tag.

Reimplemented from regina::GluingPermSearcher< 3 >.

Reimplemented in regina::ClosedPrimeMinSearcher.

◆ detail()

template<class T , bool supportsUtf8 = false>

std::string regina::Output< T, 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.

◆ dumpData()

void regina::CompactSearcher::dumpData ( std::ostream & out ) const

overridevirtual

Dumps all internal data in a plain text format to the given output stream.

This object can be recreated from this text data by calling the input stream constructor for the appropriate class.

This routine may be useful for transferring objects from one processor to another.

If subclasses override this function, they should write subclass data after superclass data. This means it is safe to dump data from a subclass and then recreate a new superclass object from that data (though subclass-specific information will be lost).

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

The key difference between dumpData() and dumpTaggedData() is that dumpTaggedData() preserves all internal information even if this object belongs to a subclass of GluingPermSearcher, whereas dumpData() only writes information pertaining to this base class.

Warning: The data format is liable to change between Regina releases. Data in this format should be used on a short-term temporary basis only.

Python: Not present; instead use data(), which returns this same information as a string. However, the matching input stream constructor is not available in Python either, so it is recommended that Python users use taggedData() and fromTaggedData() instead.

Parameters

out	the output stream to which the data should be written.

Reimplemented from regina::GluingPermSearcher< 3 >.

Reimplemented in regina::ClosedPrimeMinSearcher.

◆ dumpTaggedData()

void regina::GluingPermSearcher< 3 >::dumpTaggedData ( std::ostream & out ) const

inlineinherited

Dumps all internal data in a plain text format, along with a marker to signify which precise class the data belongs to.

This routine can be used with fromTaggedData() to transport objects from place to place whose precise class is unknown.

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

The key difference between dumpData() and dumpTaggedData() is that dumpTaggedData() preserves all internal information even if this object belongs to a subclass of GluingPermSearcher, whereas dumpData() only writes information pertaining to this base class.

Warning: The data format is liable to change between Regina releases. Data in this format should be used on a short-term temporary basis only.

Python: Not present; instead use taggedData(), which returns this same information as a string.

Parameters

out	the output stream to which the data should be written.

◆ findAllPerms()

template<typename Action , typename... Args>

void regina::GluingPermSearcher< 3 >::findAllPerms	(	FacetPairing< 3 >	pairing,
		FacetPairing< 3 >::IsoList	autos,
		bool	orientableOnly,
		bool	finiteOnly,
		CensusPurge	whichPurge,
		Action &&	action,
		Args &&...	args
	)

inlinestaticinherited

The main entry routine for running a search for all gluing permutation sets that complement a given face pairing.

This routine examines the search parameters, chooses the best possible search algorithm, constructs an object of the corresponding subclass of GluingPermSearcher<3> and then calls runSearch().

See the GluingPermSearcher<3> constructor for documentation on the arguments to this routine. See the runSearch() method for documentation on how the search runs and returns its results via action and args..

Precondition: The given face pairing is connected, i.e., it is possible to reach any tetrahedron from any other tetrahedron via a series of matched face pairs.; The given face pairing is in canonical form as described by FacetPairing<3>::isCanonical(). Note that all face pairings constructed by FacetPairing<3>::findAllPairings() are of this form.

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

◆ findEdgeClass() [1/2]

int regina::CompactSearcher::findEdgeClass ( int edgeID ) const

inlineprotected

Returns the representative of the equivalence class containing the given tetrahedron edge.

The class representative is defined to be the root of the corresponding union-find tree.

See the TetEdgeState class for further details. See also the other variant of findEdgeClass(), which is slightly slower but which also tracks edge orientation.

Parameters

edgeID the index of a single tetrahedron edge; this must be between 0 and 6t-1 inclusive, where t is the number of tetrahedra. See the TetEdgeState class notes for details on edge indexing.

Returns: the index of the tetrahedron edge at the root of the union-find tree, i.e., the representative of the equivalence class.

◆ findEdgeClass() [2/2]

int regina::CompactSearcher::findEdgeClass	(	int	edgeID,
		char &	twisted
	)		const

inlineprotected

Returns the representative of the equivalence class containing the given tetrahedron edge.

The class representative is defined to be the root of the corresponding union-find tree.

The argument twisted is also modified to indicate whether or not the identification of the given edge with the class representative preserves orientation. Note that this arugment is not initialised. Instead, if the identification is orientation-preserving then twisted will be left unmodified, and if it is orientation-reversing then twisted will be changed from 0 to 1 or vice-versa.

See the TetEdgeState class for further details. See also the other variant of findEdgeClass(), which is slightly faster but which does not track edge orientation.

Parameters

edgeID	the index of a single tetrahedron edge; this must be between 0 and 6t-1 inclusive, where t is the number of tetrahedra. See the TetEdgeState class notes for details on edge indexing.
twisted	used to track edge orientation, as described above. This must be either 0 or 1 as it is passed into the function, and it will also be either 0 or 1 upon returning from the function.

Returns: the index of the tetrahedron edge at the root of the union-find tree, i.e., the representative of the equivalence class.

◆ fromTaggedData() [1/2]

std::unique_ptr< GluingPermSearcher< 3 > > regina::GluingPermSearcher< 3 >::fromTaggedData ( const std::string & data )

inlinestaticinherited

Creates a new search manager based on tagged data stored in the given string.

This may be a new search or a partially completed search.

The tagged data should be in the format returned by taggedData(). The precise class of the search manager will be determined from the tagged data, and does not need to be known in advance. This is in contrast to dumpData() and the input stream constructors, where the class of the data being read must be known at compile time.

Warning: The data format is liable to change between Regina releases. Data in this format should be used on a short-term temporary basis only.

Exceptions

InvalidArgument the data found in the given string is invalid, incomplete, or incorrectly formatted.

Parameters

data	the tagged data from which to reconstruct a search manager.

Returns: the new search manager, or null if the data in the given string was invalid or incorrectly formatted.

◆ fromTaggedData() [2/2]

std::unique_ptr< GluingPermSearcher< 3 > > regina::GluingPermSearcher< 3 >::fromTaggedData ( std::istream & in )

inlinestaticinherited

Creates a new search manager based on tagged data read from the given input stream.

This may be a new search or a partially completed search.

The tagged data should be in the format written by dumpTaggedData(). The precise class of the search manager will be determined from the tagged data, and does not need to be known in advance. This is in contrast to dumpData() and the input stream constructors, where the class of the data being read must be known at compile time.

Warning: The data format is liable to change between Regina releases. Data in this format should be used on a short-term temporary basis only.

Exceptions

InvalidInput the data found in the given input stream is invalid, incomplete, or incorrectly formatted.

Python: Not present; instead you can use the variant of fromTaggedData() that takes its input as a string.

Parameters

in	the input stream from which to read.

Returns: the new search manager, or null if the data in the input stream was invalid or incorrectly formatted.

◆ isCanonical()

bool regina::GluingPermSearcher< 3 >::isCanonical ( ) const

protectedinherited

Compares the current set of gluing permutations with its preimage under each automorphism of the underlying face pairing, in order to see whether the current set is in canonical form (i.e., is lexicographically smallest).

Returns: true if the current set is in canonical form, or false otherwise.

◆ isComplete()

bool regina::GluingPermSearcher< 3 >::isComplete ( ) const

inlineinherited

Determines whether this search manager holds a complete gluing permutation set or just a partially completed search state.

This may assist the action routine when running partial depth-based searches. See partialSearch() for further details.

Returns: true if a complete gluing permutation set is held, or false otherwise.

◆ lowDegreeEdge()

bool regina::GluingPermSearcher< 3 >::lowDegreeEdge	(	const FacetSpec< 3 > &	face,
		bool	testDegree12,
		bool	testDegree3
	)		const

protectedinherited

Determines whether the permutations already constructed model a triangulation with a low degree edge.

Precisely which types of low degree edges are identified must be specified through parameters testDegree12 and testDegree3.

Tests that do not refer to the gluing permutation for the given face will not be run.

This routine is not fussy about the order in which gluing permutations are selected, as long as permutations not yet selected have the corresponding element of permIndices[] set to -1.

Parameters

face	the specific tetrahedron face upon which tests will be based.
testDegree12	`true` if we should test for non-boundary edges of degree 1 or 2.
testDegree3	`true` if we should test for non-boundary edges of degree 3 involving three distinct tetrahedra.

Returns: true if the permutations under construction will lead to a low-degree edge as specified by parameters testDegree12 and testDegree3, or false if no such edge is found.

◆ mergeEdgeClasses()

bool regina::CompactSearcher::mergeEdgeClasses ( )

protected

Merge the classes of tetrahedron edges as required by the new gluing made at stage orderElt of the search.

See the TetEdgeState class for details.

This routine returns a boolean that indicates whether this merge creates an invalid edge (i.e., an edge identified with itself in reverse).

Returns: true if this merge creates an invalid edge, or false if not.

◆ mergeVertexClasses()

int regina::CompactSearcher::mergeVertexClasses ( )

protected

Merge the classes of tetrahedron vertices as required by the new gluing made at stage orderElt of the search.

See the TetVertexState class for details.

This routine returns a bitwise (OR) combination of the VLINK_... flags defined earlier in this class. These flags describe what happened to the vertex links during this particular merge. In particular, they note when a vertex link is closed off, or is made into something other than a punctured 2-sphere.

Returns: a combination of VLINK_... flags describing how the vertex links were changed, or 0 if none of the changes described by these flags were observed.

◆ partialSearch()

template<typename Action , typename... Args>

void regina::GluingPermSearcher< 3 >::partialSearch	(	long	maxDepth,
		Action &&	action,
		Args &&...	args
	)

inlineinherited

Runs a partial search for all possible gluing permutations that satisfy the search criteria, branching only to the given depth and no further.

This routine essentially does some but not all of the work of runSearch(). See the runSearch() documentation for a detailed overview of what the full search aims to achieve.

If runSearch() enumerates an entire search tree, then you can think of partialSearch() as only enumerating the first maxDepth levels of this search tree. Rather than producing complete gluing permutation sets, this search will produce a series of partially-constructed permutation sets. A partial searche can be continued by calling runSearch() again on the underlying GluingPermSearcher (perhaps after being frozen, or passed on to a different processor via taggedData() and fromTaggedData()). If necessary, the action routine may call isComplete() to distinguish between a complete set of gluing permutations and a partial search state.

Note that a restarted search will never drop below its initial depth. That is, calling runSearch() with a fixed depth can be used to subdivide the overall search space into many branches, and then calling runSearch() on each resulting partial search will complete each of these branches without overlap.

If the search tree is shallow enough (or if maxDepth is large enough), it is possible that this routine will produce complete gluing permutation sets.

Parameters

maxDepth	the depth of the partial search to run. A negative number indicates that a full search should be run.
action	a function (or other callable object) to call for each permutation set (partial or complete) that is found.
args	any additional arguments that should be passed to action, following the initial permutation set argument.

◆ runSearch()

template<typename Action , typename... Args>

void regina::GluingPermSearcher< 3 >::runSearch	(	Action &&	action,
		Args &&...	args
	)

inlineinherited

Generates all possible gluing permutation sets that satisfy the current search criteria.

The search criteria are specified in the class constructor, or through the static method findAllPerms().

Each set of gluing permutations will be produced precisely once up to equivalence, where equivalence is defined by the given set of automorphisms of the given face pairing.

For each permutation set that is generated, 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 GluingPerms<3>. This will be the permutation set that was found. If action wishes to keep the permutation set, it should take a deep copy (not a reference), since the permutation set may be changed and reused after action returns.
If there are any additional arguments supplied in the list args, then these will be passed as subsequent arguments to action.
action must return void.

It is possible to run only a partial search, branching to a given depth but no further; for this you should use the separate routine partialSearch(), not runSearch().

Todo:: Feature: Allow cancellation of permutation set generation.

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

Parameters

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

◆ searchImpl()

void regina::CompactSearcher::searchImpl	(	long	maxDepth,
		ActionWrapper &&	action
	)

overrideprotectedvirtual

A de-templatised implementation of runSearch() and partialSearch().

Here the templated action plus arguments are bundled together in a wrapper whose full type is known in advance.

Subclasses corresponding to more specialised search criteria should override this routine to use a better optimised algorithm where possible.

See runSearch() and partialSearch() for further details.

Reimplemented from regina::GluingPermSearcher< 3 >.

Reimplemented in regina::ClosedPrimeMinSearcher.

◆ splitEdgeClasses()

void regina::CompactSearcher::splitEdgeClasses ( )

protected

Split the classes of tetrahedron edges to mirror the undoing of the gluing at stage orderElt of the search.

See the TetEdgeState class for details.

◆ splitVertexClasses()

void regina::CompactSearcher::splitVertexClasses ( )

protected

Split the classes of tetrahedron vertices to mirror the undoing of the gluing at stage orderElt of the search.

See the TetVertexState class for details.

◆ str()

template<class T , bool supportsUtf8 = false>

std::string regina::Output< T, 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.

◆ taggedData()

std::string regina::GluingPermSearcher< 3 >::taggedData ( ) const

inlineinherited

Returns all internal data in a plain text format, along with a marker to signify which precise class the data belongs to.

This routine can be used with fromTaggedData() to transport objects from place to place whose precise class is unknown.

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

The key difference between data() and taggedData() is that taggedData() preserves all internal information even if this object belongs to a subclass of GluingPermSearcher, whereas data() only writes information pertaining to this base class.

Warning: The data format is liable to change between Regina releases. Data in this format should be used on a short-term temporary basis only.

Returns: all of this object's internal data in plain text format.

◆ utf8()

template<class T , bool supportsUtf8 = false>

std::string regina::Output< T, 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.

◆ vtxBdryBackup()

void regina::CompactSearcher::vtxBdryBackup ( int vertexID )

inlineprotected

Copies the bdryNext and bdryTwist arrays to the bdryNextOld and bdryTwistOld arrays for the given tetrahedron vertex.

See the TetVertexState class for further information.

Parameters

vertexID the tetrahedron vertex on which to operate; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.

◆ vtxBdryConsistencyCheck()

void regina::CompactSearcher::vtxBdryConsistencyCheck ( )

protected

Runs a number of tests on all tetrahedron vertices to locate consistency errors in the bdryEdges, bdryNext and bdryTwist members of the TetVertexState class.

Any errors that are identified will be written to standard error. Note that some errors might be harmless (for instance, when a call to mergeVertexClasses() leaves processing incomplete because it has located a bad vertex link and expects the merge to be immediately undone).

◆ vtxBdryDump()

void regina::CompactSearcher::vtxBdryDump ( std::ostream & out )

protected

Dumps a summary of bdryNext, bdryTwist and bdryEdges for every vertex of every tetrahedron to the given output stream.

The output format is relatively compact, and is subject to change in future versions of Regina. The output uses one line only, and a final newline is written.

See the TetVertexState class for further information.

Parameters

out	the output stream to which to write.

◆ vtxBdryFixAdj()

void regina::CompactSearcher::vtxBdryFixAdj ( int vertexID )

inlineprotected

Adjusts the bdryNext and bdryTwist arrays for nearby tetrahedron vertices, to ensure that these arrays are consistent with the bdryNext and bdryTwist arrays stored with the given vertex.

It is assumed that the vertex linking triangle for the given tetrahedron vertex contributes at least one boundary edge to the vertex link. Recall from the TetVertexState class notes that the bdryNext and bdryTwist arrays for the given vertex describe the boundary edges that follow on in either direction from the boundary edges supplied by this triangle.

This routine locates the tetrahedron vertices that provide the neighbouring boundary edges, and adjusts the bdryNext and bdryTwist arrays for these neighbouring vertices to point back to the given vertex.

This routine is intended to assist with backtracking. This routine is safe to use if the given tetrahedron vertex points to itself (i.e., it provides a complete boundary cycle of three edges in the vertex link).

See the TetVertexState class for further information.

Precondition: The vertex linking triangle for the given tetrahedron vertex contributes at least one boundary edge to the vertex link.

Parameters

vertexID the tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.

◆ vtxBdryJoin()

void regina::CompactSearcher::vtxBdryJoin	(	int	vertexID,
		char	end,
		int	adjVertexID,
		char	twist
	)

inlineprotected

Signifies that the boundary edges supplied by the vertex linking triangles for the two given tetrahedron vertices should be marked as adjacent.

The bdryNext and bdryTwist arrays for each vertex will be adjusted to point to the other.

See the TetVertexState class for details.

Parameters

vertexID	the first tetrahedron vertex on which to operate; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
end	specifies in which direction the adjacent boundary edges lie. This must be either 0 or 1, and its value should correspond to the relevant index in the bdryNext and bdryTwist arrays for vertex vertexID.
adjVertexID	the tetrahedron vertex whose boundary edges are adjacent to the boundary edges supplied by vertexID; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
twist	0 if the orientations of the two boundary segments of vertex link are oriented in the same direction, or 1 if they are oriented in opposite directions; see the bdryTwist documentation for details.

◆ vtxBdryLength1()

bool regina::CompactSearcher::vtxBdryLength1 ( int vertexID )

inlineprotected

Determines whether one of the edges of the vertex linking triangle for the given tetrahedron vertex in fact forms an entire one-edge boundary component of the overall vertex link.

See the TetVertexState class for further information.

Parameters

vertexID the tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.

Returns: true if a one-edge boundary component is formed as described above, or false otherwise.

◆ vtxBdryLength2()

bool regina::CompactSearcher::vtxBdryLength2	(	int	vertexID1,
		int	vertexID2
	)

inlineprotected

Determines whether edges of the vertex linking triangles for each of the given tetrahedron vertices combine to form an entire two-edge boundary component of the overall vertex link, with one edge from each triangle.

See the TetVertexState class for further information.

Parameters

vertexID1	the first tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
vertexID2	the second tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.

Returns: true if a two-edge boundary component is formed as described above, or false otherwise.

◆ vtxBdryNext()

void regina::CompactSearcher::vtxBdryNext	(	int	vertexID,
		int	tet,
		int	vertex,
		int	bdryFace,
		int	next[2],
		char	twist[2]
	)

inlineprotected

Assuming the given edge of the vertex linking triangle for the given tetrahedron vertex lies on the boundary of the vertex link, this routine identifies the adjacent boundary edges of the vertex link in each direction.

The given edge of the vertex linking triangle must belong to one of the two tetrahedron faces currently being joined.

The tetrahedron vertex to examine is passed in vertexID, tet and vertex, and the particular edge of the vertex linking triangle to examine is specified by bdryFace. Details of the adjacent boundary edges are returned in the arrays next and twist.

Note that the values returned might or might not correspond to the bdryNext and bdryTwist arrays of the TetVertexState class, since the TetVertexState arrays skip over adjacent edges belonging to the same vertex linking triangle.

If the given edge of the vertex linking triangle is not a boundary edge of the vertex link, the behaviour of this routine is undefined.

See the TetVertexState class for further information.

Precondition: The tetrahedron face (tet, bdryFace) is one of the two faces that are currently being joined together. That is, this face is either order[orderElt] or its partner in the underlying face pairing.

Parameters

vertexID	the tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
tet	the tetrahedron described by vertexID; this must be (vertexID / 4). It is passed separately to avoid a slow division operation.
vertex	the tetrahedron vertex number described by vertexID; this must be (vertexID % 4). It is passed separately to avoid a slow modulus operation.
bdryFace	the face number of the given tetrahedron containing the edge of the vertex linking triangle that is under consideration. This must be between 0 and 3 inclusive, and it may not be equal to vertex.
next	returns the tetrahedron vertex supplying each adjacent boundary edge; see the TetVertexState::bdryNext notes for details on which directions correspond to array indices 0 and 1.
twist	returns whether the orientations of the adjacent boundary edges are consistent with the orientation of this boundary edge; see the TetVertexState::bdryTwist notes for further information on orientations in the vertex link.

◆ vtxBdryRestore()

void regina::CompactSearcher::vtxBdryRestore ( int vertexID )

inlineprotected

Copies the bdryNextOld and bdryTwistOld arrays to the bdryNext and bdryTwist arrays for the given tetrahedron vertex.

See the TetVertexState class for further information.

Parameters

vertexID the tetrahedron vertex on which to operate; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.

◆ writeTextLong()

void regina::ShortOutput< GluingPermSearcher< 3 > , 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::GluingPermSearcher< 3 >::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.

Member Data Documentation

◆ autos_

const FacetPairing<3>::IsoList regina::GluingPermSearcher< 3 >::autos_

protectedinherited

The set of isomorphisms that define equivalence of gluing permutation sets.

Generally this is the set of all automorphisms of the underlying face pairing.

◆ dataTag

constexpr char regina::CompactSearcher::dataTag = 'f'

staticconstexpr

A character used to identify this class when reading and writing tagged data in text format.

◆ edgeState

TetEdgeState* regina::CompactSearcher::edgeState

protected

Used for tracking equivalence classes of identified tetrahedron edges.

See the TetEdgeState description for details. This array has size 6n, where edge e of tetrahedron t has index 6t+e.

◆ edgeStateChanged

int* regina::CompactSearcher::edgeStateChanged

protected

Tracks the way in which the edgeState[] array has been updated over time.

This array has size 8n. Suppose the gluing for order[i] affects face f of tetrahedron t. Then element 4i+v of this array describes how the gluing for order[i] affects the edge of tetrahedron t opposite vertices f and v (note that a quarter of this array will remain unused, since f and v are never equal).

If this identification of edges results in the tree with root edgeState[p] being grafted beneath the tree with root edgeState[q], this array will store the value p. Otherwise it will store the value -1.

◆ finiteOnly_

bool regina::GluingPermSearcher< 3 >::finiteOnly_

protectedinherited

Are we only searching for gluing permutations that correspond to finite triangulations?

◆ nEdgeClasses

unsigned regina::CompactSearcher::nEdgeClasses

protected

The number of equivalence classes of identified tetrahedron edges.

◆ nVertexClasses

unsigned regina::CompactSearcher::nVertexClasses

protected

The number of equivalence classes of identified tetrahedron vertices.

◆ order

FacetSpec<3>* regina::GluingPermSearcher< 3 >::order

protectedinherited

Describes the order in which gluing permutations are assigned to faces.

Specifically, this order is order[0], order[1], ..., order[orderSize-1].

Note that each element of this array corresponds to a single edge of the underlying face pairing graph, which in turn represents a tetrahedron face and its image under the given face pairing.

The specific tetrahedron face stored in this array for each edge of the underlying face pairing graph will be the smaller of the two identified tetrahedron faces (unless otherwise specified for a particular edge type; see ClosedPrimeMinSearcher for examples).

◆ orderElt

int regina::GluingPermSearcher< 3 >::orderElt

protectedinherited

Marks which element of order[] we are currently examining at this stage of the search.

◆ orderSize

int regina::GluingPermSearcher< 3 >::orderSize

protectedinherited

The total number of edges in the face pairing graph, i.e., the number of elements of interest in the order[] array.

◆ orientableOnly_

bool regina::GluingPermSearcher< 3 >::orientableOnly_

protectedinherited

Are we only searching for gluing permutations that correspond to orientable triangulations?

◆ orientation

int* regina::GluingPermSearcher< 3 >::orientation

protectedinherited

Keeps track of the orientation of each tetrahedron in the underlying triangulation.

Orientation is positive/negative, or 0 if unknown. Note that in some algorithms the orientation is simply +/-1, and in some algorithms the orientation counts forwards or backwards from 0 according to how many times the orientation has been set or verified.

◆ perms_

GluingPerms<3> regina::GluingPermSearcher< 3 >::perms_

protectedinherited

The set of gluing permutations under construction.

◆ started

bool regina::GluingPermSearcher< 3 >::started

protectedinherited

Has the search started yet? This helps distinguish between a new search and the resumption of a partially completed search.

◆ vertexLinkNextFace

const int regina::CompactSearcher::vertexLinkNextFace[4][4]

staticprotected

Maintains an ordering of the three tetrahedron faces surrounding a vertex in a tetrahedron.

This ordering is consistent with the orientations of triangles in the vertex link used by TetVertexState::twistUp.

For vertex v (0..3), the tetrahedron face that follows f (0..3) in this ordering is vertexLinkNextFace[v][f]. The remaining array elements vertexLinkNextFace[v][v] are all -1.

◆ vertexLinkPrevFace

const int regina::CompactSearcher::vertexLinkPrevFace[4][4]

staticprotected

Provides backwards links for the ordering described by vertexLinkNextFace.

For vertex v (0..3), the tetrahedron face that precedes f (0..3) in this ordering is vertexLinkPrevFace[v][f]. The remaining array elements vertexLinkPrevFace[v][v] are all -1.

◆ vertexState

TetVertexState* regina::CompactSearcher::vertexState

protected

Used for tracking equivalence classes of identified tetrahedron vertices.

See the TetVertexState description for details. This array has size 4n, where vertex v of tetrahedron t has index 4t+v.

◆ vertexStateChanged

int* regina::CompactSearcher::vertexStateChanged

protected

Tracks the way in which the vertexState[] array has been updated over time.

This array has size 8n, where element 4i+v describes how the gluing for order[i] affects vertex v of the corresponding tetrahedron (thus a quarter of this array will remain unused, since only three vertices are affected for each gluing).

If this identification of vertices results in the tree with root vertexState[p] being grafted beneath the tree with root vertexState[q], this array will store the value p. Otherwise it will store the value -1.

◆ VLINK_CLOSED

constexpr char regina::CompactSearcher::VLINK_CLOSED = 1

staticconstexprprotected

Signifies that a vertex link has been closed off (i.e., the link has no remaining boundary edges).

◆ VLINK_NON_SPHERE

constexpr char regina::CompactSearcher::VLINK_NON_SPHERE = 2

staticconstexprprotected

Signifies that a vertex link has been made into something other than a 2-sphere with zero or more punctures.

◆ whichPurge_

CensusPurge regina::GluingPermSearcher< 3 >::whichPurge_

protectedinherited

Are there any types of triangulation that we may optionally avoid constructing? This should be a bitwise OR of constants from the CensusPurgeFlags enumeration.

See the constructor documentation for further details on this search parameter.

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

census/gluingpermsearcher3.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Protected Attributes

Static Protected Attributes

Detailed Description

Member Typedef Documentation

◆ ActionWrapper

◆ PurgeFlags

Constructor & Destructor Documentation

◆ CompactSearcher() [1/2]

◆ CompactSearcher() [2/2]

◆ ~CompactSearcher()

Member Function Documentation

◆ badEdgeLink()

◆ bestSearcher()

◆ completePermSet()

◆ data()

◆ dataTagInternal()

◆ detail()

◆ dumpData()

◆ dumpTaggedData()

◆ findAllPerms()

◆ findEdgeClass() [1/2]

◆ findEdgeClass() [2/2]

◆ fromTaggedData() [1/2]

◆ fromTaggedData() [2/2]

◆ isCanonical()

◆ isComplete()

◆ lowDegreeEdge()

◆ mergeEdgeClasses()

◆ mergeVertexClasses()

◆ partialSearch()

◆ runSearch()

◆ searchImpl()

◆ splitEdgeClasses()

◆ splitVertexClasses()

◆ str()

◆ taggedData()

◆ utf8()

◆ vtxBdryBackup()

◆ vtxBdryConsistencyCheck()

◆ vtxBdryDump()

◆ vtxBdryFixAdj()

◆ vtxBdryJoin()

◆ vtxBdryLength1()

◆ vtxBdryLength2()

◆ vtxBdryNext()

◆ vtxBdryRestore()

◆ writeTextLong()

◆ writeTextShort()

Member Data Documentation

◆ autos_

◆ dataTag

◆ edgeState

◆ edgeStateChanged

◆ finiteOnly_

◆ nEdgeClasses

◆ nVertexClasses

◆ order

◆ orderElt

◆ orderSize

◆ orientableOnly_

◆ orientation

◆ perms_

◆ started

◆ vertexLinkNextFace

◆ vertexLinkPrevFace

◆ vertexState

◆ vertexStateChanged

◆ VLINK_CLOSED

◆ VLINK_NON_SPHERE

◆ whichPurge_