regina::NFacePairing Class Reference
Census of Triangulations

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

`#include <census/nfacepairing.h>`

Inheritance diagram for regina::NFacePairing:

## 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 FacetPairing * | fromTextRep (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...
Static Public Member Functions inherited from regina::NThread
static bool | start (void *(*routine)(void *), void *args, NThreadID *id)
| Starts a new thread that performs the given routine. More...
static void | yield ()
| Causes the currently running thread to voluntarily relinquish the processor. 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

  cloneMe | the 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

  tri | the 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

  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.

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:

- census/nfacepairing.h

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