#include <ngluingpermsearcher.h>
Public Member Functions | |
NGluingPermSearcher (const NFacePairing *pairing, const NFacePairingIsoList *autos, bool orientableOnly, bool finiteOnly, int whichPurge, UseGluingPerms use, void *useArgs=0) | |
Initialises a new search for gluing permutation sets. | |
NGluingPermSearcher (std::istream &in, UseGluingPerms use, void *useArgs=0) | |
Initialises a new search manager based on data read from the given input stream. | |
virtual | ~NGluingPermSearcher () |
Destroys this search manager and all supporting data structures. | |
virtual void | runSearch (long maxDepth=-1) |
Generates all possible gluing permutation sets that satisfy the current search criteria. | |
virtual bool | completePermSet () const |
Determines whether this search manager holds a complete gluing permutation set or just a partially completed search state. | |
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. | |
virtual void | dumpData (std::ostream &out) const |
Dumps all internal data in a plain text format to the given output stream. | |
Static Public Member Functions | |
static void | findAllPerms (const NFacePairing *pairing, const NFacePairingIsoList *autos, bool orientableOnly, bool finiteOnly, int whichPurge, UseGluingPerms use, void *useArgs=0) |
The main entry routine for running a search for all gluing permutation sets that complement a given face pairing. | |
static NGluingPermSearcher * | bestSearcher (const NFacePairing *pairing, const NFacePairingIsoList *autos, bool orientableOnly, bool finiteOnly, int whichPurge, UseGluingPerms use, void *useArgs=0) |
Constructs a search manager of the best possible class for the given search parameters. | |
static NGluingPermSearcher * | readTaggedData (std::istream &in, UseGluingPerms use, void *useArgs=0) |
Creates a new search manager based on tagged data read from the given input stream. | |
Static Public Attributes | |
static const char | dataTag_ |
A character used to identify this class when reading and writing tagged data in text format. | |
Protected Member Functions | |
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). | |
bool | badEdgeLink (const NTetFace &face) const |
Determines whether the permutations already constructed model a triangulation with an edge identified with itself in reverse. | |
bool | lowDegreeEdge (const NTetFace &face, bool testDegree12, bool testDegree3) const |
Determines whether the permutations already constructed model a triangulation with a low degree edge. | |
bool | mayPurge (const NTetFace &face) const |
Determines whether the permutations under construction are doomed to model a triangulation that can be purged from the census. | |
virtual char | dataTag () const |
Returns the character used to identify this class when storing tagged data in text format. | |
Protected Attributes | |
const NFacePairingIsoList * | autos_ |
The set of isomorphisms that define equivalence of gluing permutation sets. | |
bool | autosNew |
Did we create the isomorphism list autos_ ourselves (in which case we must destroy it also)? | |
bool | orientableOnly_ |
Are we only searching for gluing permutations that correspond to orientable triangulations? | |
bool | finiteOnly_ |
Are we only searching for gluing permutations that correspond to finite triangulations? | |
int | whichPurge_ |
Are there any types of triangulation that we may optionally avoid constructing? See the constructor documentation for further details on this search parameter. | |
UseGluingPerms | use_ |
A routine to call each time a gluing permutation set is found during the search. | |
void * | useArgs_ |
Additional user-supplied data to be passed as the second argument to the use_ routine. | |
bool | started |
Has the search started yet? This helps distinguish between a new search and the resumption of a partially completed search. | |
int * | orientation |
Keeps track of the orientation of each tetrahedron in the underlying triangulation. |
Subclasses of NGluingPermSearcher correspond to specialised (and heavily optimised) search algorithms that may be used in sufficiently constrained scenarios. The main class NGluingPermSearcher 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).
Note that this class derives from NGluingPerms. The search will involve building and repeatedly modifying the inherited NGluingPerms data in-place.
regina::NGluingPermSearcher::NGluingPermSearcher | ( | const NFacePairing * | pairing, | |
const NFacePairingIsoList * | autos, | |||
bool | orientableOnly, | |||
bool | finiteOnly, | |||
int | whichPurge, | |||
UseGluingPerms | use, | |||
void * | useArgs = 0 | |||
) |
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, as well as what should be done with each gluing permutation set that is found.
Parameter whichPurge may be used to avoid constructing permutation sets that correspond to triangulations satisfying certain constraints (such as non-minimality). The use of this parameter, combined with 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 not all permutation sets described by parameter whichPurge will be avoided (i.e., you may get gluing permutation sets that you did not want). It is guaranteed however that every permutation set whose corresonding triangulation does not satisfy the whichPurge constraints will be generated.
Similarly, even if finiteOnly is set to true
, some non-finite triangulations might still slip through the net (since the full vertex links are not always constructed). However, like whichPurge, setting finiteOnly to true
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().
The given face pairing is in canonical form as described by NFacePairing::isCanonical(). Note that all face pairings constructed by NFacePairing::findAllPairings() are of this form.
pairing | the specific pairing of tetrahedron faces 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 face pairing, and will generally be the set of all such automorphisms. This parameter may be 0, in which case the set of all automorphisms of the given face pairing will be generated and used. | |
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 triangulations are required, or false if there is no such requirement. Note that regardless of this value, some non-finite triangulations might still be produced; see the notes above for details. | |
whichPurge | specifies which permutation sets we may avoid constructing (see the function notes above for details). This should be a bitwise OR of purge constants from class NCensus, or 0 if we should simply generate every possible permutation set. If a variety of purge constants are bitwise ORed together, a permutation set whose triangulation satisfies any of these constraints may be avoided. Note that not all such permutation sets will be avoided, but enough are avoided that the performance increase is noticeable. | |
use | the function to call upon each permutation set that is found. The first parameter passed to this function will be a gluing permutation set. The second parameter will be parameter useArgs as was passed to this routine. | |
useArgs | the pointer to pass as the final parameter for the function use which will be called upon each permutation set found. |
regina::NGluingPermSearcher::NGluingPermSearcher | ( | std::istream & | in, | |
UseGluingPerms | use, | |||
void * | useArgs = 0 | |||
) |
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 readTaggedData() instead.
If the data found in the input stream is invalid or incorrectly formatted, the routine inputError() will return true
but the contents of this object will be otherwise undefined.
in | the input stream from which to read. | |
use | as for the main NGluingPermSearcher constructor. | |
useArgs | as for the main NGluingPermSearcher constructor. |
virtual regina::NGluingPermSearcher::~NGluingPermSearcher | ( | ) | [virtual] |
Destroys this search manager and all supporting data structures.
bool regina::NGluingPermSearcher::badEdgeLink | ( | const NTetFace & | face | ) | const [protected] |
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.
face | the specific tetrahedron face upon which tests will be based. |
true
if the permutations under construction will lead to an edge identified with itself in reverse, or false
if no such edge is identified. static NGluingPermSearcher* regina::NGluingPermSearcher::bestSearcher | ( | const NFacePairing * | pairing, | |
const NFacePairingIsoList * | autos, | |||
bool | orientableOnly, | |||
bool | finiteOnly, | |||
int | whichPurge, | |||
UseGluingPerms | use, | |||
void * | useArgs = 0 | |||
) | [static] |
Constructs a search manager of the best possible class for the given search parameters.
Different subclasses of NGluingPermSearcher 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.
The resulting object is newly created, and must be destroyed by the caller of this routine.
See the NGluingPermSearcher constructor for documentation on the arguments to this routine.
The given face pairing is in canonical form as described by NFacePairing::isCanonical(). Note that all face pairings constructed by NFacePairing::findAllPairings() are of this form.
bool regina::NGluingPermSearcher::completePermSet | ( | ) | const [inline, virtual] |
Determines whether this search manager holds a complete gluing permutation set or just a partially completed search state.
This may assist the use_ routine when running partial depth-based searches. See runSearch() for further details.
true
if a complete gluing permutation set is held, or false
otherwise. Reimplemented in regina::NClosedPrimeMinSearcher.
char regina::NGluingPermSearcher::dataTag | ( | ) | const [inline, protected, virtual] |
Returns the character used to identify this class when storing tagged data in text format.
Reimplemented in regina::NClosedPrimeMinSearcher.
virtual void regina::NGluingPermSearcher::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 this class.
This routine may be useful for transferring objects from one processor to another.
Note that subclass data is written after superclass data, so it is safe to dump data from a subclass and then recreate a new superclass object from that data (though subclass-specific information will of course be lost).
out | the output stream to which the data should be written. |
Reimplemented from regina::NGluingPerms.
Reimplemented in regina::NClosedPrimeMinSearcher.
void regina::NGluingPermSearcher::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.
This routine can be used with readTaggedData() to transport objects from place to place whose precise class is unknown.
out | the output stream to which the data should be written. |
static void regina::NGluingPermSearcher::findAllPerms | ( | const NFacePairing * | pairing, | |
const NFacePairingIsoList * | autos, | |||
bool | orientableOnly, | |||
bool | finiteOnly, | |||
int | whichPurge, | |||
UseGluingPerms | use, | |||
void * | useArgs = 0 | |||
) | [static] |
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 NGluingPermSearcher and then calls runSearch().
See the NGluingPermSearcher constructor for documentation on the arguments to this routine. See the runSearch() method for documentation on how the search runs and returns its results.
The given face pairing is in canonical form as described by NFacePairing::isCanonical(). Note that all face pairings constructed by NFacePairing::findAllPairings() are of this form.
bool regina::NGluingPermSearcher::isCanonical | ( | ) | const [protected] |
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).
true
if the current set is in canonical form, or false
otherwise. bool regina::NGluingPermSearcher::lowDegreeEdge | ( | const NTetFace & | face, | |
bool | testDegree12, | |||
bool | testDegree3 | |||
) | const [protected] |
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.
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. |
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 identified. bool regina::NGluingPermSearcher::mayPurge | ( | const NTetFace & | face | ) | const [protected] |
Determines whether the permutations under construction are doomed to model a triangulation that can be purged from the census.
The conditions under which a triangulation may be purged are specified by the search parameter whichPurge_.
Note that this routine will not identify all triangulations that satisfy the given conditions; however, whenever this routine does return true
it is guaranteed that the permutations under construction will only lead to triangulations that do meet the given conditions.
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.
face | the specific tetrahedron face upon which tests will be based. |
true
if the permutations under construction will only lead to triangulations that may be purged, or false
if the results are inconclusive. static NGluingPermSearcher* regina::NGluingPermSearcher::readTaggedData | ( | std::istream & | in, | |
UseGluingPerms | use, | |||
void * | useArgs = 0 | |||
) | [static] |
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.
If the data found in the input stream is invalid or incorrectly formatted, a null pointer will be returned. Otherwise a newly constructed search manager will be returned, and it is the responsibility of the caller of this routine to destroy it after use.
The arguments use and useArgs are the smae as for the NGluingPermSearcher constructor.
in | the input stream from which to read. |
virtual void regina::NGluingPermSearcher::runSearch | ( | long | maxDepth = -1 |
) | [virtual] |
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, routine use_ (as passed to the class constructor) will be called with that permutation set as an argument.
Once the generation of permutation sets has finished, routine use_ will be called once more, this time with null
as its first (permutation set) argument.
Subclasses corresponding to more specialised search criteria should override this routine to use a better optimised algorithm where possible.
It is possible to run only a partial search, branching to a given depth but no further. In this case, rather than producing complete gluing permutation sets, the search will produce a series of partially-complete NGluingPermSearcher objects. These partial searches may then be restarted by calling runSearch() once more (usually after being frozen or passed on to a different processor). If necessary, the use_ routine may call completePermSet() 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.
maxDepth | the depth of the partial search to run, or a negative number if a full search should be run (the default). |
Reimplemented in regina::NClosedPrimeMinSearcher.
const NFacePairingIsoList* regina::NGluingPermSearcher::autos_ [protected] |
The set of isomorphisms that define equivalence of gluing permutation sets.
Generally this is the set of all automorphisms of the underlying face pairing.
bool regina::NGluingPermSearcher::autosNew [protected] |
Did we create the isomorphism list autos_ ourselves (in which case we must destroy it also)?
const char regina::NGluingPermSearcher::dataTag_ [static] |
A character used to identify this class when reading and writing tagged data in text format.
Reimplemented in regina::NClosedPrimeMinSearcher.
bool regina::NGluingPermSearcher::finiteOnly_ [protected] |
Are we only searching for gluing permutations that correspond to finite triangulations?
bool regina::NGluingPermSearcher::orientableOnly_ [protected] |
Are we only searching for gluing permutations that correspond to orientable triangulations?
int* regina::NGluingPermSearcher::orientation [protected] |
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.
bool regina::NGluingPermSearcher::started [protected] |
Has the search started yet? This helps distinguish between a new search and the resumption of a partially completed search.
UseGluingPerms regina::NGluingPermSearcher::use_ [protected] |
A routine to call each time a gluing permutation set is found during the search.
void* regina::NGluingPermSearcher::useArgs_ [protected] |
Additional user-supplied data to be passed as the second argument to the use_ routine.
int regina::NGluingPermSearcher::whichPurge_ [protected] |
Are there any types of triangulation that we may optionally avoid constructing? See the constructor documentation for further details on this search parameter.