Regina Calculation Engine
Public Member Functions | Friends | List of all members
regina::NFacePairing Class Reference

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

#include <census/nfacepairing.h>

Inheritance diagram for regina::NFacePairing:
regina::NGenericFacetPairing< 3 > regina::NThread

Public Member Functions

 NFacePairing (const NFacePairing &cloneMe)
 Creates a new face pairing that is a clone of the given face pairing. More...
 
 NFacePairing (const NTriangulation &tri)
 Creates the face pairing of the given 3-manifold triangulation. More...
 
unsigned getNumberOfTetrahedra () const
 A legacy alias for size(), provided for backward compatibility only. More...
 
void followChain (unsigned &tet, NFacePair &faces) const
 Follows a chain as far as possible from the given point. More...
 
bool hasTripleEdge () const
 Determines whether this face pairing contains a triple edge. More...
 
bool hasBrokenDoubleEndedChain () const
 Determines whether this face pairing contains a broken double-ended chain. More...
 
bool hasOneEndedChainWithDoubleHandle () const
 Determines whether this face pairing contains a one-ended chain with a double handle. More...
 
bool hasWedgedDoubleEndedChain () const
 Determines whether this face pairing contains a wedged double-ended chain. More...
 
bool hasOneEndedChainWithStrayBigon () const
 Determines whether this face pairing contains a one-ended chain with a stray bigon. More...
 
bool hasTripleOneEndedChain () const
 Determines whether this face pairing contains a triple one-ended chain. More...
 
bool hasSingleStar () const
 Determines whether this face pairing contains a single-edged star. More...
 
bool hasDoubleStar () const
 Determines whether this face pairing contains a double-edged star. More...
 
bool hasDoubleSquare () const
 Determines whether this face pairing contains a double-edged square. More...
 
- Public Member Functions inherited from regina::NGenericFacetPairing< 3 >
 NGenericFacetPairing (const NGenericFacetPairing &cloneMe)
 Creates a new facet pairing that is a clone of the given facet pairing. More...
 
 NGenericFacetPairing (const Triangulation &tri)
 Creates the facet pairing of given triangulation. More...
 
virtual ~NGenericFacetPairing ()
 Deallocates any memory used by this structure. More...
 
unsigned size () const
 Returns the number of simplices whose facets are described by this facet pairing. More...
 
const NFacetSpec< dim > & dest (const NFacetSpec< dim > &source) const
 Returns the other facet to which the given simplex facet is paired. More...
 
const NFacetSpec< dim > & dest (unsigned simp, unsigned facet) const
 Returns the other facet to which the given simplex facet is paired. More...
 
const NFacetSpec< dim > & operator[] (const NFacetSpec< dim > &source) const
 Returns the other facet to which the given simplex facet is paired. More...
 
bool isUnmatched (const NFacetSpec< dim > &source) const
 Determines whether the given simplex facet has been left deliberately unmatched. More...
 
bool isUnmatched (unsigned simp, unsigned facet) const
 Determines whether the given simplex facet has been left deliberately unmatched. More...
 
bool isClosed () const
 Determines whether this facet pairing is closed. More...
 
bool isCanonical () const
 Determines whether this facet pairing is in canonical form, i.e., is a lexicographically minimal representative of its isomorphism class. More...
 
void findAutomorphisms (IsoList &list) const
 Fills the given list with the set of all combinatorial automorphisms of this facet pairing. More...
 
std::string toString () const
 A deprecated alias for str(), which returns a human-readable representation of this facet pairing. More...
 
std::string str () const
 Returns a human-readable representation of this facet pairing. More...
 
std::string toTextRep () const
 Returns a text-based representation of this facet pairing that can be used to reconstruct the facet pairing. More...
 
void writeDot (std::ostream &out, const char *prefix=0, bool subgraph=false, bool labels=false) const
 Writes the graph corresponding to this facet pairing in the Graphviz DOT language. More...
 
std::string dot (const char *prefix=0, bool subgraph=false, bool labels=false) const
 Returns a Graphviz DOT representation of the graph that describes this facet pairing. More...
 
void * run (void *param)
 Internal to findAllPairings(). More...
 
- Public Member Functions inherited from regina::NThread
virtual ~NThread ()
 Destroys this thread. More...
 
bool start (void *args=0, bool deleteAfterwards=false)
 Starts a new thread and performs run() within this new thread. More...
 
void join ()
 Waits for a previously-started thread to terminate. More...
 

Friends

class NGenericFacetPairing< 3 >
 

Additional Inherited Members

- Public Types inherited from regina::NGenericFacetPairing< 3 >
typedef DimTraits< dim >
::FacetPairing 
FacetPairing
 The facet pairing class specific to this dimension. More...
 
