Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

regina::NFacePairing Class Reference
[Census of Triangulations]

Represents a specific pairwise matching of tetrahedron faces. More...

#include <nfacepairing.h>

Inheritance diagram for regina::NFacePairing:

regina::NThread List of all members.

Public Member Functions

 NFacePairing (const NFacePairing &cloneMe)
 Creates a new face pairing that is a clone of the given face pairing.

virtual ~NFacePairing ()
 Deallocates any memory used by this structure.

unsigned getNumberOfTetrahedra () const
 Returns the number of tetrahedra whose faces are (potentially) paired in this particular matching.

const NTetFacedest (const NTetFace &source) const
 Returns the other face to which the given tetrahedron face is paired.

const NTetFacedest (unsigned tet, unsigned face) const
 Returns the other face to which the given tetrahedron face is paired.

const NTetFaceoperator[] (const NTetFace &source) const
 Returns the other face to which the given tetrahedron face is paired.

bool isUnmatched (const NTetFace &source) const
 Determines whether the given tetrahedron face has been left deliberately unmatched.

bool isUnmatched (unsigned tet, unsigned face) const
 Determines whether the given tetrahedron face has been left deliberately unmatched.

bool isCanonical () const
 Determines whether this face pairing is in canonical form, i.e., is a minimal representative of its isomorphism class.

void findAutomorphisms (NFacePairingIsoList &list) const
 Fills the given list with the set of all combinatorial automorphisms of this face pairing.

std::string toString () const
 Returns a human-readable representation of this face pairing.

std::string toTextRep () const
 Returns a text-based representation of this face pairing that can be used to reconstruct the face pairing.

bool isClosed () const
 Determines whether this face pairing is closed.

bool hasTripleEdge () const
 Determines whether this face pairing contains a triple edge.

void followChain (unsigned &tet, NFacePair &faces) const
 Follows a chain as far as possible from the given point.

bool hasBrokenDoubleEndedChain () const
 Determines whether this face pairing contains a broken double-ended chain.

bool hasOneEndedChainWithDoubleHandle () const
 Determines whether this face pairing contains a one-ended chain with a double handle.

void * run (void *param)
 Internal to findAllPairings().


Static Public Member Functions

NFacePairingfromTextRep (const std::string &rep)
 Reconstructs a face pairing from a text-based representation.

bool findAllPairings (unsigned nTetrahedra, NBoolSet boundary, int nBdryFaces, UseFacePairing use, void *useArgs=0, bool newThread=false)
 Generates all possible face pairings satisfying the given constraints.


Detailed Description

Represents a specific pairwise matching of tetrahedron faces.

Given a fixed number of tetrahedra, each tetrahedron face is either paired with some other tetrahedron face (which is in turn paired with it) or remains unmatched. A tetrahedron face cannot be paired with itself.

Such a matching models part of the structure of a triangulation, in which each tetrahedron face is either glued to some other tetrahedron face (which is in turn glued to it) or is an unglued boundary face.

Note that if this pairing is used to construct an actual triangulation, the individual gluing permutations will still need to be specified; they are not a part of this structure.

Test:
Test suite contains partial tests.


Constructor & Destructor Documentation

regina::NFacePairing::NFacePairing const NFacePairing cloneMe  ) 
 

Creates a new face pairing that is a clone of the given face pairing.

Parameters:
cloneMe the face pairing to clone.

regina::NFacePairing::~NFacePairing  )  [inline, virtual]
 

Deallocates any memory used by this structure.


Member Function Documentation

const NTetFace & regina::NFacePairing::dest unsigned  tet,
unsigned  face
const [inline]
 

Returns the other face to which the given tetrahedron face is paired.

If the given face is left deliberately unmatched, the value returned will be boundary (as returned by NTetFace::isBoundary()).

Parameters:
tet the tetrahedron under investigation (this must be strictly less than the total number of tetrahedra under consideration).
face the face of the given tetrahedron under investigation (between 0 and 3 inclusive).
Returns:
the other face to which the given face is paired.

const NTetFace & regina::NFacePairing::dest const NTetFace source  )  const [inline]
 

Returns the other face to which the given tetrahedron face is paired.

If the given face is left deliberately unmatched, the value returned will be boundary (as returned by NTetFace::isBoundary()).

Precondition:
The given face is a real tetrahedron face (not boundary, before-the-start or past-the-end).
Parameters:
source the face under investigation.
Returns:
the other face to which the given face is paired.

bool regina::NFacePairing::findAllPairings unsigned  nTetrahedra,
NBoolSet  boundary,
int  nBdryFaces,
UseFacePairing  use,
void *  useArgs = 0,
bool  newThread = false
[static]
 

Generates all possible face pairings satisfying the given constraints.

Only connected face pairings (pairings in which each tetrahedron can be reached from each other via a series of individual matched faces) will be produced.

Each face pairing will be produced precisely once up to isomorphism. Face pairings are considered isomorphic if they are related by a relabelling of the tetrahedra and/or a renumbering of the four faces of each tetrahedron. Each face pairing that is generated will be a minimal representative of its isomorphism class, i.e., will be in canonical form as described by isCanonical().

