#include <nfacepairing.h>
Public Member Functions | |
Constructors and Destructors | |
NFacePairing (const NFacePairing &cloneMe) | |
Creates a new face pairing that is a clone of the given face pairing. | |
NFacePairing (const NTriangulation &tri) | |
Creates the face pairing of given triangulation. | |
virtual | ~NFacePairing () |
Deallocates any memory used by this structure. | |
Basic Queries | |
(end: Constructors and Destructors) | |
unsigned | getNumberOfTetrahedra () const |
Returns the number of tetrahedra whose faces are (potentially) paired in this particular matching. | |
const NTetFace & | dest (const NTetFace &source) const |
Returns the other face to which the given tetrahedron face is paired. | |
const NTetFace & | dest (unsigned tet, unsigned face) const |
Returns the other face to which the given tetrahedron face is paired. | |
const NTetFace & | operator[] (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 | isClosed () const |
Determines whether this face pairing is closed. | |
Isomorphic Representations | |
(end: Basic Queries) | |
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. | |
Input and Output | |
(end: Isomorphic Representations) | |
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. | |
void | writeDot (std::ostream &out, const char *prefix=0, bool subgraph=false) const |
Writes the graph corresponding to this face pairing in the Graphviz DOT language. | |
Subgraph Queries | |
void | followChain (unsigned &tet, NFacePair &faces) const |
Follows a chain as far as possible from the given point. | |
bool | hasTripleEdge () const |
Determines whether this face pairing contains a triple edge. | |
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. | |
bool | hasWedgedDoubleEndedChain () const |
Determines whether this face pairing contains a wedged double-ended chain. | |
bool | hasOneEndedChainWithStrayBigon () const |
Determines whether this face pairing contains a one-ended chain with a stray bigon. | |
bool | hasTripleOneEndedChain () const |
Determines whether this face pairing contains a triple one-ended chain. | |
bool | hasSingleStar () const |
Determines whether this face pairing contains a single-edged star. | |
bool | hasDoubleStar () const |
Determines whether this face pairing contains a double-edged star. | |
bool | hasDoubleSquare () const |
Determines whether this face pairing contains a double-edged square. | |
Graph Enumeration | |
(end: Subgraph Queries) | |
void * | run (void *param) |
Internal to findAllPairings(). | |
Static Public Member Functions | |
static NFacePairing * | fromTextRep (const std::string &rep) |
(end: Input and Output) | |
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 face pairings. | |
static bool | findAllPairings (unsigned nTetrahedra, NBoolSet boundary, int nBdryFaces, UseFacePairing use, void *useArgs=0, bool newThread=false) |
(end: Graph Enumeration) |
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.
regina::NFacePairing::NFacePairing | ( | const NFacePairing & | cloneMe | ) |
Creates a new face pairing that is a clone of the given face pairing.
cloneMe | the face pairing to clone. |
regina::NFacePairing::NFacePairing | ( | const NTriangulation & | tri | ) |
Creates the face pairing of given 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.
tri | the triangulation whose face pairing should be constructed. |
regina::NFacePairing::~NFacePairing | ( | ) | [inline, virtual] |
Deallocates any memory used by this structure.
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()).
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 tetrahedron face is paired.
If the given face is left deliberately unmatched, the value returned will be boundary (as returned by NTetFace::isBoundary()).
source | the face under investigation. |
static bool regina::NFacePairing::findAllPairings | ( | unsigned | nTetrahedra, | |
NBoolSet | boundary, | |||
int | nBdryFaces, | |||
UseFacePairing | use, | |||
void * | useArgs = 0 , |
|||
bool | newThread = false | |||
) | [static] |
(end: Graph Enumeration)
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.
Feature: Allow cancellation of face pairing generation.
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). |
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.
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().
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 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.
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. |
static NFacePairing* regina::NFacePairing::fromTextRep | ( | const std::string & | rep | ) | [static] |
(end: Input and Output)
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.
rep | a text-based representation of a face pairing, as produced by routine toTextRep(). |
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.
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.
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.
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).
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.
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:
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.
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).
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.
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.
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.
true
if and only if this face pairing contains a wedged double-ended chain. 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()
.
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.
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). |
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.
source | the face under investigation. |
true
if the given face has been left unmatched, or false
if the given face is paired with some other face. 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()).
source | the face under investigation. |
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.
param | a structure containing the parameters that were passed to findAllPairings(). |
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.
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.
void regina::NFacePairing::writeDot | ( | std::ostream & | out, | |
const char * | prefix = 0 , |
|||
bool | subgraph = false | |||
) | const |
Writes the graph corresponding to this face pairing in the Graphviz DOT language.
Every vertex of this graph represents a tetrahedron, and every edge represents a pair of tetrahedron faces that are joined together. Note that for a closed triangulation this graph will be entirely 4-valent; for triangulations with boundary faces, some graph vertices will have degree three or less.
The graph can either be written as a complete DOT graph, or as a clustered subgraph within some larger DOT graph (according to whether the argument subgraph is passed as false
or true
).
If a complete DOT graph is being written, the output may be used as a standalone DOT file ready for use with Graphviz.
If a subgraph is being written, the output will contain a single subgraph
section that should be inserted into some larger DOT file. Note that the output generated by writeDotHeader(), followed by one or more subgraphs and then a closing curly brace will suffice. The subgraph name will begin with the string cluster_
, so that Graphviz identifies it as a cluster accordingly.
The argument prefix will be prepended to the name of each graph vertex, and will also be used in the name of the graph or subgraph. Using unique prefixes becomes important if you are calling writeDot() several times to generate several subgraphs for use in a single DOT file. If the prefix argument is null or empty then a default prefix will be used.
Note that this routine generates undirected graphs, not directed graphs. The final DOT file should be used with either the neato or fdp programs shipped with Graphviz.
out | the output stream to which to write. | |
prefix | a string to prepend to the name of each graph vertex, and to include in the graph or subgraph name; see above for details. | |
subgraph | false if a complete standalone DOT graph should be output, or true if a clustered subgraph should be output for use in some larger DOT file. |
static void regina::NFacePairing::writeDotHeader | ( | std::ostream & | out, | |
const char * | graphName = 0 | |||
) | [static] |
Writes header information for a Graphviz DOT file that will describe the graphs for one or more face pairings.
See the writeDot() documentation for further information on such graphs.
The output will be in the Graphviz DOT language, and will include appropriate display settings for graphs, edges and nodes. The opening brace for a graph
section of the DOT file is included.
This routine may be used with writeDot() to generate a single DOT file containing the graphs for several different face pairings. A complete DOT file can be produced by calling this routine, then calling writeDot() in subgraph mode for each face pairing, then outputting a final closing curly brace.
Note that if you require a DOT file containing the graph for only a single face pairing, this routine is unnecessary; you may simply call writeDot() in full graph mode instead.
This routine is suitable for generating undirected graphs, not directed graphs. The final DOT file should be used with either the neato or fdp programs shipped with Graphviz.
out | the output stream to which to write. | |
graphName | the name of the graph in the DOT file. If this is null or empty then a default graph name will be used. |