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::CompactSearcher 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/gluingpermsearcher3.h>

Inheritance diagram for regina::CompactSearcher:
regina::GluingPermSearcher< 3 > regina::GluingPerms< 3 > regina::ClosedPrimeMinSearcher

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 void(* Use) (const GluingPermSearcher< 3 > *, void *)
 A routine that can do arbitrary processing upon a set of gluing permutations. More...
 

Public Member Functions

 CompactSearcher (const FacetPairing< 3 > *pairing, const FacetPairing< 3 >::IsoList *autos, bool orientableOnly, int whichPurge, GluingPermSearcher< 3 >::Use use, void *useArgs=0)
 Creates a new search manager for use when only compact 3-manifold triangulations are required. More...
 
 CompactSearcher (std::istream &in, GluingPermSearcher< 3 >::Use use, void *useArgs=0)
 Initialises a new search manager based on data read from the given input stream. More...
 
virtual ~CompactSearcher ()
 Destroys this search manager and all supporting data structures. More...
 
virtual void dumpData (std::ostream &out) const override
 Dumps all internal data in a plain text format to the given output stream. More...
 
virtual void runSearch (long maxDepth=-1) override
 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...
 
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< dim > * facetPairing () const
 Returns the specific pairing of simplex facets that this set of gluing permutations complements. More...
 
Perm< dim+1 > gluingPerm (const FacetSpec< dim > &source) const
 Returns the gluing permutation associated with the given simplex facet. More...
 
Perm< dim+1 > gluingPerm (unsigned simp, unsigned facet) const
 Returns the gluing permutation associated with the given simplex facet. More...
 
Triangulation< dim > * 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 FacetPairing< 3 > *pairing, const FacetPairing< 3 >::IsoList *autos, bool orientableOnly, bool finiteOnly, int whichPurge, GluingPermSearcher< 3 >::Use 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 GluingPermSearcher< 3 > * bestSearcher (const FacetPairing< 3 > *pairing, const FacetPairing< 3 >::IsoList *autos, bool orientableOnly, bool finiteOnly, int whichPurge, GluingPermSearcher< 3 >::Use use, void *useArgs=0)
 Constructs a search manager of the best possible class for the given search parameters. More...
 
