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

#include <census/gluingpermsearcher2.h>

Inheritance diagram for regina::GluingPermSearcher< 2 >:

Public Member Functions
	GluingPermSearcher (FacetPairing< 2 > pairing, FacetPairing< 2 >::IsoList autos, bool orientableOnly)
	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...

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

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

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

static std::unique_ptr< GluingPermSearcher< 2 > >	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< 2 > >	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< 2 > &)>
	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 edge pairing, in order to see whether the current set is in canonical form (i.e., is lexicographically smallest). More...

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

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

const FacetPairing< 2 >::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	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 triangle in the underlying triangulation. More...

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

int	orderSize
	The total number of edges in the edge 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...

Detailed Description

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

In the future, there may be subclasses of GluingPermSearcher<2> that correspond to specialised search algorithms for use in certain scenarios. The main class GluingPermSearcher<2> offers a default search algorithm that may be used in a general context.

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

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

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< 2 >::GluingPermSearcher	(	FacetPairing< 2 >	pairing,
		FacetPairing< 2 >::IsoList	autos,
		bool	orientableOnly
	)

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.

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

Parameters

pairing	the specific pairing of triangle edges 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 edge 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.

◆ GluingPermSearcher() [2/2]

regina::GluingPermSearcher< 2 >::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, 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.

◆ ~GluingPermSearcher()

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

virtual

Destroys this search manager and all supporting data structures.

Member Function Documentation

◆ bestSearcher()

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

inlinestatic

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

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

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

Returns: the new search manager.

◆ completePermSet()

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

inline

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

Parameters

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

◆ dataTagInternal()

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

inlineprotectedvirtual

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

Returns: the class tag.

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

virtual void regina::GluingPermSearcher< 2 >::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; 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< 2 >::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.

◆ findAllPerms()

template<typename Action , typename... Args>

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

static

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

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

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

◆ fromTaggedData() [1/2]

std::unique_ptr< GluingPermSearcher< 2 > > regina::GluingPermSearcher< 2 >::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< 2 > > regina::GluingPermSearcher< 2 >::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 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< 2 >::isCanonical ( ) const

protected

Compares the current set of gluing permutations with its preimage under each automorphism of the underlying edge 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< 2 >::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.

◆ partialSearch()

template<typename Action , typename... Args>

void regina::GluingPermSearcher< 2 >::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 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< 2 >::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 edge 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<2>. 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< 2 >::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.

◆ 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< 2 >::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()

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.

◆ writeTextLong()

void regina::ShortOutput< GluingPermSearcher< 2 > , 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< 2 >::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<2>::IsoList regina::GluingPermSearcher< 2 >::autos_

protected

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

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

◆ dataTag

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

staticconstexpr

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

◆ order

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

protected

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

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

The specific triangle edge stored in this array for each edge of the underlying edge pairing graph will be the smaller of the two identified triangle edges (unless otherwise specified by a subclass that uses a specialised search algorithm.

◆ orderElt

int regina::GluingPermSearcher< 2 >::orderElt

protected

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

◆ orderSize

int regina::GluingPermSearcher< 2 >::orderSize

protected

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

◆ orientableOnly_

bool regina::GluingPermSearcher< 2 >::orientableOnly_

protected

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

◆ orientation

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

protected

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

protected

The set of gluing permutations under construction.

◆ started

bool regina::GluingPermSearcher< 2 >::started

protected

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

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

census/gluingpermsearcher2.h

Public Member Functions

Static Public Member Functions

Static Public Attributes

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ ActionWrapper

Constructor & Destructor Documentation

◆ GluingPermSearcher() [1/2]

◆ GluingPermSearcher() [2/2]

◆ ~GluingPermSearcher()

Member Function Documentation

◆ bestSearcher()

◆ completePermSet()

◆ data()

◆ dataTagInternal()

◆ detail()

◆ dumpData()

◆ dumpTaggedData()

◆ findAllPerms()

◆ fromTaggedData() [1/2]

◆ fromTaggedData() [2/2]

◆ isCanonical()

◆ isComplete()

◆ partialSearch()

◆ runSearch()

◆ searchImpl()

◆ str()

◆ taggedData()

◆ utf8()

◆ writeTextLong()

◆ writeTextShort()

Member Data Documentation

◆ autos_

◆ dataTag

◆ order

◆ orderElt

◆ orderSize

◆ orientableOnly_

◆ orientation

◆ perms_

◆ started