For each face pairing that is generated, routine use (as passed to this function) will be called with that pairing and its automorphisms as arguments.

Once the generation of face pairings has finished, routine use will be called once more, this time with null as its first two arguments (the face pairing and its automorphisms).

The face pairing generation may be run in the current thread or as a separate thread.

Todo:
Optimise (long-term): When generating face pairings, do some checking to eliminate cases in which tetrahedron (k > 0) can be swapped with tetrahedron 0 to produce a smaller representation of the same pairing.

Feature: Allow cancellation of face pairing generation.

Python:
Not present.
Parameters:
nTetrahedra the number of tetrahedra whose faces should be (potentially) matched.
boundary determines whether any faces may be left unmatched. This set should contain true if pairings with at least one unmatched face are to be generated, and should contain false if pairings with no unmatched faces are to be generated.
nBdryFaces specifies the precise number of faces that should be left unmatched. If this parameter is negative, it is ignored and no additional restriction is imposed. If parameter boundary does not contain true, this parameter is likewise ignored. If parameter boundary does contain true and this parameter is non-negative, only pairings with precisely this many unmatched faces will be generated. In particular, if this parameter is positive then pairings with no unmatched faces will not be produced irrespective of whether false is contained in parameter boundary. Note that, in order to produce any pairings at all, this parameter must be even and at most 2T+2, where T is the number of tetrahedra requested.
use the function to call upon each face pairing that is found. The first parameter passed to this function will be a face pairing. The second parameter will be a list of all its automorphisms (relabellings of tetrahedra and individual tetrahedron faces that produce the exact same pairing). The third parameter will be parameter useArgs as was passed to this routine.
useArgs the pointer to pass as the final parameter for the function use which will be called upon each pairing found.
newThread true if face pairing generation should be performed in a separate thread, or false if generation should take place in the current thread. If this parameter is true, this routine will exit immediately (after spawning the new thread).
Returns:
true if the new thread was successfully started (or if face pairing generation has taken place in the current thread), or false if the new thread could not be started.

void regina::NFacePairing::findAutomorphisms NFacePairingIsoList list  )  const [inline]
 

Fills the given list with the set of all combinatorial automorphisms of this face pairing.

An automorphism is a relabelling of the tetrahedra and/or a renumbering of the four faces of each tetrahedron resulting in precisely the same face pairing.

This routine uses optimisations that can cause unpredictable breakages if this face pairing is not in canonical form.

The automorphisms placed in the given list will be newly created; it is the responsibility of the caller of this routine to deallocate them.

Precondition:
The given list is empty.

This face pairing is connected, i.e., it is possible to reach any tetrahedron from any other tetrahedron via a series of matched face pairs.

This face pairing is in canonical form as described by isCanonical().

Python:
Not present.
Parameters:
list the list into which the newly created automorphisms will be placed.

void regina::NFacePairing::followChain unsigned &  tet,
NFacePair faces
const
 

Follows a chain as far as possible from the given point.

A chain is the underlying face pairing for a layered chain; specifically it involves one tetrahedron joined to a second along two faces, the remaining two faces of the second tetrahedron joined to a third and so on. A chain can involve as few as one tetrahedron or as many as we like. Note that the remaining two faces of the first tetrahedron and the remaining two faces of the final tetrahedron remain unaccounted for by this structure.

This routine begins with two faces of a given tetrahedron, described by parameters tet and face. If these two faces are both joined to some different tetrahedron, parameter tet will be changed to this new tetrahedron and parameter faces will be changed to the remaining faces of this new tetrahedron (i.e., the two faces that were not joined to the original faces of the original tetrahedron).

This procedure is repeated as far as possible until either the two faces in question join to two different tetrahedra, the two faces join to each other, or at least one of the two faces is unmatched.

Thus, given one end of a chain, this procedure can be used to follow the face pairings through to the other end of the chain.

Warning:
You must be sure when calling this routine that you are not inside a chain that loops back onto itself! If the face pairing forms a large loop with each tetrahedron joined by two faces to the next, this routine will cycle around the loop forever and never return.
Parameters:
tet the index in the underlying triangulation of the tetrahedron to begin at. This parameter will be modified directly by this routine as a way of returning the results.
faces the pair of face numbers in the given tetrahedron at which we begin. This parameter will also be modified directly by this routine as a way of returning results.

NFacePairing* regina::NFacePairing::fromTextRep const std::string &  rep  )  [static]
 

Reconstructs a face pairing from a text-based representation.

This text-based representation must be in the format produced by routine toTextRep().

The face pairing returned will be newly constructed; it is the responsibility of the caller of this routine to deallocate it.

Precondition:
The face pairing to be reconstructed involves at least one tetrahedron.
Parameters:
rep a text-based representation of a face pairing, as produced by routine toTextRep().
Returns:
the corresponding newly constructed face pairing, or null if the given text-based representation was invalid.

unsigned regina::NFacePairing::getNumberOfTetrahedra  )  const [inline]
 

Returns the number of tetrahedra whose faces are (potentially) paired in this particular matching.

Returns:
the number of tetrahedra under consideration.

