A utility class for searching through all possible gluing permutation sets that correspond to a given pentachoron facet pairing. More...

#include <census/gluingpermsearcher4.h>

Inheritance diagram for regina::GluingPermSearcher< 4 >:

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

struct	PentTriangleState
	A structure used to track equivalence classes of pentachoron triangles as the gluing permutation set is constructed. More...

Public Member Functions
	GluingPermSearcher (FacetPairing< 4 > pairing, FacetPairing< 4 >::IsoList autos, bool orientableOnly, bool finiteOnly)
	Initialises a new search for gluing permutation sets. More...

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

virtual	~GluingPermSearcher ()
	Destroys this search manager and all supporting data structures. 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...

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

virtual void	dumpData (std::ostream &out) const
	Dumps all internal data in a plain text format to the given output stream. 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...

	GluingPermSearcher (const GluingPermSearcher &)=delete

GluingPermSearcher &	operator= (const GluingPermSearcher &)=delete

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< 4 > pairing, FacetPairing< 4 >::IsoList autos, bool orientableOnly, bool finiteOnly, Action &&action, Args &&... args)
	The main entry routine for running a search for all gluing permutation sets that complement a given pentachoron facet pairing. More...

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

static std::unique_ptr< GluingPermSearcher< 4 > >	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< 4 > >	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 = 'g'
	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< 4 > &)>
	The type used to hold the user's action function and arguments when enumerating gluing permutations. More...

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

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

bool	badTriangleLink (const FacetSpec< 4 > &facet) const
	Determines whether the permutations already constructed model a 4-manifold triangulation with a (2-dimensional) triangle identified with itself using a non-trivial rotation or reflection. More...

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

size_t	findTriangleClass (size_t triID) const
	Returns the representative of the equivalence class containing the given pentachoron triangle. More...

size_t	findTriangleClass (size_t triID, Perm< 3 > &twist) const
	Returns the representative of the equivalence class containing the given pentachoron triangle. More...

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

bool	mergeTriangleClasses ()
	Merges the classes of pentachoron triangles as required by the new gluing made at stage orderElt of the search. More...

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

void	splitTriangleClasses ()
	Splits the classes of pentachoron triangles to mirror the undoing of the gluing at stage orderElt of the search. More...

void	edgeBdryJoin (size_t edgeID, char end, size_t adjEdgeID, char twist)
	Signifies that the boundary edges supplied by the linking triangles for the two given pentachoron edges should be marked as adjacent. More...

void	edgeBdryFixAdj (size_t edgeID)
	Adjusts the bdryNext and bdryTwist arrays for nearby pentachoron edges, to ensure that these arrays are consistent with the bdryNext and bdryTwist arrays stored with the given pentachoron edge. More...

void	edgeBdryBackup (size_t edgeID)
	Copies the bdryNext and bdryTwist arrays to the bdryNextOld and bdryTwistOld arrays for the given pentachoron edge. More...

void	edgeBdryRestore (size_t edgeID)
	Copies the bdryNextOld and bdryTwistOld arrays to the bdryNext and bdryTwist arrays for the given pentachoron edge. More...

void	edgeBdryNext (size_t edgeID, size_t pent, int edge, int bdryFacet, size_t next[2], char twist[2])
	Assuming the given edge of the linking triangle for the given pentachoron edge lies on the boundary of the link, this routine identifies the adjacent boundary edges of the link in each direction. More...

bool	edgeBdryLength1 (size_t edgeID)
	Determines whether one of the edges of the linking triangle for the given pentachoron edge in fact forms an entire one-edge boundary component of the overall 4-manifold edge link. More...

bool	edgeBdryLength2 (size_t edgeID1, size_t edgeID2)
	Determines whether edges of the linking triangles for each of the given pentachoron edges combine to form an entire two-edge boundary component of the overall 4-manifold edge link, with one edge from each triangle. More...

void	edgeBdryConsistencyCheck ()
	Runs a number of tests on all pentachoron edges to locate consistency errors in the bdryEdges, bdryNext and bdryTwist members of the PentEdgeState class. More...

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

Protected Attributes
GluingPerms< 4 >	perms_
	The set of gluing permutations under construction. More...