typedef DimTraits< dim >
::Isomorphism 
Isomorphism
 The isomorphism class used for triangulations in this dimension. More...
 
typedef DimTraits< dim >::Perm Perm
 The permutation class used to glue together facets of simplices when building triangulations in this dimension. More...
 
typedef DimTraits< dim >::Simplex Simplex
 The class that represents a top-level simplex of a triangulation in this dimension. More...
 
typedef DimTraits< dim >
::Triangulation 
Triangulation
 The triangulation class specific to this dimension. More...
 
typedef std::list< Isomorphism * > IsoList
 A list of isomorphisms on pairwise matchings of simplex facets. More...
 
typedef void(* Use )(const FacetPairing *, const IsoList *, void *)
 A routine that can do arbitrary processing upon a facet pairing and its automorphisms. More...
 
- Static Public Member Functions inherited from regina::NGenericFacetPairing< 3 >
static FacetPairingfromTextRep (const std::string &rep)
 Reconstructs a facet pairing from a text-based representation. More...
 
static void writeDotHeader (std::ostream &out, const char *graphName=0)
 Writes header information for a Graphviz DOT file that will describe the graphs for one or more facet pairings. More...
 
static std::string dotHeader (const char *graphName=0)
 Returns header information for a Graphviz DOT file that will describe the graphs for one or more facet pairings. More...
 
static bool findAllPairings (unsigned nSimplices, NBoolSet boundary, int nBdryFacets, Use use, void *useArgs=0, bool newThread=false)
 Generates all possible facet pairings satisfying the given constraints. More...
 
- Protected Member Functions inherited from regina::NGenericFacetPairing< 3 >
 NGenericFacetPairing (unsigned size)
 Creates a new facet pairing. More...
 
NFacetSpec< dim > & dest (const NFacetSpec< dim > &source)
 Returns the other facet to which the given simplex facet is paired. More...
 
NFacetSpec< dim > & dest (unsigned simp, unsigned facet)
 Returns the other facet to which the given simplex facet is paired. More...
 
NFacetSpec< dim > & operator[] (const NFacetSpec< dim > &source)
 Returns the other facet to which the given simplex facet is paired. More...
 
bool noDest (const NFacetSpec< dim > &source) const
 Determines whether the matching for the given simplex facet has not yet been determined. More...
 
bool noDest (unsigned simp, unsigned facet) const
 Determines whether the matching for the given simplex facet has not yet been determined. More...
 
bool isCanonicalInternal (IsoList &list) const
 Determines whether this facet pairing is in canonical (smallest lexicographical) form, given a small set of assumptions. More...
 
- Protected Attributes inherited from regina::NGenericFacetPairing< 3 >
unsigned size_
 The number of simplices under consideration. More...
 
NFacetSpec< dim > * pairs_
 The other facet to which each simplex facet is paired. More...
 

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:
Included in the test suite.

Constructor & Destructor Documentation

regina::NFacePairing::NFacePairing ( const NFacePairing cloneMe)
inline

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

Parameters
cloneMethe face pairing to clone.
regina::NFacePairing::NFacePairing ( const NTriangulation tri)
inline

Creates the face pairing of the given 3-manifold triangulation.

This is the face pairing that describes how the tetrahedron faces of the given triangulation are joined together, as described in the class notes.

Precondition
The given triangulation is not empty.
Parameters
trithe triangulation whose face pairing should be constructed.

Member Function Documentation

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 faces. 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
tetthe 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.
facesthe 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.
unsigned regina::NFacePairing::getNumberOfTetrahedra ( ) const
inline

A legacy alias for size(), provided for backward compatibility only.

This routine returns the number of tetrahedra whose faces are described by this face pairing.

Deprecated:
As of Regina 4.94, this routine has been renamed to size(). The old name getNumberOfTetrahedra() is provided for backward compatibility, but will be removed in some future version of Regina.
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.

A face pairing containing a broken double-ended chain cannot model a closed minimal irreducible P^2-irreducible 3-manifold triangulation on more than two tetrahedra. See "Face pairing graphs and 3-manifold enumeration", Benjamin A. Burton, J. Knot Theory Ramifications 13 (2004), 1057–1101.

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::hasDoubleSquare ( ) const

Determines whether this face pairing contains a double-edged square.

A double-edged square involves four distinct tetrahedra that meet each other as follows. Two pairs of tetrahedra are joined along two pairs of faces each. Then each tetrahedron is joined along a single face to one tetrahedron of the other pair. The four tetrahedron faces not yet joined to anything (one from each tetrahedron) remain unaccounted for by this structure.

