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

A utility class used to search for triangulations across one or more 3-manifold census databases. More...

#include <census/ncensus.h>

Public Types

typedef bool(* AcceptTriangulation )(NTriangulation *, void *)
 A routine used to determine whether a particular triangulation should be included in a census. More...
 

Static Public Member Functions

static NCensusHitslookup (const NTriangulation &tri)
 Searches for the given triangulation through all of Regina's in-built census databases. More...
 
static NCensusHitslookup (const std::string &isoSig)
 Searches for the given triangulation through all of Regina's in-built census databases. More...
 
static unsigned long formCensus (NPacket *parent, unsigned nTetrahedra, NBoolSet finiteness, NBoolSet orientability, NBoolSet boundary, int nBdryTris, int whichPurge, AcceptTriangulation sieve=0, void *sieveArgs=0)
 Deprecated routine that fills the given packet with all triangulations in a census of 3-manifold triangulations satisfying the given constraints. More...
 
static unsigned long formPartialCensus (const NFacePairing *pairing, NPacket *parent, NBoolSet finiteness, NBoolSet orientability, int whichPurge, AcceptTriangulation sieve=0, void *sieveArgs=0)
 Deprecated routine that fills the given packet with all triangulations in a partial census of 3-manifold triangulations satisfying the given constraints. More...
 
static bool mightBeMinimal (NTriangulation *tri, void *ignore=0)
 Deprecated routine to determine whether the given triangulation even has a chance at being minimal. More...
 

Static Public Attributes

static const int PURGE_NON_MINIMAL
 This constant indicates that non-minimal triangulations may be ignored. More...
 
static const int PURGE_NON_PRIME
 This constant 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. More...
 
static const int PURGE_NON_MINIMAL_PRIME
 This constant 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. More...
 
static const int PURGE_P2_REDUCIBLE
 This constant indicates that any triangulation containing an embedded two-sided projective plane may be ignored. More...
 

Detailed Description

A utility class used to search for triangulations across one or more 3-manifold census databases.

Member Typedef Documentation

typedef bool(* regina::NCensus::AcceptTriangulation)(NTriangulation *, void *)

A routine used to determine whether a particular triangulation should be included in a census.

Routines of this type are used by NCensus::formCensus().

The first parameter passed should be a triangulation currently under consideration. The second parameter may contain arbitrary data as passed to NCensus::formCensus().

The return value should be true if the triangulation passed should be included in the census, or false otherwise.

Deprecated:
The NCensus enumeration facilities are on their way out of Regina, and in the future the NCensus class will be used purely for census lookups. If you wish to build a census yourself, you should call NFacePairing::findAllPairings() and NGluingPermSearcher::findAllPerms() directly.

Member Function Documentation

static unsigned long regina::NCensus::formCensus ( NPacket parent,
unsigned  nTetrahedra,
NBoolSet  finiteness,
NBoolSet  orientability,
NBoolSet  boundary,
int  nBdryTris,
int  whichPurge,
AcceptTriangulation  sieve = 0,
void *  sieveArgs = 0 
)
static

Deprecated routine that fills the given packet with all triangulations in a census of 3-manifold triangulations satisfying the given constraints.

Each triangulation in the census will appear as a child of the given packet.

This routine will conduct a census of all valid triangulations containing a given number of tetrahedra. All such triangulations are included in the census up to combinatorial isomorphism; given any isomorphism class, exactly one representative will appear in the census.

The census can be optionally restricted to only include triangulations satisfying further constraints (such as orientability and finiteness); see the individual parameter descriptions for further details. In particular, parameter sieve can be used to impose arbitrary restrictions that are not hard-coded into this class.

Note that if constraints may be imposed using the hard-coded parameters (such as orientability and finiteness), it is generally better to do this than to use the arbitrary constraint parameter sieve. Hard-coded parameters will be tested earlier, and some (such as orientability) can be incorporated directly into the census algorithm to give a vast performance increase.

Parameter whichPurge may be used to further avoid constructing triangulations satisfying particular constraints (such as non-minimality). This can significantly speed up the census. In this case however not all such triangulations will be avoided, but it is guaranteed that every triangulation that does not satisfy the constraints defined by whichPurge will be produced.

Only valid triangulations will be produced; see NTriangulation::isValid() for further details.

Note that this routine should only be used if the census contains a small enough total number of triangulations to avoid any memory disasters.

