Regina Calculation Engine
Classes | Public Types | Public Member Functions | Static Public Member Functions | Static Public Attributes | Protected Member Functions | Protected Attributes | Static Protected Attributes | List of all members
regina::NCompactSearcher Class Reference

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

#include <census/ngluingpermsearcher.h>

Inheritance diagram for regina::NCompactSearcher:
regina::NGluingPermSearcher regina::NGluingPerms regina::NGenericGluingPerms< 3 > regina::NClosedPrimeMinSearcher

Classes

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

Public Types

enum  PurgeFlags {
  PURGE_NONE = 0, PURGE_NON_MINIMAL = 1, PURGE_NON_PRIME = 2, PURGE_NON_MINIMAL_PRIME = 3,
  PURGE_NON_MINIMAL_HYP = 9, PURGE_P2_REDUCIBLE = 4
}
 Flags to indicate that our enumeration may (at the discretion of the enumeration algorithm) ignore certain classes of triangulations. More...
 
typedef DimTraits< dim >
::FacetPairing 
FacetPairing
 
typedef DimTraits< dim >::Perm Perm
 
typedef DimTraits< dim >::Simplex Simplex
 
typedef DimTraits< dim >
::Triangulation 
Triangulation
 

Public Member Functions

 NCompactSearcher (const NFacePairing *pairing, const NFacePairing::IsoList *autos, bool orientableOnly, int whichPurge, UseGluingPerms use, void *useArgs=0)
 Creates a new search manager for use when only compact 3-manifold triangulations are required. More...
 
 NCompactSearcher (std::istream &in, UseGluingPerms use, void *useArgs=0)
 Initialises a new search manager based on data read from the given input stream. More...
 
virtual ~NCompactSearcher ()
 Destroys this search manager and all supporting data structures. More...
 
virtual void dumpData (std::ostream &out) const
 Dumps all internal data in a plain text format to the given output stream. More...
 
virtual void runSearch (long maxDepth=-1)
 Generates all possible gluing permutation sets that satisfy the current search criteria. More...
 
bool completePermSet () 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...
 
unsigned getNumberOfTetrahedra () const
 Returns the total number of tetrahedra under consideration. More...
 
const NFacePairinggetFacePairing () const
 Returns the specific pairing of tetrahedron faces that this set of gluing permutations complements. More...
 
bool inputError () const
 Was an error found during construction from an input stream? More...
 
unsigned size () const
 Returns the total number of simplices under consideration. More...
 
const FacetPairing * getFacetPairing () const
 Returns the specific pairing of simplex facets that this set of gluing permutations complements. More...
 
Perm gluingPerm (const NFacetSpec< dim > &source) const
 Returns the gluing permutation associated with the given simplex facet. More...
 
Perm gluingPerm (unsigned simp, unsigned facet) const
 Returns the gluing permutation associated with the given simplex facet. More...
 
Triangulation * triangulate () const
 Returns a newly created triangulation as modelled by this set of gluing permutations and the associated simplex facet pairing. More...
 

Static Public Member Functions

