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

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

#include <census/dim2gluingpermsearcher.h>

Inheritance diagram for regina::Dim2GluingPermSearcher:
regina::Dim2GluingPerms regina::NGenericGluingPerms< 2 >

Public Member Functions

 Dim2GluingPermSearcher (const Dim2EdgePairing *pairing, const Dim2EdgePairing::IsoList *autos, bool orientableOnly, UseDim2GluingPerms use, void *useArgs=0)
 Initialises a new search for gluing permutation sets. More...
 
 Dim2GluingPermSearcher (std::istream &in, UseDim2GluingPerms use, void *useArgs=0)
 Initialises a new search manager based on data read from the given input stream. More...
 
virtual ~Dim2GluingPermSearcher ()
 Destroys this search manager and all supporting data structures. 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...
 
virtual void dumpData (std::ostream &out) const
 Dumps all internal data in a plain text format to the given output stream. More...
 
- Public Member Functions inherited from regina::Dim2GluingPerms
 Dim2GluingPerms (const Dim2GluingPerms &cloneMe)
 Creates a new set of gluing permutations that is a clone of the given permutation set. More...
 
 Dim2GluingPerms (std::istream &in)
 Reads a new set of gluing permutations from the given input stream. More...
 
- Public Member Functions inherited from regina::NGenericGluingPerms< 2 >
 NGenericGluingPerms (const NGenericGluingPerms< dim > &cloneMe)
 Creates a new set of gluing permutations that is a clone of the given permutation set. More...
 
 NGenericGluingPerms (std::istream &in)
 Reads a new set of gluing permutations from the given input stream. More...
 
virtual ~NGenericGluingPerms ()
 Deallocates any memory used by this structure. 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 Dim2EdgePairing *pairing, const Dim2EdgePairing::IsoList *autos, bool orientableOnly, UseDim2GluingPerms use, void *useArgs=0)
 The main entry routine for running a search for all gluing permutation sets that complement a given edge pairing. More...
 
static Dim2GluingPermSearcherbestSearcher (const Dim2EdgePairing *pairing, const Dim2EdgePairing::IsoList *autos, bool orientableOnly, UseDim2GluingPerms use, void *useArgs=0)
 Constructs a search manager of the best possible class for the given search parameters. More...
 