Deprecated:
The NCensus enumeration facilities are on their way out of Regina, and in the future the NCensus class will be used purely for census lookups. To perform the kind of enumeration that is described here, you should call NFacePairing::findAllPairings() and NGluingPermSearcher::findAllPerms() directly.
Python:
Parameters sieve and sieveArgs are not present (and will be treated as 0).
Parameters
parentthe packet beneath which members of the census will be placed.
nTetrahedrathe number of tetrahedra in each triangulation in the census.
finitenessdetermines whether to include finite and/or ideal triangulations. The set should contain true if finite (non-ideal) triangulations are to be included, and should contain false if ideal triangulations are to be included.
orientabilitydetermines whether to include orientable and/or non-orientable triangulations. The set should contain true if orientable triangulations are to be included, and should contain false if non-orientable triangulations are to be included.
boundarydetermines whether to include triangulations with and/or without boundary triangles. The set should contain true if triangulations with boundary triangles are to be included, and should contain false if triangulations with only internal triangles are to be included.
nBdryTrisspecifies the precise number of boundary triangles that should be present in the triangulations produced. If this parameter is negative, it is ignored and no additional restriction is imposed. See the documentation for routine NFacePairing::findAllPairings() for details regarding this parameter and how it interacts with parameter boundary.
whichPurgespecifies which triangulations we may further avoid constructing (see the function notes above for details). This should be a bitwise OR of purge constants defined in this class, or 0 if no additional pruning should take place. If a variety of purge constants are bitwise ORed together, a triangulation satisfying any of these constraints may be avoided. Note that not all such triangulations will be avoided, but enough are avoided that the performance increase is noticeable.
sievean additional constraint function that may be used to exclude certain triangulations from the census. If this parameter is non-zero, each triangulation produced (after passing all other criteria) will be passed through this function. If this function returns true then the triangulation will be included in the census; otherwise it will not. When this function is called, the first (triangulation) argument will be a triangulation under consideration for inclusion in the census. The second argument will be parameter sieveArgs as passed to formCensus(). Parameter sieve may be passed as null (in which case no additional constraint function will be used).
sieveArgsthe pointer to pass as the final parameter for the function sieve which will be called upon each triangulation found. If sieve is null then sieveArgs will be ignored.
Returns
the number of triangulations produced in the census.
static unsigned long regina::NCensus::formPartialCensus ( const NFacePairing pairing,
NPacket parent,
NBoolSet  finiteness,
NBoolSet  orientability,
int  whichPurge,
AcceptTriangulation  sieve = 0,
void *  sieveArgs = 0 
)
static

Deprecated routine that fills the given packet with all triangulations in a partial census of 3-manifold triangulations satisfying the given constraints.

Each triangulation in the partial census will appear as a child of the given packet.

This routine will conduct a census of all valid triangulations that are modelled by the given tetrahedron face pairing. All such triangulations are included in the census up to combinatorial isomorphism; given any isomorphism class, exactly one representative will appear in the census.

The census can be optionally restricted to only include triangulations satisfying further constraints (such as orientability and finiteness); see the individual parameter descriptions for further details. In particular, parameter sieve can be used to impose arbitrary restrictions that are not hard-coded into this class.

Note that if constraints may be imposed using the hard-coded parameters (such as orientability and finiteness), it is generally better to do this than to use the arbitrary constraint parameter sieve. Hard-coded parameters will be tested earlier, and some (such as orientability) can be incorporated directly into the census algorithm to give a vast performance increase.

Parameter whichPurge may be used to further avoid constructing triangulations satisfying particular constraints (such as non-minimality). The use of this parameter, combined with parameters finiteness and orientability, can significantly speed up the census. For some combinations of these parameters entirely different algorithms are used.

Note however that not all triangulations described by parameter whichPurge will be avoided. It is guaranteed however that every triangulation that does not satisfy the constraints defined by whichPurge will be produced.

Only valid triangulations will be produced; see NTriangulation::isValid() for further details.

Note that this routine should only be used if the partial census contains a small enough total number of triangulations to avoid any memory disasters.

The partial census will run in the current thread. This routine will only return once the partial census is complete.

Deprecated:
The NCensus enumeration facilities are on their way out of Regina, and in the future the NCensus class will be used purely for census lookups. To perform the kind of enumeration that is described here, you should call NGluingPermSearcher::findAllPerms() directly.
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.
Python:
Parameters sieve and sieveArgs are not present (and will be treated as 0).
Parameters
pairingthe tetrahedron face pairing that triangulations in this partial census must be modelled by.
parentthe packet beneath which members of the partial census will be placed.
finitenessdetermines whether to include finite and/or ideal triangulations. The set should contain true if finite (non-ideal) triangulations are to be included, and should contain false if ideal triangulations are to be included.
orientabilitydetermines whether to include orientable and/or non-orientable triangulations. The set should contain true if orientable triangulations are to be included, and should contain false if non-orientable triangulations are to be included.
whichPurgespecifies which triangulations we may further avoid constructing (see the function notes above for details). This should be a bitwise OR of purge constants defined in this class, or 0 if no additional pruning should take place. If a variety of purge constants are bitwise ORed together, a triangulation satisfying any of these constraints may be avoided. Note that not all such triangulations will be avoided, but enough are avoided that the performance increase is noticeable.
sievean additional constraint function that may be used to exclude certain triangulations from the census. If this parameter is non-zero, each triangulation produced (after passing all other criteria) will be passed through this function. If this function returns true then the triangulation will be included in the census; otherwise it will not. When this function is called, the first (triangulation) argument will be a triangulation under consideration for inclusion in the census. The second argument will be parameter sieveArgs as passed to formPartialCensus(). Parameter sieve may be passed as null (in which case no additional constraint function will be used).
sieveArgsthe pointer to pass as the final parameter for the function sieve which will be called upon each triangulation found. If sieve is null then sieveArgs will be ignored.
Returns
the number of triangulations produced in the partial census.
static NCensusHits* regina::NCensus::lookup ( const NTriangulation tri)
static