const FacetPairing< 4 >::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 (non-ideal) triangulations? 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 pentachoron in the underlying triangulation. More...

FacetSpec< 4 > *	order_
	Describes the order in which gluing permutations are assigned to pentachoron facets. More...

size_t	orderSize_
	The total number of edges in the facet pairing graph, i.e., the number of elements of interest in the order_[] array. More...

ssize_t	orderElt_
	Marks which element of order_[] we are currently examining at this stage of the search. More...

size_t	nEdgeClasses_
	The number of equivalence classes of identified pentachoron edges. More...

PentEdgeState *	edgeState_
	Used for tracking equivalence classes of identified pentachoron edges. More...

ssize_t *	edgeStateChanged_
	Tracks the way in which the edgeState_[] array has been updated over time. More...

size_t	nTriangleClasses_
	The number of equivalence classes of identified pentachoron triangles. More...

PentTriangleState *	triState_
	Used for tracking equivalence classes of identified pentachoron triangles. More...

ssize_t *	triStateChanged_
	Tracks the way in which the triState_[] array has been updated over time. More...

Static Protected Attributes
static const int	edgeLinkNextFacet [10][5]
	Maintains an ordering of the three pentachoron facets surrounding an edge in a pentachoron. More...

static const int	edgeLinkPrevFacet [10][5]
	Provides backwards links for the ordering described by edgeLinkNextFacet. More...

Detailed Description

A utility class for searching through all possible gluing permutation sets that correspond to a given pentachoron facet pairing.

Subclasses of GluingPermSearcher<4> correspond to specialised (and heavily optimised) search algorithms that may be used in sufficiently constrained scenarios. The main class GluingPermSearcher<4> offers a default (but slower) search algorithm that may be used in more general contexts.

The simplest way of performing a search through all possible gluing permutations is by calling the static method findAllPerms(). This will examine the search parameters and ensure that the best possible algorithm is used. For finer control over the program flow, the static method bestSearcher() can be used to create a search manager of the most suitable class and then runSearch() can be called on this object directly. For absolute control, a specific algorithm can be forced by explicitly constructing an object of the corresponding class (and again calling runSearch() on that object directly).

The search algorithm used by this base class employs modified union-find structures for both triangle and edge equivalence classes to prune searches that are guaranteed to lead to invalid triangles or edges. This is a 4-dimensional analogue to the algorithms described in "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.

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< 4 >::ActionWrapper = std::function<void(const GluingPerms<4>&)>

protected

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

Constructor & Destructor Documentation

◆ GluingPermSearcher() [1/2]

regina::GluingPermSearcher< 4 >::GluingPermSearcher	(	FacetPairing< 4 >	pairing,
		FacetPairing< 4 >::IsoList	autos,
		bool	orientableOnly,
		bool	finiteOnly
	)

Initialises a new search for gluing permutation sets.

The search is started by calling runSearch(). Note that the static method findAllPerms() handles both construction and searching, and is the preferred entry point for end users.

The arguments to this constructor describe the search parameters in detail.

The appropriate use of parameters orientableOnly and finiteOnly can significantly speed up the permutation set generation. For some combinations of these parameters entirely different algorithms are used.

Note that even if finiteOnly is set to true, some ideal triangulations might still slip through the net (since the full vertex links are not always constructed). However, setting finiteOnly to true will allow the census algorithm to take shortcuts and therefore run faster. The resulting triangulations may be tested for finiteness (and other properties) by calling triangulate().

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

Parameters

pairing	the specific pairing of pentachoron facets that the generated permutation sets will complement.
autos	the collection of isomorphisms that define equivalence of permutation sets. These are used by runSearch(), which produces each permutation set precisely once up to equivalence. These isomorphisms must all be automorphisms of the given facet pairing, and will generally be the set of all such automorphisms (which you can generate via `pairing.findAutomorphisms()`).
orientableOnly	`true` if only gluing permutations corresponding to orientable triangulations should be generated, or `false` if no such restriction should be imposed.
finiteOnly	`true` if only gluing permutations corresponding to finite (non-ideal) triangulations are required, or `false` if there is no such requirement. Note that regardless of this value, some ideal triangulations might still be produced; see the notes above for details.

◆ GluingPermSearcher() [2/2]