static void findAllPerms (const NFacePairing *pairing, const NFacePairing::IsoList *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. More...
 
static NGluingPermSearcherbestSearcher (const NFacePairing *pairing, const NFacePairing::IsoList *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. More...
 
static NGluingPermSearcherreadTaggedData (std::istream &in, UseGluingPerms use, void *useArgs=0)
 Creates a new search manager based on tagged data read from the given input stream. More...
 

Static Public Attributes

static const char dataTag_
 A character used to identify this class when reading and writing tagged data in text format. More...
 

Protected Member Functions

virtual char dataTag () const
 Returns the character used to identify this class when storing tagged data in text format. More...
 
int findEdgeClass (int edgeID) const
 Returns the representative of the equivalence class containing the given tetrahedron edge. More...
 
int findEdgeClass (int edgeID, char &twisted) const
 Returns the representative of the equivalence class containing the given tetrahedron edge. More...
 
int mergeVertexClasses ()
 Merge the classes of tetrahedron vertices as required by the new gluing made at stage orderElt of the search. More...
 
bool mergeEdgeClasses ()
 Merge the classes of tetrahedron edges as required by the new gluing made at stage orderElt of the search. More...
 
void splitVertexClasses ()
 Split the classes of tetrahedron vertices to mirror the undoing of the gluing at stage orderElt of the search. More...
 
void splitEdgeClasses ()
 Split the classes of tetrahedron edges to mirror the undoing of the gluing at stage orderElt of the search. More...
 
void vtxBdryJoin (int vertexID, char end, int adjVertexID, char twist)
 Signifies that the boundary edges supplied by the vertex linking triangles for the two given tetrahedron vertices should be marked as adjacent. More...
 
void vtxBdryFixAdj (int vertexID)
 Adjusts the bdryNext and bdryTwist arrays for nearby tetrahedron vertices, to ensure that these arrays are consistent with the bdryNext and bdryTwist arrays stored with the given vertex. More...
 
void vtxBdryBackup (int vertexID)
 Copies the bdryNext and bdryTwist arrays to the bdryNextOld and bdryTwistOld arrays for the given tetrahedron vertex. More...
 
void vtxBdryRestore (int vertexID)
 Copies the bdryNextOld and bdryTwistOld arrays to the bdryNext and bdryTwist arrays for the given tetrahedron vertex. More...
 
void vtxBdryNext (int vertexID, int tet, int vertex, int bdryFace, int next[2], char twist[2])
 Assuming the given edge of the vertex linking triangle for the given tetrahedron vertex lies on the boundary of the vertex link, this routine identifies the adjacent boundary edges of the vertex link in each direction. More...
 
bool vtxBdryLength1 (int vertexID)
 Determines whether one of the edges of the vertex linking triangle for the given tetrahedron vertex in fact forms an entire one-edge boundary component of the overall vertex link. More...
 
bool vtxBdryLength2 (int vertexID1, int vertexID2)
 Determines whether edges of the vertex linking triangles for each of the given tetrahedron vertices combine to form an entire two-edge boundary component of the overall vertex link, with one edge from each triangle. More...
 
void vtxBdryConsistencyCheck ()
 Runs a number of tests on all tetrahedron vertices to locate consistency errors in the bdryEdges, bdryNext and bdryTwist members of the TetVertexState class. More...
 
void vtxBdryDump (std::ostream &out)
 Dumps a summary of bdryNext, bdryTwist and bdryEdges for every vertex of every tetrahedron to the given output stream. More...
 
bool isCanonical () const
 Compares the current set of gluing permutations with its preimage under each automorphism of the underlying face pairing, in order to see whether the current set is in canonical form (i.e., is lexicographically smallest). More...
 
bool badEdgeLink (const NTetFace &face) const
 Determines whether the permutations already constructed model a triangulation with an edge identified with itself in reverse. More...
 
bool lowDegreeEdge (const NTetFace &face, bool testDegree12, bool testDegree3) const
 Determines whether the permutations already constructed model a triangulation with a low degree edge. More...
 
int & permIndex (const NFacetSpec< dim > &source)
 Returns the index into array Perm::Sn_1 describing how the the given facet is joined to its partner. More...
 
int & permIndex (unsigned simp, unsigned facet)
 Returns the index into array Perm::Sn_1 describing how the the given facet is joined to its partner. More...
 
const int & permIndex (const NFacetSpec< dim > &source) const
 Returns the index into array Perm::Sn_1 describing how the the given facet is joined to its partner. More...
 
const int & permIndex (unsigned simp, unsigned facet) const
 Returns the index into array Perm::Sn_1 describing how the the given facet is joined to its partner. More...
 
int gluingToIndex (const NFacetSpec< dim > &source, const Perm &gluing) const
 Returns the index into array Perm::Sn_1 corresponding to the given gluing permutation from the given facet to its partner. More...
 
int gluingToIndex (unsigned simp, unsigned facet, const Perm &gluing) const
 Returns the index into array Perm::Sn_1 corresponding to the given gluing permutation from the given facet to its partner. More...
 
Perm indexToGluing (const NFacetSpec< dim > &source, int index) const
 Returns the gluing permutation from the given facet to its partner that corresponds to the given index into array Perm::Sn_1. More...
 
Perm indexToGluing (unsigned simp, unsigned facet, int index) const
 Returns the gluing permutation from the given facet to its partner that corresponds to the given index into array Perm::Sn_1. More...
 

Protected Attributes

unsigned nVertexClasses
 The number of equivalence classes of identified tetrahedron vertices. More...
 
TetVertexStatevertexState
 Used for tracking equivalence classes of identified tetrahedron vertices. More...
 
int * vertexStateChanged
 Tracks the way in which the vertexState[] array has been updated over time. More...
 
unsigned nEdgeClasses
 The number of equivalence classes of identified tetrahedron edges. More...
 
TetEdgeStateedgeState
 Used for tracking equivalence classes of identified tetrahedron edges. More...
 
int * edgeStateChanged
 Tracks the way in which the edgeState[] array has been updated over time. More...
 
const NFacePairing::IsoListautos_
 The set of isomorphisms that define equivalence of gluing permutation sets. More...
 
bool autosNew
 Did we create the isomorphism list autos_ ourselves (in which case we must destroy it also)? More...
 
bool orientableOnly_
 Are we only searching for gluing permutations that correspond to orientable triangulations? More...
 
bool finiteOnly_
 Are we only searching for gluing permutations that correspond to finite triangulations? More...
 
int whichPurge_
 Are there any types of triangulation that we may optionally avoid constructing? This should be a bitwise OR of constants from the PurgeFlags enumeration. More...
 
UseGluingPerms use_
 A routine to call each time a gluing permutation set is found during the search. More...
 
void * useArgs_
 Additional user-supplied data to be passed as the second argument to the use_ routine. More...
 
bool started
 Has the search started yet? This helps distinguish between a new search and the resumption of a partially completed search. More...
 
int * orientation
 Keeps track of the orientation of each tetrahedron in the underlying triangulation. More...
 
NTetFaceorder
 Describes the order in which gluing permutations are assigned to faces. More...
 
int orderSize
 The total number of edges in the face pairing graph, i.e., the number of elements of interest in the order[] array. More...
 
int orderElt
 Marks which element of order[] we are currently examining at this stage of the search. More...
 
const FacetPairing * pairing_
 The facet pairing that this permutation set complements. More...
 
int * permIndices_
 The index into array Perm::Sn_1 describing how each simplex facet is glued to its partner. More...
 
bool inputError_
 Has an error occurred during construction from an input stream? More...
 

Static Protected Attributes

static const char VLINK_CLOSED
 Signifies that a vertex link has been closed off (i.e., the link has no remaining boundary edges). More...
 
static const char VLINK_NON_SPHERE
 Signifies that a vertex link has been made into something other than a 2-sphere with zero or more punctures. More...
 
static const int vertexLinkNextFace [4][4]
 Maintains an ordering of the three tetrahedron faces surrounding a vertex in a tetrahedron. More...
 
static const int vertexLinkPrevFace [4][4]
 Provides backwards links for the ordering described by vertexLinkNextFace. More...
 

Detailed Description

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

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

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

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

Python:
Not present.

Member Enumeration Documentation

Flags to indicate that our enumeration may (at the discretion of the enumeration algorithm) ignore certain classes of triangulations.

These flags can be combined using bitwise OR.

See the NGluingPermSearcher constructor documentation for further details on how these flags are used.

Python:
For convenience, these constants are also made available directly in Python's regina namespace.
Enumerator
PURGE_NONE 

Indicates that no triangulations should be ignored.

PURGE_NON_MINIMAL 

Indicates that non-minimal triangulations may be ignored.

PURGE_NON_PRIME 

Indicates that any triangulation that is not prime (i.e., can be written as a non-trivial connected sum) and any bounded triangulation that is reducible over a disc may be ignored.

PURGE_NON_MINIMAL_PRIME 

Indicates that any triangulation that is not prime (i.e., can be written as a non-trivial connected sum), any bounded triangulation that is reducible over a disc and any triangulation that is non-minimal may be ignored.

Note that this is simply a combination of the constants PURGE_NON_MINIMAL and PURGE_NON_PRIME.

PURGE_NON_MINIMAL_HYP 

Indicates that any triangulation that is not a minimal ideal triangulation of a cusped finite-volume hyperbolic 3-manifold may be ignored.

PURGE_P2_REDUCIBLE 

Indicates that any triangulation containing an embedded two-sided projective plane may be ignored.

Constructor & Destructor Documentation

regina::NCompactSearcher::NCompactSearcher ( const NFacePairing pairing,
const NFacePairing::IsoList autos,
bool  orientableOnly,
int  whichPurge,
UseGluingPerms  use,
void *  useArgs = 0 
)

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

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

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

Precondition
The given face pairing is connected, i.e., it is possible to reach any tetrahedron from any other tetrahedron via a series of matched face pairs.
The given face pairing is in canonical form as described by NFacePairing::isCanonical(). Note that all face pairings constructed by NFacePairing::findAllPairings() are of this form.
regina::NCompactSearcher::NCompactSearcher ( 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.

The arguments use and useArgs are the same as for the NGluingPermSearcher constructor.

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.
Parameters
inthe input stream from which to read.
regina::NCompactSearcher::~NCompactSearcher ( )
inlinevirtual

Destroys this search manager and all supporting data structures.

Member Function Documentation

bool regina::NGluingPermSearcher::badEdgeLink ( const NTetFace face) const
protectedinherited

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

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

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

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

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

Parameters
facethe specific tetrahedron face upon which tests will be based.
Returns
true if the permutations under construction will lead to an edge identified with itself in reverse, or false if no such edge is found.
static NGluingPermSearcher* regina::NGluingPermSearcher::bestSearcher ( const NFacePairing pairing,
const NFacePairing::IsoList autos,
bool  orientableOnly,
bool  finiteOnly,
int  whichPurge,
UseGluingPerms  use,
void *  useArgs = 0 
)
staticinherited

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.

Precondition
The given face pairing is connected, i.e., it is possible to reach any tetrahedron from any other tetrahedron via a series of matched face pairs.
The given face pairing is in canonical form as described by NFacePairing::isCanonical(). Note that all face pairings constructed by NFacePairing::findAllPairings() are of this form.
Returns
the newly created search manager.
bool regina::NGluingPermSearcher::completePermSet ( ) const
inlineinherited

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.

Returns
true if a complete gluing permutation set is held, or false otherwise.
char regina::NCompactSearcher::dataTag ( ) const
inlineprotectedvirtual

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

Returns
the class tag.

Reimplemented from regina::NGluingPermSearcher.

Reimplemented in regina::NClosedPrimeMinSearcher.

virtual void regina::NCompactSearcher::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).

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.
Parameters
outthe output stream to which the data should be written.

Reimplemented from regina::NGluingPermSearcher.

Reimplemented in regina::NClosedPrimeMinSearcher.

void regina::NGluingPermSearcher::dumpTaggedData ( std::ostream &  out) const
inherited

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.

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.
Parameters
outthe output stream to which the data should be written.
static void regina::NGluingPermSearcher::findAllPerms ( const NFacePairing pairing,
const NFacePairing::IsoList autos,
bool  orientableOnly,
bool  finiteOnly,
int  whichPurge,
UseGluingPerms  use,
void *  useArgs = 0 
)
staticinherited

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.

Precondition
The given face pairing is connected, i.e., it is possible to reach any tetrahedron from any other tetrahedron via a series of matched face pairs.
The given face pairing is in canonical form as described by NFacePairing::isCanonical(). Note that all face pairings constructed by NFacePairing::findAllPairings() are of this form.
int regina::NCompactSearcher::findEdgeClass ( int  edgeID) const
inlineprotected

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

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

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

Parameters
edgeIDthe index of a single tetrahedron edge; this must be between 0 and 6t-1 inclusive, where t is the number of tetrahedra. See the TetEdgeState class notes for details on edge indexing.
Returns
the index of the tetrahedron edge at the root of the union-find tree, i.e., the representative of the equivalence class.
int regina::NCompactSearcher::findEdgeClass ( int  edgeID,
char &  twisted 
) const
inlineprotected

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

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

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

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

Parameters
edgeIDthe index of a single tetrahedron edge; this must be between 0 and 6t-1 inclusive, where t is the number of tetrahedra. See the TetEdgeState class notes for details on edge indexing.
twistedused to track edge orientation, as described above. This must be either 0 or 1 as it is passed into the function, and it will also be either 0 or 1 upon returning from the function.
Returns
the index of the tetrahedron edge at the root of the union-find tree, i.e., the representative of the equivalence class.
const NFacePairing * regina::NGluingPerms::getFacePairing ( ) const
inlineinherited

Returns the specific pairing of tetrahedron faces that this set of gluing permutations complements.

Deprecated:
This routine has been renamed to getFacetPairing(). This old name has been kept for backward compatibility, but will be removed in some future version of Regina.
Returns
the corresponding tetrahedron face pairing.
const FacetPairing* regina::NGenericGluingPerms< dim >::getFacetPairing ( ) const
inherited

Returns the specific pairing of simplex facets that this set of gluing permutations complements.

Returns
the corresponding simplex facet pairing.
unsigned regina::NGluingPerms::getNumberOfTetrahedra ( ) const
inlineinherited

Returns the total number of tetrahedra under consideration.

Deprecated:
This routine has been renamed to size(). This old name has been kept for backward compatibility, but will be removed in some future version of Regina.
Returns
the number of tetrahedra under consideration.
Perm regina::NGenericGluingPerms< dim >::gluingPerm ( const NFacetSpec< dim > &  source) const
inherited

Returns the gluing permutation associated with the given simplex facet.

Precondition
The given facet is actually paired with some other facet in the underlying pairwise matching (see routine getFacetPairing()).
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe simplex facet under investigation.
Returns
the associated gluing permutation.
Perm regina::NGenericGluingPerms< dim >::gluingPerm ( unsigned  simp,
unsigned  facet 
) const
inherited

Returns the gluing permutation associated with the given simplex facet.

Precondition
The given facet is actually paired with some other facet in the underlying pairwise matching (see routine getFacetPairing()).
Parameters
simpthe simplex under investigation (this must be strictly less than the total number of simplices under consideration).
facetthe facet of the given simplex under investigation (between 0 and dim inclusive).
Returns
the associated gluing permutation.
int regina::NGenericGluingPerms< dim >::gluingToIndex ( const NFacetSpec< dim > &  source,
const Perm &  gluing 
) const
protectedinherited

Returns the index into array Perm::Sn_1 corresponding to the given gluing permutation from the given facet to its partner.

This need not be the index into Perm::Sn_1 that is currently stored for the given facet.

Indices into array Perm::Sn_1 are stored internally in the array permIndices_. Full gluing permutations on the other hand are used in constructing triangulations.

Precondition
The given simplex facet has a partner according to the underlying facet pairing, i.e., is not a boundary facet.
If the given simplex facet and its partner are facets x and y of their respective simplices, then the given gluing permutation maps x to y.
Parameters
sourcethe simplex facet under investigation.
gluinga possible gluing permutation from the given simplex facet to its partner according to the underlying facet pairing.
Returns
the index into Perm::Sn_1 corresponding to the given gluing permutation; this will be between 0 and dim!-1 inclusive.
int regina::NGenericGluingPerms< dim >::gluingToIndex ( unsigned  simp,
unsigned  facet,
const Perm &  gluing 
) const
protectedinherited

Returns the index into array Perm::Sn_1 corresponding to the given gluing permutation from the given facet to its partner.

This need not be the index into Perm::Sn_1 that is currently stored for the given facet.

Indices into array Perm::Sn_1 are stored internally in the array permIndices_. Full gluing permutations on the other hand are used in constructing triangulations.

Precondition
The given simplex facet has a partner according to the underlying facet pairing, i.e., is not a boundary facet.
If the given simplex facet and its partner are facets x and y of their respective simplices, then the given gluing permutation maps x to y.
Parameters
simpthe simplex under investigation; this must be strictly less than the total number of simplices under consideration.
facetthe facet of the given simplex under investigation; this must be between 0 and dim inclusive.
gluinga possible gluing permutation from the given simplex facet to its partner according to the underlying facet pairing.
Returns
the index into Perm::Sn_1 corresponding to the given gluing permutation; this will be between 0 and dim!-1 inclusive.
Perm regina::NGenericGluingPerms< dim >::indexToGluing ( const NFacetSpec< dim > &  source,
int  index 
) const
protectedinherited

Returns the gluing permutation from the given facet to its partner that corresponds to the given index into array Perm::Sn_1.

This index into Perm::Sn_1 need not be the index that is currently stored for the given facet.

Indices into array Perm::Sn_1 are stored internally in the array permIndices_. Full gluing permutations on the other hand are used in constructing triangulations.

If the given simplex facet and its partner according to the underlying facet pairing are facets x and y of their respective simplices, then the resulting gluing permutation will map x to y.

Precondition
The given simplex facet has a partner according to the underlying facet pairing, i.e., is not a boundary facet.
Parameters
sourcethe simplex facet under investigation.
indexan index into Perm::Sn_1; this must be between 0 and dim!-1 inclusive.
Returns
the gluing permutation corresponding to the given index into Perm::Sn_1.
Perm regina::NGenericGluingPerms< dim >::indexToGluing ( unsigned  simp,
unsigned  facet,
int  index 
) const
protectedinherited

Returns the gluing permutation from the given facet to its partner that corresponds to the given index into array Perm::Sn_1.

This index into Perm::Sn_1 need not be the index that is currently stored for the given facet.

Indices into array Perm::Sn_1 are stored internally in the array permIndices_. Full gluing permutations on the other hand are used in constructing triangulations.

If the given simplex facet and its partner according to the underlying facet pairing are facets x and y of their respective simplices, then the resulting gluing permutation will map x to y.

Precondition
The given simplex facet has a partner according to the underlying facet pairing, i.e., is not a boundary facet.
Parameters
simpthe simplex under investigation; this must be strictly less than the total number of simplices under consideration.
facetthe facet of the given simplex under investigation; this must be between 0 and dim inclusive.
indexan index into Perm::Sn_1; this must be between 0 and dim!-1 inclusive.
Returns
the gluing permutation corresponding to the given index into Perm::Sn_1.
bool regina::NGenericGluingPerms< dim >::inputError ( ) const
inherited

Was an error found during construction from an input stream?

This routine returns true if an input stream constructor was used to create this object but the data in the input stream was invalid or incorrectly formatted.

If a different constructor was called (i.e., no input stream was used), then this routine will always return false.

Returns
true if an error occurred during construction from an input stream, or false otherwise.
bool regina::NGluingPermSearcher::isCanonical ( ) const
protectedinherited

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

Returns
true if the current set is in canonical form, or false otherwise.
bool regina::NGluingPermSearcher::lowDegreeEdge ( const NTetFace face,
bool  testDegree12,
bool  testDegree3 
) const
protectedinherited

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

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

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

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

Parameters
facethe specific tetrahedron face upon which tests will be based.
testDegree12true if we should test for non-boundary edges of degree 1 or 2.
testDegree3true if we should test for non-boundary edges of degree 3 involving three distinct tetrahedra.
Returns
true if the permutations under construction will lead to a low-degree edge as specified by parameters testDegree12 and testDegree3, or false if no such edge is found.
bool regina::NCompactSearcher::mergeEdgeClasses ( )
protected

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

See the TetEdgeState class for details.

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

Returns
true if this merge creates an invalid edge, or false if not.
int regina::NCompactSearcher::mergeVertexClasses ( )
protected

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

See the TetVertexState class for details.

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

Returns
a combination of VLINK_... flags describing how the vertex links were changed, or 0 if none of the changes described by these flags were observed.
int& regina::NGenericGluingPerms< dim >::permIndex ( const NFacetSpec< dim > &  source)
protectedinherited

Returns the index into array Perm::Sn_1 describing how the the given facet is joined to its partner.

Note that this permutation is not a gluing permutation as such, but rather a permutation of 0,...,dim-1 only. For a real facet gluing permutation, see routine gluingPerm().

Precondition
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe simplex facet under investigation.
Returns
a reference to the corresponding array index.
int& regina::NGenericGluingPerms< dim >::permIndex ( unsigned  simp,
unsigned  facet 
)
protectedinherited

Returns the index into array Perm::Sn_1 describing how the the given facet is joined to its partner.

Note that this permutation is not a gluing permutation as such, but rather a permutation of 0,...,dim-1 only. For a real facet gluing permutation, see routine gluingPerm().

Parameters
simpthe simplex under investigation (this must be strictly less than the total number of simplices under consideration).
facetthe facet of the given simplex under investigation (between 0 and dim inclusive).
Returns
a reference to the corresponding array index.
const int& regina::NGenericGluingPerms< dim >::permIndex ( const NFacetSpec< dim > &  source) const
protectedinherited

Returns the index into array Perm::Sn_1 describing how the the given facet is joined to its partner.

Note that this permutation is not a gluing permutation as such, but rather a permutation of 0,...,dim-1 only. For a real facet gluing permutation, see routine gluingPerm().

Precondition
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe simplex facet under investigation.
Returns
a reference to the corresponding array index.
const int& regina::NGenericGluingPerms< dim >::permIndex ( unsigned  simp,
unsigned  facet 
) const
protectedinherited

Returns the index into array Perm::Sn_1 describing how the the given facet is joined to its partner.

Note that this permutation is not a gluing permutation as such, but rather a permutation of 0,...,dim-1 only. For a real facet gluing permutation, see routine gluingPerm().

Parameters
simpthe simplex under investigation (this must be strictly less than the total number of simplices under consideration).
facetthe facet of the given simplex under investigation (between 0 and dim inclusive).
Returns
a reference to the corresponding array index.
static NGluingPermSearcher* regina::NGluingPermSearcher::readTaggedData ( std::istream &  in,
UseGluingPerms  use,
void *  useArgs = 0 
)
staticinherited

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 same as for the NGluingPermSearcher constructor.

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.
Parameters
inthe input stream from which to read.
virtual void regina::NCompactSearcher::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.

Todo:
Feature: Allow cancellation of permutation set generation.
Parameters
maxDepththe depth of the partial search to run, or a negative number if a full search should be run (the default).

Reimplemented from regina::NGluingPermSearcher.

Reimplemented in regina::NClosedPrimeMinSearcher.

unsigned regina::NGenericGluingPerms< dim >::size ( ) const
inherited

Returns the total number of simplices under consideration.

Returns
the number of simplices under consideration.
void regina::NCompactSearcher::splitEdgeClasses ( )
protected

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

See the TetEdgeState class for details.

void regina::NCompactSearcher::splitVertexClasses ( )
protected

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

See the TetVertexState class for details.

Triangulation* regina::NGenericGluingPerms< dim >::triangulate ( ) const
inherited

Returns a newly created triangulation as modelled by this set of gluing permutations and the associated simplex facet pairing.

Each matched pair of facets and their associated permutations will be realised as two simplex facets in the triangulation glued together with the corresponding gluing permutation. Each unmatched facet will be realised as a boundary facet in the triangulation.

It is the responsibility of the caller of this routine to delete this triangulation once it is no longer required.

Returns
a newly created triangulation modelled by this structure.
void regina::NCompactSearcher::vtxBdryBackup ( int  vertexID)
inlineprotected

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

See the TetVertexState class for further information.

Parameters
vertexIDthe tetrahedron vertex on which to operate; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
void regina::NCompactSearcher::vtxBdryConsistencyCheck ( )
protected

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

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

void regina::NCompactSearcher::vtxBdryDump ( std::ostream &  out)
protected

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

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

See the TetVertexState class for further information.

Parameters
outthe output stream to which to write.
void regina::NCompactSearcher::vtxBdryFixAdj ( int  vertexID)
inlineprotected

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

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

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

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

See the TetVertexState class for further information.

Precondition
The vertex linking triangle for the given tetrahedron vertex contributes at least one boundary edge to the vertex link.
Parameters
vertexIDthe tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
void regina::NCompactSearcher::vtxBdryJoin ( int  vertexID,
char  end,
int  adjVertexID,
char  twist 
)
inlineprotected

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

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

See the TetVertexState class for details.

Parameters
vertexIDthe first tetrahedron vertex on which to operate; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
endspecifies in which direction the adjacent boundary edges lie. This must be either 0 or 1, and its value should correspond to the relevant index in the bdryNext and bdryTwist arrays for vertex vertexID.
adjVertexIDthe tetrahedron vertex whose boundary edges are adjacent to the boundary edges supplied by vertexID; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
twist0 if the orientations of the two boundary segments of vertex link are oriented in the same direction, or 1 if they are oriented in opposite directions; see the bdryTwist documentation for details.
bool regina::NCompactSearcher::vtxBdryLength1 ( int  vertexID)
inlineprotected

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

See the TetVertexState class for further information.

Parameters
vertexIDthe tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
Returns
true if a one-edge boundary component is formed as described above, or false otherwise.
bool regina::NCompactSearcher::vtxBdryLength2 ( int  vertexID1,
int  vertexID2 
)
inlineprotected

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

See the TetVertexState class for further information.

Parameters
vertexID1the first tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
vertexID2the second tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
Returns
true if a two-edge boundary component is formed as described above, or false otherwise.
void regina::NCompactSearcher::vtxBdryNext ( int  vertexID,
int  tet,
int  vertex,
int  bdryFace,
int  next[2],
char  twist[2] 
)
inlineprotected

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

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

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

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

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

See the TetVertexState class for further information.

Precondition
The tetrahedron face (tet, bdryFace) is one of the two faces that are currently being joined together. That is, this face is either order[orderElt] or its partner in the underlying face pairing.
Parameters
vertexIDthe tetrahedron vertex to examine; this must be between 0 and 4n-1 inclusive, where n is the number of tetrahedra.
tetthe tetrahedron described by vertexID; this must be (vertexID / 4). It is passed separately to avoid a slow division operation.
vertexthe tetrahedron vertex number described by vertexID; this must be (vertexID % 4). It is passed separately to avoid a slow modulus operation.
bdryFacethe face number of the given tetrahedron containing the edge of the vertex linking triangle that is under consideration. This must be between 0 and 3 inclusive, and it may not be equal to vertex.
nextreturns the tetrahedron vertex supplying each adjacent boundary edge; see the TetVertexState::bdryNext notes for details on which directions correspond to array indices 0 and 1.
twistreturns whether the orientations of the adjacent boundary edges are consistent with the orientation of this boundary edge; see the TetVertexState::bdryTwist notes for further information on orientations in the vertex link.
void regina::NCompactSearcher::vtxBdryRestore ( int  vertexID)
inlineprotected

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

See the TetVertexState class for further information.

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

Member Data Documentation

const NFacePairing::IsoList* regina::NGluingPermSearcher::autos_
protectedinherited

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

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

bool regina::NGluingPermSearcher::autosNew
protectedinherited

Did we create the isomorphism list autos_ ourselves (in which case we must destroy it also)?

const char regina::NCompactSearcher::dataTag_
static

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

TetEdgeState* regina::NCompactSearcher::edgeState
protected

Used for tracking equivalence classes of identified tetrahedron edges.

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

int* regina::NCompactSearcher::edgeStateChanged
protected

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

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

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

bool regina::NGluingPermSearcher::finiteOnly_
protectedinherited

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

bool regina::NGenericGluingPerms< dim >::inputError_
protectedinherited

Has an error occurred during construction from an input stream?

unsigned regina::NCompactSearcher::nEdgeClasses
protected

The number of equivalence classes of identified tetrahedron edges.

unsigned regina::NCompactSearcher::nVertexClasses
protected

The number of equivalence classes of identified tetrahedron vertices.

NTetFace* regina::NGluingPermSearcher::order
protectedinherited

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

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

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

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

int regina::NGluingPermSearcher::orderElt
protectedinherited

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

int regina::NGluingPermSearcher::orderSize
protectedinherited

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

bool regina::NGluingPermSearcher::orientableOnly_
protectedinherited

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

int* regina::NGluingPermSearcher::orientation
protectedinherited

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

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

const FacetPairing* regina::NGenericGluingPerms< dim >::pairing_
protectedinherited

The facet pairing that this permutation set complements.

This is guaranteed to be the minimal representative of its facet pairing isomorphism class.

int* regina::NGenericGluingPerms< dim >::permIndices_
protectedinherited

The index into array Perm::Sn_1 describing how each simplex facet is glued to its partner.

Note that this is not a gluing permutation as such but rather a permutation of 0,...,dim-1 only (see the routines gluingToIndex() and indexToGluing() for conversions). If a permutation has not yet been selected (e.g., if this permutation set is still under construction) then this index is -1.

bool regina::NGluingPermSearcher::started
protectedinherited

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

UseGluingPerms regina::NGluingPermSearcher::use_
protectedinherited

A routine to call each time a gluing permutation set is found during the search.

void* regina::NGluingPermSearcher::useArgs_
protectedinherited

Additional user-supplied data to be passed as the second argument to the use_ routine.

const int regina::NCompactSearcher::vertexLinkNextFace[4][4]
staticprotected

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

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

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

const int regina::NCompactSearcher::vertexLinkPrevFace[4][4]
staticprotected

Provides backwards links for the ordering described by vertexLinkNextFace.

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

TetVertexState* regina::NCompactSearcher::vertexState
protected

Used for tracking equivalence classes of identified tetrahedron vertices.

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

int* regina::NCompactSearcher::vertexStateChanged
protected

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

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

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

const char regina::NCompactSearcher::VLINK_CLOSED
staticprotected

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

const char regina::NCompactSearcher::VLINK_NON_SPHERE
staticprotected

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

int regina::NGluingPermSearcher::whichPurge_
protectedinherited

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

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


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

Copyright © 1999-2014, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).