Searches for the given triangulation through all of Regina's in-built census databases.

Internally, the census databases store isomorphism signatures as opposed to fully fleshed-out triangulations. If you already have the isomorphism signature of the triangulation, then you can call the variant lookup(const std::string&) instead, which will be faster since it avoids some extra overhead.

Note that there may be many hits (possibly from multiple databases, and in some cases possibly even within the same database). The list of hits will be returned as an NCensusHits object, which you can use to iterate through the individual matches. Even if there are no matches at all, an NCensusHits object will still be returned; you can call NCensusHits::empty() to test whether any matches were found.

The NCensusHits object that is returned will be newly allocated, and it is the caller's responsibility to destroy it.

This routine is fast: it first computes the isomorphism signature of the triangulation, and then performs a logarithmic-time lookup in each database (here "logarithmic" means logarithmic in the size of the database).

Parameters
trithe triangulation that you wish to search for.
Returns
a newly created list of all database matches.
static NCensusHits* regina::NCensus::lookup ( const std::string &  isoSig)
static

Searches for the given triangulation through all of Regina's in-built census databases.

For this routine you specify the triangulation by giving its isomorphism signature, as returned by NTriangulation::isoSig(). This is faster than the variant lookup(const NTriangulation&), since Regina's census databases store isomorphism signatures internally. If you do not already know the isomorphism signature, it is fine to just call lookup(const NTriangulation&) instead.

Note that there may be many hits (possibly from multiple databases, and in some cases possibly even within the same database). The list of hits will be returned as an NCensusHits object, which you can use to iterate through the individual matches. Even if there are no matches at all, an NCensusHits object will still be returned; you can call NCensusHits::empty() to test whether any matches were found.

The NCensusHits object that is returned will be newly allocated, and it is the caller's responsibility to destroy it.

This routine is fast: it first computes the isomorphism signature of the triangulation, and then performs a logarithmic-time lookup in each database (here "logarithmic" means logarithmic in the size of the database).

Parameters
isoSigthe isomorphism signature of the triangulation that you wish to search for.
Returns
a newly created list of all database matches.
static bool regina::NCensus::mightBeMinimal ( NTriangulation tri,
void *  ignore = 0 
)
static

Deprecated routine to determine whether the given triangulation even has a chance at being minimal.

This routine can be passed as parameter sieve to routine NCensus::formCensus() to exclude obviously non-minimal triangulations from a census.

A variety of tests will be performed; these tests are subject to change between Regina releases. Currently this routine counts vertices and also tries to simplify the triangulation using NTriangulation::simplifyToLocalMinimum().

Currently this routine is only useful for triangulations whose triangles are all internal; if the given triangulation has boundary triangles then this routine will simply return true.

Deprecated:
The NCensus enumeration facilities are on their way out of Regina, and so this routine is no longer necessary. For a fast test as to whether a triangulation might be minimal, you should simply call NTriangulation::simplifyToLocalMinimum(false).
Python:
Parameter ignore is not present.
Parameters
trithe triangulation to examine.
ignorea parameter that is ignored.
Returns
false if the given triangulation is known to be non-minimal, or true if minimality of the given triangulation has not been determined.

Member Data Documentation

const int regina::NCensus::PURGE_NON_MINIMAL
static

This constant indicates that non-minimal triangulations may be ignored.

Deprecated:
This constant is deprecated; please use NGluingPermSearcher::PURGE_NON_MINIMAL instead.
const int regina::NCensus::PURGE_NON_MINIMAL_PRIME
static

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

Deprecated:
This constant is deprecated; please use NGluingPermSearcher::PURGE_NON_MINIMAL_PRIME instead.
const int regina::NCensus::PURGE_NON_PRIME
static

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

Deprecated:
This constant is deprecated; please use NGluingPermSearcher::PURGE_NON_PRIME instead.
const int regina::NCensus::PURGE_P2_REDUCIBLE
static

This constant indicates that any triangulation containing an embedded two-sided projective plane may be ignored.

Deprecated:
This constant is deprecated; please use NGluingPermSearcher::PURGE_NON_MINIMAL instead.

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