regina::GluingPermSearcher< 4 >::GluingPermSearcher ( 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. 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.

◆ ~GluingPermSearcher()

virtual regina::GluingPermSearcher< 4 >::~GluingPermSearcher ( )

virtual

Destroys this search manager and all supporting data structures.

Member Function Documentation

◆ badTriangleLink()

bool regina::GluingPermSearcher< 4 >::badTriangleLink ( const FacetSpec< 4 > & facet ) const

protected

Determines whether the permutations already constructed model a 4-manifold triangulation with a (2-dimensional) triangle identified with itself using a non-trivial rotation or reflection.

Tests that do not refer to the gluing permutation for the given pentachoron facet 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

facet the specific pentachoron facet upon which tests will be based.

Returns: true if the permutations under construction will lead to a triangle identified with itself using a non-trivial rotation or reflection, or false if no such triangle is found.

◆ bestSearcher()

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

inlinestatic

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

Different subclasses of GluingPermSearcher<4> 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<4> constructor for documentation on the arguments to this routine.

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

Returns: the new search manager.

◆ data()

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

inline

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.

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

◆ dataTagInternal()

char regina::GluingPermSearcher< 4 >::dataTagInternal ( ) const

inlineprotectedvirtual

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

Returns: the class tag.

◆ detail()

std::string regina::Output< GluingPermSearcher< 4 > , 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()

virtual void regina::GluingPermSearcher< 4 >::dumpData ( std::ostream & out ) const

virtual

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. You can 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.

◆ dumpTaggedData()

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

inline

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.

◆ edgeBdryBackup()

void regina::GluingPermSearcher< 4 >::edgeBdryBackup ( size_t edgeID )

inlineprotected

Copies the bdryNext and bdryTwist arrays to the bdryNextOld and bdryTwistOld arrays for the given pentachoron edge.

See the PentEdgeState class for further information.

Parameters

edgeID the pentachoron edge on which to operate; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.

◆ edgeBdryConsistencyCheck()

void regina::GluingPermSearcher< 4 >::edgeBdryConsistencyCheck ( )

protected

Runs a number of tests on all pentachoron edges to locate consistency errors in the bdryEdges, bdryNext and bdryTwist members of the PentEdgeState 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 mergeEdgeClasses() leaves processing incomplete because it has located a bad edge link and expects the merge to be immediately undone).

◆ edgeBdryDump()

void regina::GluingPermSearcher< 4 >::edgeBdryDump ( std::ostream & out )

protected

Dumps a summary of bdryNext, bdryTwist and bdryEdges for every edge of every pentachoron 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 PentEdgeState class for further information.

Parameters

out	the output stream to which to write.

◆ edgeBdryFixAdj()

void regina::GluingPermSearcher< 4 >::edgeBdryFixAdj ( size_t edgeID )

inlineprotected

Adjusts the bdryNext and bdryTwist arrays for nearby pentachoron edges, to ensure that these arrays are consistent with the bdryNext and bdryTwist arrays stored with the given pentachoron edge.

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

This routine locates the pentachoron edges that provide the neighbouring boundary edges of the link, and adjusts the bdryNext and bdryTwist arrays for these neighbouring pentachoron edges to point back to the given pentachoron edge.

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

See the PentEdgeState class for further information.

Precondition: The linking triangle for the given pentachoron edge contributes at least one boundary edge to the 4-manifold edge link.

Parameters

edgeID the pentachoron edge to examine; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.

◆ edgeBdryJoin()

void regina::GluingPermSearcher< 4 >::edgeBdryJoin	(	size_t	edgeID,
		char	end,
		size_t	adjEdgeID,
		char	twist
	)

inlineprotected

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

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

See the PentEdgeState class for details.

Parameters

edgeID	the first pentachoron edge on which to operate; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.
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 edge edgeID.
adjEdgeID	the pentachoron edge whose boundary edges are adjacent to the boundary edges supplied by edgeID; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.
twist	0 if the orientations of the two boundary segments of edge link are oriented in the same direction, or 1 if they are oriented in opposite directions; see the bdryTwist documentation for details.

◆ edgeBdryLength1()

bool regina::GluingPermSearcher< 4 >::edgeBdryLength1 ( size_t edgeID )

inlineprotected

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

See the PentEdgeState class for further information.