static GluingPermSearcher< 3 > * readTaggedData (std::istream &in, GluingPermSearcher< 3 >::Use 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 override
 Returns the character used to identify this class when storing tagged data in text format. More...
 
int findEdgeClass (int edgeID) const
 Returns the representative of the equivalence class containing the given tetrahedron edge. More...
 
int findEdgeClass (int edgeID, char &twisted) const
 Returns the representative of the equivalence class containing the given tetrahedron edge. More...
 
int mergeVertexClasses ()
 Merge the classes of tetrahedron vertices as required by the new gluing made at stage orderElt of the search. More...
 
bool mergeEdgeClasses ()
 Merge the classes of tetrahedron edges as required by the new gluing made at stage orderElt of the search. More...
 
void splitVertexClasses ()
 Split the classes of tetrahedron vertices to mirror the undoing of the gluing at stage orderElt of the search. More...
 
void splitEdgeClasses ()
 Split the classes of tetrahedron edges to mirror the undoing of the gluing at stage orderElt of the search. More...
 
void vtxBdryJoin (int vertexID, char end, int adjVertexID, char twist)
 Signifies that the boundary edges supplied by the vertex linking triangles for the two given tetrahedron vertices should be marked as adjacent. More...
 
void vtxBdryFixAdj (int vertexID)
 Adjusts the bdryNext and bdryTwist arrays for nearby tetrahedron vertices, to ensure that these arrays are consistent with the bdryNext and bdryTwist arrays stored with the given vertex. More...
 
void vtxBdryBackup (int vertexID)
 Copies the bdryNext and bdryTwist arrays to the bdryNextOld and bdryTwistOld arrays for the given tetrahedron vertex. More...
 
void vtxBdryRestore (int vertexID)
 Copies the bdryNextOld and bdryTwistOld arrays to the bdryNext and bdryTwist arrays for the given tetrahedron vertex. More...
 
void vtxBdryNext (int vertexID, int tet, int vertex, int bdryFace, int next[2], char twist[2])
 Assuming the given edge of the vertex linking triangle for the given tetrahedron vertex lies on the boundary of the vertex link, this routine identifies the adjacent boundary edges of the vertex link in each direction. More...
 
bool vtxBdryLength1 (int vertexID)
 Determines whether one of the edges of the vertex linking triangle for the given tetrahedron vertex in fact forms an entire one-edge boundary component of the overall vertex link. More...
 
bool vtxBdryLength2 (int vertexID1, int vertexID2)
 Determines whether edges of the vertex linking triangles for each of the given tetrahedron vertices combine to form an entire two-edge boundary component of the overall vertex link, with one edge from each triangle. More...
 
void vtxBdryConsistencyCheck ()
 Runs a number of tests on all tetrahedron vertices to locate consistency errors in the bdryEdges, bdryNext and bdryTwist members of the TetVertexState class. More...
 
void vtxBdryDump (std::ostream &out)
 Dumps a summary of bdryNext, bdryTwist and bdryEdges for every vertex of every tetrahedron to the given output stream. More...
 
bool isCanonical () const
 Compares the current set of gluing permutations with its preimage under each automorphism of the underlying face pairing, in order to see whether the current set is in canonical form (i.e., is lexicographically smallest). More...
 
bool badEdgeLink (const FacetSpec< 3 > &face) const
 Determines whether the permutations already constructed model a triangulation with an edge identified with itself in reverse. More...
 
bool lowDegreeEdge (const FacetSpec< 3 > &face, bool testDegree12, bool testDegree3) const
 Determines whether the permutations already constructed model a triangulation with a low degree edge. More...
 
int & permIndex (const FacetSpec< dim > &source)
 Returns the index into array Perm<dim+1>::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<dim+1>::Sn_1 describing how the the given facet is joined to its partner. More...
 
const int & permIndex (const FacetSpec< dim > &source) const
 Returns the index into array Perm<dim+1>::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<dim+1>::Sn_1 describing how the the given facet is joined to its partner. More...
 
int gluingToIndex (const FacetSpec< dim > &source, const Perm< dim+1 > &gluing) const
 Returns the index into array Perm<dim+1>::Sn_1 corresponding to the given gluing permutation from the given facet to its partner. More...
 
int gluingToIndex (unsigned simp, unsigned facet, const Perm< dim+1 > &gluing) const
 Returns the index into array Perm<dim+1>::Sn_1 corresponding to the given gluing permutation from the given facet to its partner. More...
 
Perm< dim+1 > indexToGluing (const FacetSpec< 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<dim+1>::Sn_1. More...
 
Perm< dim+1 > 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<dim+1>::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 FacetPairing< 3 >::IsoList * autos_
 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...
 
GluingPermSearcher< 3 >::Use 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...
 
FacetSpec< 3 > * order
 Describes the order in which gluing permutations are assigned to faces. More...
 
int orderSize
 The total number of edges in the face pairing graph, i.e., the number of elements of interest in the order[] array. More...
 
int orderElt
 Marks which element of order[] we are currently examining at this stage of the search. More...
 
const FacetPairing< dim > * pairing_
 The facet pairing that this permutation set complements. More...
 
int * permIndices_
 The index into array Perm<dim+1>::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 ClosedPrimeMinSearcher). That is, only compact 3-manifolds will be produced.

Python:\n Not present.

Member Function Documentation

◆ facetPairing()

const FacetPairing< dim > * regina::GluingPerms< dim >::facetPairing
inlineinherited

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

Returns
the corresponding simplex facet pairing.

◆ gluingPerm() [1/2]

Perm< dim+1 > regina::GluingPerms< dim >::gluingPerm ( const FacetSpec< dim > &  source) const
inlineinherited

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

◆ gluingPerm() [2/2]

Perm< dim+1 > regina::GluingPerms< dim >::gluingPerm ( unsigned  simp,
unsigned  facet 
) const
inlineinherited

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

◆ gluingToIndex() [1/2]

int regina::GluingPerms< dim >::gluingToIndex ( const FacetSpec< dim > &  source,
const Perm< dim+1 > &  gluing 
) const
protectedinherited

Returns the index into array Perm<dim+1>::Sn_1 corresponding to the given gluing permutation from the given facet to its partner.

This need not be the index into Perm<dim+1>::Sn_1 that is currently stored for the given facet.

Indices into array Perm<dim+1>::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<dim+1>::Sn_1 corresponding to the given gluing permutation; this will be between 0 and dim!-1 inclusive.

◆ gluingToIndex() [2/2]

int regina::GluingPerms< dim >::gluingToIndex ( unsigned  simp,
unsigned  facet,
const Perm< dim+1 > &  gluing 
) const
protectedinherited

Returns the index into array Perm<dim+1>::Sn_1 corresponding to the given gluing permutation from the given facet to its partner.

This need not be the index into Perm<dim+1>::Sn_1 that is currently stored for the given facet.

Indices into array Perm<dim+1>::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<dim+1>::Sn_1 corresponding to the given gluing permutation; this will be between 0 and dim!-1 inclusive.

◆ indexToGluing() [1/2]

Perm< dim+1 > regina::GluingPerms< dim >::indexToGluing ( const FacetSpec< dim > &  source,
int  index 
) const
inlineprotectedinherited

Returns the gluing permutation from the given facet to its partner that corresponds to the given index into array Perm<dim+1>::Sn_1.

This index into Perm<dim+1>::Sn_1 need not be the index that is currently stored for the given facet.

Indices into array Perm<dim+1>::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<dim+1>::Sn_1; this must be between 0 and dim!-1 inclusive.
Returns
the gluing permutation corresponding to the given index into Perm<dim+1>::Sn_1.

◆ indexToGluing() [2/2]

Perm< dim+1 > regina::GluingPerms< dim >::indexToGluing ( unsigned  simp,
unsigned  facet,
int  index 
) const
inlineprotectedinherited

Returns the gluing permutation from the given facet to its partner that corresponds to the given index into array Perm<dim+1>::Sn_1.

This index into Perm<dim+1>::Sn_1 need not be the index that is currently stored for the given facet.

Indices into array Perm<dim+1>::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<dim+1>::Sn_1; this must be between 0 and dim!-1 inclusive.
Returns
the gluing permutation corresponding to the given index into Perm<dim+1>::Sn_1.

◆ inputError()

bool regina::GluingPerms< dim >::inputError
inlineinherited

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.

◆ permIndex() [1/4]

int & regina::GluingPerms< dim >::permIndex ( const FacetSpec< dim > &  source)
inlineprotectedinherited

Returns the index into array Perm<dim+1>::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.

◆ permIndex() [2/4]

const int & regina::GluingPerms< dim >::permIndex ( const FacetSpec< dim > &  source) const
inlineprotectedinherited

Returns the index into array Perm<dim+1>::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.

◆ permIndex() [3/4]

int & regina::GluingPerms< dim >::permIndex ( unsigned  simp,
unsigned  facet 
)
inlineprotectedinherited

Returns the index into array Perm<dim+1>::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.

◆ permIndex() [4/4]

const int & regina::GluingPerms< dim >::permIndex ( unsigned  simp,
unsigned  facet 
) const
inlineprotectedinherited

Returns the index into array Perm<dim+1>::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.

◆ size()

unsigned regina::GluingPerms< dim >::size
inlineinherited

Returns the total number of simplices under consideration.

Returns
the number of simplices under consideration.

◆ triangulate()

Triangulation<dim>* regina::GluingPerms< 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.

Member Data Documentation

◆ inputError_

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

Has an error occurred during construction from an input stream?

◆ pairing_

const FacetPairing<dim>* regina::GluingPerms< 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.

◆ permIndices_

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

The index into array Perm<dim+1>::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.


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

Copyright © 1999-2020, 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@maths.uq.edu.au).