bool regina::NFacePairing::hasBrokenDoubleEndedChain  )  const
 

Determines whether this face pairing contains a broken double-ended chain.

A chain involves a sequence of tetrahedra, each joined to the next along two faces, and is described in detail in the documentation for followChain().

A one-ended chain is a chain in which the first tetrahedron is also joined to itself along one face (i.e., the underlying face pairing for a layered solid torus). A double-ended chain is a chain in which the first tetrahedron is joined to itself along one face and the final tetrahedron is also joined to itself along one face (i.e., the underlying face pairing for a layered lens space).

A broken double-ended chain consists of two one-ended chains (using distinct sets of tetrahedra) joined together along one face. The remaining two faces (one from each chain) that were unaccounted for by the individual one-ended chains remain unaccounted for by this broken double-ended chain.

In this routine we are interested specifically in finding a broken double-ended chain that is not a part of a complete double-ended chain, i.e., the final two unaccounted faces are not joined together.

Returns:
true if and only if this face pairing contains a broken double-ended chain that is not part of a complete double-ended chain.

bool regina::NFacePairing::hasOneEndedChainWithDoubleHandle  )  const
 

Determines whether this face pairing contains a one-ended chain with a double handle.

A chain involves a sequence of tetrahedra, each joined to the next along two faces, and is described in detail in the documentation for followChain().

A one-ended chain is a chain in which the first tetrahedron is also joined to itself along one face (i.e., the underlying face pairing for a layered solid torus).

A one-ended chain with a double handle begins with a one-ended chain. The two faces that are unaccounted for by this one-ended chain must be joined to two different tetrahedra, and these two tetrahedra must be joined to each other along two faces. The remaining two faces of these two tetrahedra remain unaccounted for by this structure.

Returns:
true if and only if this face pairing contains a one-ended chain with a double handle.

bool regina::NFacePairing::hasTripleEdge  )  const
 

Determines whether this face pairing contains a triple edge.

A triple edge is where two different tetrahedra are joined along three of their faces.

Returns:
true if and only if this face pairing contains a triple edge.

bool regina::NFacePairing::isCanonical  )  const
 

Determines whether this face pairing is in canonical form, i.e., is a minimal representative of its isomorphism class.

Isomorphisms of face pairings correspond to relabellings of tetrahedra and relabellings of the four faces within each tetrahedron.

Face pairings are ordered by lexicographical comparison of dest(0,0), dest(0,1), ..., dest(n-1,3), where n is the value of getNumberOfTetrahedra().

Returns:
true if and only if this face pairing is in canonical form.

bool regina::NFacePairing::isClosed  )  const
 

Determines whether this face pairing is closed.

A closed face pairing has no unmatched faces.

bool regina::NFacePairing::isUnmatched unsigned  tet,
unsigned  face
const [inline]
 

Determines whether the given tetrahedron face has been left deliberately unmatched.

Parameters:
tet the tetrahedron under investigation (this must be strictly less than the total number of tetrahedra under consideration).
face the face of the given tetrahedron under investigation (between 0 and 3 inclusive).
Returns:
true if the given face has been left unmatched, or false if the given face is paired with some other face.

bool regina::NFacePairing::isUnmatched const NTetFace source  )  const [inline]
 

Determines whether the given tetrahedron face has been left deliberately unmatched.

Precondition:
The given face is a real tetrahedron face (not boundary, before-the-start or past-the-end).
Parameters:
source the face under investigation.
Returns:
true if the given face has been left unmatched, or false if the given face is paired with some other face.

const NTetFace & regina::NFacePairing::operator[] const NTetFace source  )  const [inline]
 

Returns the other face to which the given tetrahedron face is paired.

This is a convenience operator whose behaviour is identical to that of dest().

If the given face is left deliberately unmatched, the value returned will be boundary (as returned by NTetFace::isBoundary()).

Precondition:
The given face is a real tetrahedron face (not boundary, before-the-start or past-the-end).
Parameters:
source the face under investigation.
Returns:
the other face to which the given face is paired.

void* regina::NFacePairing::run void *  param  )  [virtual]
 

Internal to findAllPairings().

This routine should never be called directly.

Performs the actual generation of face pairings, possibly as a separate thread. At most one copy of this routine should be running at any given time for a particular NFacePairing instance.

Python:
Not present.
Parameters:
param a structure containing the parameters that were passed to findAllPairings().
Returns:
the value 0.

Implements regina::NThread.

std::string regina::NFacePairing::toString  )  const
 

Returns a human-readable representation of this face pairing.

The string returned will contain no newlines.

Returns:
a string representation of this pairing.

std::string regina::NFacePairing::toTextRep  )  const
 

Returns a text-based representation of this face pairing that can be used to reconstruct the face pairing.

This reconstruction is done through routine fromTextRep().

The text produced is not particularly readable; for a human-readable text representation, see routine toString() instead.

The string returned will contain no newlines.

Returns:
a text-based representation of this face pairing.


The documentation for this class was generated from the following file:
Copyright © 1999-2004, Ben Burton
This software is released under the GNU General Public License.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@debian.org).