Parameters

edgeID the pentachoron edge to examine; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.

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

◆ edgeBdryLength2()

bool regina::GluingPermSearcher< 4 >::edgeBdryLength2	(	size_t	edgeID1,
		size_t	edgeID2
	)

inlineprotected

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

See the PentEdgeState class for further information.

Parameters

edgeID1	the first pentachoron edge to examine; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.
edgeID2	the second pentachoron edge to examine; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.

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

◆ edgeBdryNext()

void regina::GluingPermSearcher< 4 >::edgeBdryNext	(	size_t	edgeID,
		size_t	pent,
		int	edge,
		int	bdryFacet,
		size_t	next[2],
		char	twist[2]
	)

protected

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

The given edge of the linking triangle must belong to one of the two pentachoron facets currently being joined.

The pentachoron edge to examine is passed in edgeID, pent and edge, and the particular edge of the linking triangle to examine is specified by bdryFacet. 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 PentEdgeState class, since the PentEdgeState arrays skip over adjacent edges belonging to the same linking triangle.

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

See the PentEdgeState class for further information.

Precondition: The pentachoron facet (pent, bdryFacet) is one of the two facets that are currently being joined together. That is, this facet is either order_[orderElt_] or its partner in the underlying pentachoron facet pairing.

Parameters

edgeID	the pentachoron edge to examine; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.
pent	the pentachoron described by edgeID; this must be (edgeID / 10). It is passed separately to avoid a slow division operation.
edge	the pentachoron edge number described by edgeID; this must be (edgeID % 10). It is passed separately to avoid a slow modulus operation.
bdryFacet	the facet number of the given pentachoron containing the edge of the linking triangle that is under consideration. This must be between 0 and 4 inclusive.
next	returns the pentachoron edge supplying each adjacent boundary edge of the link; see the PentEdgeState::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 PentEdgeState::bdryTwist notes for further information on orientations in the link.

◆ edgeBdryRestore()

void regina::GluingPermSearcher< 4 >::edgeBdryRestore ( size_t edgeID )

inlineprotected

Copies the bdryNextOld and bdryTwistOld arrays to the bdryNext and bdryTwist arrays for the given pentachoron edge.

See the PentEdgeState class for further information.

Parameters

edgeID the pentachoron edge on which to operate; this must be between 0 and 10n-1 inclusive, where n is the number of pentachora.

◆ findAllPerms()

template<typename Action , typename... Args>

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

inlinestatic

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

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

See the GluingPermSearcher<4> 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 facet pairing is connected, i.e., it is possible to reach any pentachoron from any other pentachoron via a series of matched facet pairs.; The given facet pairing is in canonical form as described by FacetPairing<4>::isCanonical(). Note that all facet pairings constructed by FacetPairing<4>::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).

◆ findTriangleClass() [1/2]

size_t regina::GluingPermSearcher< 4 >::findTriangleClass ( size_t triID ) const

inlineprotected

Returns the representative of the equivalence class containing the given pentachoron triangle.

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

See the PentTriangleState class for further details. See also the other variant of findTriangleClass(), which is slower but which also tracks triangle rotations and reflections.

Parameters

triID the index of a single pentachoron triangle; this must be between 0 and 10p-1 inclusive, where p is the number of pentachora. See the PentTriangleState class notes for details on triangle indexing.

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

◆ findTriangleClass() [2/2]

size_t regina::GluingPermSearcher< 4 >::findTriangleClass	(	size_t	triID,
		Perm< 3 > &	twist
	)		const

inlineprotected

Returns the representative of the equivalence class containing the given pentachoron triangle.

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

The argument twist is also modified to indicate what rotation or reflection is used to identify vertices (0,1,2) of the given triangle with vertices (0,1,2) of the class representative. Note that this argument is not initialised. Instead, the original twist will be multiplied on the left by the mapping described above.

See the PentTriangleState class for further details. See also the other variant of findTriangleClass(), which is faster but which does not track triangle rotations and reflections.

Parameters

triID	the index of a single pentachoron triangle; this must be between 0 and 10p-1 inclusive, where p is the number of pentachora. See the PentTriangleState class notes for details on triangle indexing.
twist	used to track triangle rotations and reflections, as described above. This must be a mapping from (0,1,2) to (0,1,2) as it is passed into the function, and it will also be a mapping from (0,1,2) to (0,1,2) upon returning from the function.

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