Returns
true if and only if this face pairing contains a double-edged square.
bool regina::NFacePairing::hasDoubleStar ( ) const

Determines whether this face pairing contains a double-edged star.

A double-edged star involves two tetrahedra that are adjacent along two separate pairs of faces, where the four remaining faces of these tetrahedra are joined to four entirely new tetrahedra (so that none of the six tetrahedra described in this structure are the same).

Returns
true if and only if this face pairing contains a double-edged star.
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.

A face pairing containing a one-ended chain with a double handle cannot model a closed minimal irreducible P^2-irreducible 3-manifold triangulation on more than two tetrahedra. See "Face pairing graphs and 3-manifold enumeration", Benjamin A. Burton, J. Knot Theory Ramifications 13 (2004), 1057–1101.

Returns
true if and only if this face pairing contains a one-ended chain with a double handle.
bool regina::NFacePairing::hasOneEndedChainWithStrayBigon ( ) const

Determines whether this face pairing contains a one-ended chain with a stray bigon.

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 stray bigon describes the following structure. We begin with a one-ended chain. Two new tetrahedra are added; these are joined to each other along two pairs of faces, and one of the new tetrahedra is joined to the end of the one-ended chain. We then ensure that:

  • This configuration is not part of a longer one-ended chain that encompasses all of the aforementioned tetrahedra;
  • There is no extra tetrahedron that is joined to both the two new tetrahedra and the end of the chain;
  • There is no extra tetrahedron that is joined to the end of the chain along one face and the far new tetrahedron along two additional faces (where by "the far new tetrahedron" we mean the new tetrahedron that was not originally joined to the chain).

Aside from these constraints, the remaining four tetrahedron faces (two faces of the far new tetrahedron, one face of the other new tetrahedron, and one face at the end of the chain) remain unaccounted for by this structure.

A face pairing containing a structure of this type cannot model a closed minimal irreducible P^2-irreducible 3-manifold triangulation on more than two tetrahedra. 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.

Returns
true if and only if this face pairing contains a one-ended chain with a stray bigon.
bool regina::NFacePairing::hasSingleStar ( ) const

Determines whether this face pairing contains a single-edged star.

A single-edged star involves two tetrahedra that are adjacent along a single face, where the six remaining faces of these tetrahedra are joined to six entirely new tetrahedra (so that none of the eight tetrahedra described in this structure are the same).

Returns
true if and only if this face pairing contains a single-edged star.
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.

A face pairing containing a triple edge cannot model a closed minimal irreducible P^2-irreducible 3-manifold triangulation on more than two tetrahedra. See "Face pairing graphs and 3-manifold enumeration", Benjamin A. Burton, J. Knot Theory Ramifications 13 (2004), 1057–1101.

Returns
true if and only if this face pairing contains a triple edge.
bool regina::NFacePairing::hasTripleOneEndedChain ( ) const

Determines whether this face pairing contains a triple one-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 triple one-ended chain is created from three one-ended chains as follows. Two new tetrahedra are added, and each one-ended chain is joined to each of the new tetrahedra along a single face. The remaining two faces (one from each of the new tetrahedra) remain unaccounted for by this structure.

A face pairing containing a triple one-ended chain cannot model a closed minimal irreducible P^2-irreducible 3-manifold triangulation on more than two tetrahedra. 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.

Returns
true if and only if this face pairing contains a triple one-ended chain.
bool regina::NFacePairing::hasWedgedDoubleEndedChain ( ) const

Determines whether this face pairing contains a wedged 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 wedged double-ended chain is created from two one-ended chains as follows. Two new tetrahedra are added, and each one-ended chain is joined to each of the new tetrahedra along a single face. In addition, the two new tetrahedra are joined to each other along a single face. The remaining two faces (one from each of the new tetrahedra) remain unaccounted for by this structure.

An alternative way of viewing a wedged double-ended chain is as an ordinary double-ended chain, where one of the internal tetrahedra is removed and replaced with a pair of tetrahedra joined to each other. Whereas the original tetrahedron met its two neighbouring tetrahedra along two faces each (giving a total of four face identifications), the two new tetrahedra now meet each of the two neighbouring tetrahedra along a single face each (again giving four face identifications).

Note that if this alternate construction is used to replace one of the end tetrahedra of the double-ended chain (not an internal tetrahedron), the resulting structure will either be a triple edge or a one-ended chain with a double handle (according to whether the original chain has zero or positive length). See hasTripleEdge() and hasOneEndedChainWithDoubleHandle() for further details.

A face pairing containing a wedged double-ended chain cannot model a closed minimal irreducible P^2-irreducible 3-manifold triangulation on more than two tetrahedra. 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.

Returns
true if and only if this face pairing contains a wedged double-ended chain.

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