static Dim2GluingPermSearcherreadTaggedData (std::istream &in, UseDim2GluingPerms 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

bool isCanonical () const
 Compares the current set of gluing permutations with its preimage under each automorphism of the underlying edge pairing, in order to see whether the current set is in canonical form (i.e., is lexicographically smallest). More...
 
virtual char dataTag () const
 Returns the character used to identify this class when storing tagged data in text format. More...
 
- Protected Member Functions inherited from regina::Dim2GluingPerms
 Dim2GluingPerms (const Dim2EdgePairing *pairing)
 Creates a new permutation set. More...
 
- Protected Member Functions inherited from regina::NGenericGluingPerms< 2 >
 NGenericGluingPerms (const FacetPairing *pairing)
 Creates a new permutation set. 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

const Dim2EdgePairing::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...
 
UseDim2GluingPerms 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 triangle in the underlying triangulation. More...
 
Dim2TriangleEdgeorder
 Describes the order in which gluing permutations are assigned to edges. More...
 
int orderSize
 The total number of edges in the edge pairing graph, i.e., the number of elements of interest in the order[] array. More...
 
int orderElt
 Marks which element of order[] we are currently examining at this stage of the search. More...
 

Additional Inherited Members

- Public Types inherited from regina::NGenericGluingPerms< 2 >
typedef DimTraits< dim >
::FacetPairing 
FacetPairing
 
typedef DimTraits< dim >::Perm Perm
 
typedef DimTraits< dim >::Simplex Simplex
 
typedef DimTraits< dim >
::Triangulation 
Triangulation
 

Detailed Description

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

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

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

Note that this class derives from Dim2GluingPerms. The search will involve building and repeatedly modifying the inherited Dim2GluingPerms data in-place.

Python:
Not present.

Constructor & Destructor Documentation

regina::Dim2GluingPermSearcher::Dim2GluingPermSearcher ( const Dim2EdgePairing pairing,
const Dim2EdgePairing::IsoList autos,
bool  orientableOnly,
UseDim2GluingPerms  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.

Precondition
The given edge pairing is connected, i.e., it is possible to reach any triangle from any other triangle via a series of matched edge pairs.
The given edge pairing is in canonical form as described by Dim2EdgePairing::isCanonical(). Note that all edge pairings constructed by Dim2EdgePairing::findAllPairings() are of this form.
Parameters
pairingthe specific pairing of triangle edges that the generated permutation sets will complement.
autosthe collection of isomorphisms that define equivalence of permutation sets. These are used by runSearch(), which produces each permutation set precisely once up to equivalence. These isomorphisms must all be automorphisms of the given edge pairing, and will generally be the set of all such automorphisms. This parameter may be 0, in which case the set of all automorphisms of the given edge pairing will be generated and used.
orientableOnlytrue if only gluing permutations corresponding to orientable triangulations should be generated, or false if no such restriction should be imposed.
usethe 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.
useArgsthe pointer to pass as the final parameter for the function use which will be called upon each permutation set found.
regina::Dim2GluingPermSearcher::Dim2GluingPermSearcher ( std::istream &  in,
UseDim2GluingPerms  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.

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.
useas for the main Dim2GluingPermSearcher constructor.
useArgsas for the main Dim2GluingPermSearcher constructor.
virtual regina::Dim2GluingPermSearcher::~Dim2GluingPermSearcher ( )
virtual

Destroys this search manager and all supporting data structures.

Member Function Documentation

static Dim2GluingPermSearcher* regina::Dim2GluingPermSearcher::bestSearcher ( const Dim2EdgePairing pairing,
const Dim2EdgePairing::IsoList autos,
bool  orientableOnly,
UseDim2GluingPerms  use,
void *  useArgs = 0 
)
static

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

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

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

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::Dim2GluingPermSearcher::dataTag ( ) const
inlineprotectedvirtual

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

Returns
the class tag.
virtual void regina::Dim2GluingPermSearcher::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::NGenericGluingPerms< 2 >.

void regina::Dim2GluingPermSearcher::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.

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::Dim2GluingPermSearcher::findAllPerms ( const Dim2EdgePairing pairing,
const Dim2EdgePairing::IsoList autos,
bool  orientableOnly,
UseDim2GluingPerms  use,
void *  useArgs = 0 
)
static

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

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

See the Dim2GluingPermSearcher 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 edge pairing is connected, i.e., it is possible to reach any triangle from any other triangle via a series of matched edge pairs.
The given edge pairing is in canonical form as described by Dim2EdgePairing::isCanonical(). Note that all edge pairings constructed by Dim2EdgePairing::findAllPairings() are of this form.
bool regina::Dim2GluingPermSearcher::isCanonical ( ) const
protected

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

Returns
true if the current set is in canonical form, or false otherwise.
static Dim2GluingPermSearcher* regina::Dim2GluingPermSearcher::readTaggedData ( std::istream &  in,
UseDim2GluingPerms  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 same as for the Dim2GluingPermSearcher 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::Dim2GluingPermSearcher::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 edge 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 Dim2GluingPermSearcher 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).

Member Data Documentation

const Dim2EdgePairing::IsoList* regina::Dim2GluingPermSearcher::autos_
protected

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

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

bool regina::Dim2GluingPermSearcher::autosNew
protected

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

const char regina::Dim2GluingPermSearcher::dataTag_
static

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

Dim2TriangleEdge* regina::Dim2GluingPermSearcher::order
protected

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

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

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

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

int regina::Dim2GluingPermSearcher::orderElt
protected

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

int regina::Dim2GluingPermSearcher::orderSize
protected

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

bool regina::Dim2GluingPermSearcher::orientableOnly_
protected

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

int* regina::Dim2GluingPermSearcher::orientation
protected

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

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

bool regina::Dim2GluingPermSearcher::started
protected

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

UseDim2GluingPerms regina::Dim2GluingPermSearcher::use_
protected

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

void* regina::Dim2GluingPermSearcher::useArgs_
protected

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


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

Copyright © 1999-2013, 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).