◆ fromTaggedData() [1/2]

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

inlinestatic

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< 4 > > regina::GluingPermSearcher< 4 >::fromTaggedData ( std::istream & in )

inlinestatic

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 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< 4 >::isCanonical ( ) const

protected

Compares the current set of gluing permutations with its preimage under each automorphism of the underlying facet 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< 4 >::isComplete ( ) const

inline

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.

◆ mergeEdgeClasses()

bool regina::GluingPermSearcher< 4 >::mergeEdgeClasses ( )

protected

Merges the classes of pentachoron edges as required by the new gluing made at stage orderElt of the search.

See the PentEdgeState class for details.

This routine returns a boolean that indicates whether this merge creates an invalid edge (i.e., an edge with identified with itself in reverse, or whose link is something other than a (possibly) punctured 2-sphere).

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

◆ mergeTriangleClasses()

bool regina::GluingPermSearcher< 4 >::mergeTriangleClasses ( )

protected

Merges the classes of pentachoron triangles as required by the new gluing made at stage orderElt of the search.

See the PentTriangleState class for details.

This routine returns a boolean that indicates whether this merge creates an invalid triangle (i.e., a triangle identified with itself using a non-trivial rotation or reflection).

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

◆ partialSearch()

template<typename Action , typename... Args>

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

inline

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

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

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< 4 >::runSearch	(	Action &&	action,
		Args &&...	args
	)

inline

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

virtual void regina::GluingPermSearcher< 4 >::searchImpl	(	long	maxDepth,
		ActionWrapper &&	action
	)

protectedvirtual

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.

◆ splitEdgeClasses()

void regina::GluingPermSearcher< 4 >::splitEdgeClasses ( )

protected

Splits the classes of pentachoron edges to mirror the undoing of the gluing at stage orderElt of the search.

See the PentEdgeState class for details.

◆ splitTriangleClasses()

void regina::GluingPermSearcher< 4 >::splitTriangleClasses ( )

protected

Splits the classes of pentachoron triangles to mirror the undoing of the gluing at stage orderElt of the search.

See the PentTriangleState class for details.

◆ str()

std::string regina::Output< GluingPermSearcher< 4 > , 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< 4 >::taggedData ( ) const

inline

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

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

◆ writeTextLong()

void regina::ShortOutput< GluingPermSearcher< 4 > , 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< 4 >::writeTextShort ( std::ostream & out ) const

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<4>::IsoList regina::GluingPermSearcher< 4 >::autos_

protected

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

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

◆ dataTag

constexpr char regina::GluingPermSearcher< 4 >::dataTag = 'g'

staticconstexpr

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

◆ edgeLinkNextFacet

const int regina::GluingPermSearcher< 4 >::edgeLinkNextFacet[10][5]

staticprotected

Maintains an ordering of the three pentachoron facets surrounding an edge in a pentachoron.

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

For edge e (0..9), the pentachoron facet that follows f (0..5) in this ordering is edgeLinkNextFacet[e][f]. Note that 2/5 of the values in this array remain unaccounted for; these remaining values are set to -1.

◆ edgeLinkPrevFacet

const int regina::GluingPermSearcher< 4 >::edgeLinkPrevFacet[10][5]

staticprotected

Provides backwards links for the ordering described by edgeLinkNextFacet.

For edge e (0..9), the pentachoron facet that follows f (0..5) in this ordering is edgeLinkPrevFacet[e][f]. Again 2/5 of the values in this array remain unaccounted for, and these remaining values are set to -1.

◆ edgeState_

PentEdgeState* regina::GluingPermSearcher< 4 >::edgeState_

protected

Used for tracking equivalence classes of identified pentachoron edges.

See the PentEdgeState description for details. This array has size 10n, where edge e of pentachoron p has index 10p+e.

◆ edgeStateChanged_

ssize_t* regina::GluingPermSearcher< 4 >::edgeStateChanged_

protected

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

This array has size 25n. Suppose the gluing for order[i] affects facet k of pentachoron p. Then element 10i+e of this array describes how the gluing for order[i] affects edge e of pentachoron p. Note that almost half of this array will remain unused, since only six edges of a pentachoron are affected by any one gluing.

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

◆ finiteOnly_

bool regina::GluingPermSearcher< 4 >::finiteOnly_

protected

Are we only searching for gluing permutations that correspond to finite (non-ideal) triangulations?

◆ nEdgeClasses_

size_t regina::GluingPermSearcher< 4 >::nEdgeClasses_

protected

The number of equivalence classes of identified pentachoron edges.

◆ nTriangleClasses_

size_t regina::GluingPermSearcher< 4 >::nTriangleClasses_

protected

The number of equivalence classes of identified pentachoron triangles.

◆ order_

FacetSpec<4>* regina::GluingPermSearcher< 4 >::order_

protected

Describes the order in which gluing permutations are assigned to pentachoron facets.

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 facet pairing graph, which in turn represents a pentachoron facet and its image under the given facet pairing.

The specific pentachoron facet stored in this array for each edge of the underlying facet pairing graph will be the smaller of the two identified pentachoron facets.

◆ orderElt_

ssize_t regina::GluingPermSearcher< 4 >::orderElt_

protected

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

◆ orderSize_

size_t regina::GluingPermSearcher< 4 >::orderSize_

protected

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

◆ orientableOnly_

bool regina::GluingPermSearcher< 4 >::orientableOnly_

protected

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

◆ orientation_

int* regina::GluingPermSearcher< 4 >::orientation_

protected

Keeps track of the orientation of each pentachoron 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<4> regina::GluingPermSearcher< 4 >::perms_

protected

The set of gluing permutations under construction.

◆ started_

bool regina::GluingPermSearcher< 4 >::started_

protected

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

◆ triState_

PentTriangleState* regina::GluingPermSearcher< 4 >::triState_

protected

Used for tracking equivalence classes of identified pentachoron triangles.

See the PentTriangleState description for details. This array has size 10n, where triangle f of pentachoron p has index 10p+f.

◆ triStateChanged_

ssize_t* regina::GluingPermSearcher< 4 >::triStateChanged_

protected

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

This array has size [25n/2]. Suppose the gluing for order[i] affects facet k of pentachoron p. Then element 5i+v of this array describes how the gluing for order[i] affects the triangle of pentachoron p opposite vertices k and v (note that a fifth of this array will remain unused, since k and v are never equal).

If this identification of triangles results in the tree with root triState_[x] being grafted beneath the tree with root triState_[y], this array will store the value x. Otherwise it will store the value -1.

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

census/gluingpermsearcher4.h

Classes

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

Constructor & Destructor Documentation

◆ GluingPermSearcher() [1/2]

◆ GluingPermSearcher() [2/2]

◆ ~GluingPermSearcher()

Member Function Documentation

◆ badTriangleLink()

◆ bestSearcher()

◆ data()

◆ dataTagInternal()

◆ detail()

◆ dumpData()

◆ dumpTaggedData()

◆ edgeBdryBackup()

◆ edgeBdryConsistencyCheck()

◆ edgeBdryDump()

◆ edgeBdryFixAdj()

◆ edgeBdryJoin()

◆ edgeBdryLength1()

◆ edgeBdryLength2()

◆ edgeBdryNext()

◆ edgeBdryRestore()

◆ findAllPerms()

◆ findTriangleClass() [1/2]

◆ findTriangleClass() [2/2]

◆ fromTaggedData() [1/2]

◆ fromTaggedData() [2/2]

◆ isCanonical()

◆ isComplete()

◆ mergeEdgeClasses()

◆ mergeTriangleClasses()

◆ partialSearch()

◆ runSearch()

◆ searchImpl()

◆ splitEdgeClasses()

◆ splitTriangleClasses()

◆ str()

◆ taggedData()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()

Member Data Documentation

◆ autos_

◆ dataTag

◆ edgeLinkNextFacet

◆ edgeLinkPrevFacet

◆ edgeState_

◆ edgeStateChanged_

◆ finiteOnly_

◆ nEdgeClasses_

◆ nTriangleClasses_

◆ order_

◆ orderElt_

◆ orderSize_

◆ orientableOnly_

◆ orientation_

◆ perms_

◆ started_

◆ triState_

◆ triStateChanged_