Regina Calculation Engine
|
A generic helper class for working with triangulations of arbitrary dimension. More...
#include <generic/ngenerictriangulation.h>
Public Types | |
typedef void | Triangulation |
The main data type for a dim-manifold triangulation. More... | |
typedef void | Simplex |
The data type for a top-dimensional simplex in a dim-manifold triangulation. More... | |
typedef void | Isomorphism |
The data type for an isomorphism between two dim-manifold triangulations. More... | |
typedef void | FacetPairing |
The data type that represents a pairing of facets of top-dimensional simplices in a dim-manifold triangulation. More... | |
typedef void | Perm |
The permutation type used to describe gluings between top-dimensional simplices in a dim-manifold triangulation. More... | |
Public Member Functions | |
Basic Properties | |
bool | isEmpty () const |
Determines whether this triangulation is empty. More... | |
Isomorphism Testing | |
bool | isIdenticalTo (const typename DimTraits< dim >::Triangulation &other) const |
Determines if this triangulation is combinatorially identical to the given triangulation. More... | |
std::auto_ptr< typename DimTraits< dim >::Isomorphism > | isIsomorphicTo (const typename DimTraits< dim >::Triangulation &other) const |
Determines if this triangulation is combinatorially isomorphic to the given triangulation. More... | |
std::auto_ptr< typename DimTraits< dim >::Isomorphism > | isContainedIn (const typename DimTraits< dim >::Triangulation &other) const |
Determines if an isomorphic copy of this triangulation is contained within the given triangulation, possibly as a subcomplex of some larger component (or components). More... | |
unsigned long | findAllIsomorphisms (const typename DimTraits< dim >::Triangulation &other, std::list< typename DimTraits< dim >::Isomorphism * > &results) const |
Finds all ways in which this triangulation is combinatorially isomorphic to the given triangulation. More... | |
unsigned long | findAllSubcomplexesIn (const typename DimTraits< dim >::Triangulation &other, std::list< typename DimTraits< dim >::Isomorphism * > &results) const |
Finds all ways in which an isomorphic copy of this triangulation is contained within the given triangulation, possibly as a subcomplex of some larger component (or components). More... | |
bool | makeCanonical () |
Relabel the top-dimensional simplices and their vertices so that this triangulation is in canonical form. More... | |
Exporting Triangulations | |
std::string | isoSig (typename DimTraits< dim >::Isomorphism **relabelling=0) const |
Constructs the isomorphism signature for this triangulation. More... | |
Static Public Member Functions | |
Importing Triangulations | |
static DimTraits< dim > ::Triangulation * | fromIsoSig (const std::string &sig) |
Recovers a full triangulation from an isomorphism signature. More... | |
static size_t | isoSigComponentSize (const std::string &sig) |
Deduces the number of top-dimensional simplices in a connected triangulation from its isomorphism signature. More... | |
A generic helper class for working with triangulations of arbitrary dimension.
This class is designed to implement member functions of the various triangulation classes in a unified, dimension-agnostic manner.
End users should not use this class directly. Instead they should call the corresponding member functions from the corresponding triangulation classes (NTriangulation and so on).
unsigned long regina::NGenericTriangulation< dim >::findAllIsomorphisms | ( | const typename DimTraits< dim >::Triangulation & | other, |
std::list< typename DimTraits< dim >::Isomorphism * > & | results | ||
) | const |
Finds all ways in which this triangulation is combinatorially isomorphic to the given triangulation.
This routine behaves identically to isIsomorphicTo(), except that instead of returning just one isomorphism, all such isomorphisms are returned.
See the isIsomorphicTo() notes for additional information.
The isomorphisms that are found will be inserted into the given list. These isomorphisms will be newly created, and the caller of this routine is responsible for destroying them. The given list will not be emptied before the new isomorphisms are inserted.
other | the triangulation to compare with this one. |
results | the list in which any isomorphisms found will be stored. |
unsigned long regina::NGenericTriangulation< dim >::findAllSubcomplexesIn | ( | const typename DimTraits< dim >::Triangulation & | other, |
std::list< typename DimTraits< dim >::Isomorphism * > & | results | ||
) | const |
Finds all ways in which an isomorphic copy of this triangulation is contained within the given triangulation, possibly as a subcomplex of some larger component (or components).
This routine behaves identically to isContainedIn(), except that instead of returning just one isomorphism (which may be boundary incomplete and need not be onto), all such isomorphisms are returned.
See the isContainedIn() notes for additional information.
The isomorphisms that are found will be inserted into the given list. These isomorphisms will be newly created, and the caller of this routine is responsible for destroying them. The given list will not be emptied before the new isomorphisms are inserted.
other | the triangulation in which to search for isomorphic copies of this triangulation. |
results | the list in which any isomorphisms found will be stored. |
|
static |
Recovers a full triangulation from an isomorphism signature.
See isoSig() for more information on isomorphism signatures. It will be assumed that the signature describes a triangulation of dimension dim.
The triangulation that is returned will be newly created.
Calling isoSig() followed by fromIsoSig() is not guaranteed to produce an identical triangulation to the original, but it is guaranteed to produce a combinatorially isomorphic triangulation.
For a full and precise description of the isomorphism signature format for 3-manifold triangulations, see Simplification paths in the Pachner graphs of closed orientable 3-manifold triangulations, Burton, 2011, arXiv:1110.6080
. The format for other dimensions is essentially the same, but with minor dimension-specific adjustments.
sig | the isomorphism signature of the triangulation to construct. Note that, unlike dehydration strings for 3-manifold triangulations, case is important for isomorphism signatures. |
std::auto_ptr<typename DimTraits<dim>::Isomorphism> regina::NGenericTriangulation< dim >::isContainedIn | ( | const typename DimTraits< dim >::Triangulation & | other | ) | const |
Determines if an isomorphic copy of this triangulation is contained within the given triangulation, possibly as a subcomplex of some larger component (or components).
Specifically, this routine determines if there is a boundary incomplete combinatorial isomorphism from this triangulation to other. Boundary incomplete isomorphisms are described in detail in the Isomorphism class notes.
In particular, note that facets of top-dimensional simplices that lie on the boundary of this triangulation need not correspond to boundary facets of other, and that other may contain more top-dimensional simplices than this triangulation.
If a boundary incomplete isomorphism is found, the details of this isomorphism are returned. The isomorphism is newly constructed, and so to assist with memory management is returned as a std::auto_ptr. Thus, to test whether an isomorphism exists without having to explicitly deal with the isomorphism itself, you can call if (isContainedIn(other).get())
and the newly created isomorphism (if it exists) will be automatically destroyed.
If more than one such isomorphism exists, only one will be returned. For a routine that returns all such isomorphisms, see findAllSubcomplexesIn().
other | the triangulation in which to search for an isomorphic copy of this triangulation. |
|
inline |
Determines whether this triangulation is empty.
An empty triangulation is one with no simplices at all.
true
if and only if this triangulation is empty. bool regina::NGenericTriangulation< dim >::isIdenticalTo | ( | const typename DimTraits< dim >::Triangulation & | other | ) | const |
Determines if this triangulation is combinatorially identical to the given triangulation.
Here "identical" means that the triangulations have the same number of top-dimensional simplices, with gluings between the same pairs of numbered simplices using the same gluing permutations. In other words, "identical" means that the triangulations are isomorphic via the identity isomorphism.
To test for the less strict combinatorial isomorphism (which allows relabelling of the top-dimensional simplices and their vertices), see isIsomorphicTo() instead.
This test does not examine the textual simplex descriptions, as seen in Simplex::getDescription(); these may still differ. It also does not test the numbering of vertices, edges and so on, as used by getVertex(), getEdge() and so on; although at the time of writing these will always be numbered the same for identical triangulations, it is conceivable that in future versions of Regina there may be situations in which identical triangulations can acquire different numberings for vertices, edges, etc.
other | the triangulation to compare with this one. |
true
if and only if the two triangulations are combinatorially identical. std::auto_ptr<typename DimTraits<dim>::Isomorphism> regina::NGenericTriangulation< dim >::isIsomorphicTo | ( | const typename DimTraits< dim >::Triangulation & | other | ) | const |
Determines if this triangulation is combinatorially isomorphic to the given triangulation.
Specifically, this routine determines if there is a one-to-one and onto boundary complete combinatorial isomorphism from this triangulation to other. Boundary complete isomorphisms are described in detail in the Isomorphism class notes.
In particular, note that this triangulation and other must contain the same number of top-dimensional simplices for such an isomorphism to exist.
If you need to ensure that top-dimensional simplices are labelled the same in both triangulations, see the stricter test isIdenticalTo() instead.
If a boundary complete isomorphism is found, the details of this isomorphism are returned. The isomorphism is newly constructed, and so to assist with memory management is returned as a std::auto_ptr. Thus, to test whether an isomorphism exists without having to explicitly deal with the isomorphism itself, you can call if (isIsomorphicTo(other).get())
and the newly created isomorphism (if it exists) will be automatically destroyed.
If more than one such isomorphism exists, only one will be returned. For a routine that returns all such isomorphisms, see findAllIsomorphisms().
other | the triangulation to compare with this one. |
std::string regina::NGenericTriangulation< dim >::isoSig | ( | typename DimTraits< dim >::Isomorphism ** | relabelling = 0 | ) | const |
Constructs the isomorphism signature for this triangulation.
An isomorphism signature is a compact text representation of a triangulation. Unlike dehydrations for 3-manifold triangulations, an isomorphism signature uniquely determines a triangulation up to combinatorial isomorphism (assuming the dimension is known in advance). That is, two triangulations of dimension dim are combinatorially isomorphic if and only if their isomorphism signatures are the same.
The isomorphism signature is constructed entirely of printable characters, and has length proportional to n log n
, where n is the number of top-dimenisonal simplices.
Isomorphism signatures are more general than dehydrations: they can be used with any triangulation (including closed, bounded and/or disconnected triangulations, as well as triangulations with large numbers of triangles).
The time required to construct the isomorphism signature of a triangulation is O(n^2 log^2 n)
.
The routine fromIsoSig() can be used to recover a triangulation from an isomorphism signature. The triangulation recovered might not be identical to the original, but it will be combinatorially isomorphic.
If relabelling is non-null (i.e., it points to some Isomorphism pointer p), then it will be modified to point to a new isomorphism that describes the precise relationship between this triangulation and the reconstruction from fromIsoSig(). Specifically, the triangulation that is reconstructed from fromIsoSig() will be combinatorially identical to relabelling.apply(this)
.
For a full and precise description of the isomorphism signature format for 3-manifold triangulations, see Simplification paths in the Pachner graphs of closed orientable 3-manifold triangulations, Burton, 2011, arXiv:1110.6080
. The format for other dimensions is essentially the same, but with minor dimension-specific adjustments.
relabelling | if non-null, this will be modified to point to a new isomorphism describing the relationship between this triangulation and that reconstructed from fromIsoSig(), as described above. |
|
static |
Deduces the number of top-dimensional simplices in a connected triangulation from its isomorphism signature.
See isoSig() for more information on isomorphism signatures. It will be assumed that the signature describes a triangulation of dimension dim.
If the signature describes a connected triangulation, this routine will simply return the size of that triangulation (e.g., the number of tetrahedra in the case dim = 3). You can also pass an isomorphism signature that describes a disconnected triangulation; however, this routine will only return the number of simplices in the first connected component. If you need the total number of simplices in a disconnected triangulation, you will need to reconstruct the full triangulation by calling fromIsoSig() instead.
This routine is very fast, since it only examines the first few characters of the isomorphism signature (in which the size of the first component is encoded). However, it is therefore possible to pass an invalid isomorphism signature and still receive a positive result. If you need to test whether a signature is valid or not, you must call fromIsoSig() instead, which will examine the entire signature in full.
sig | an isomorphism signature of a dim-dimensional triangulation. Note that, unlike dehydration strings for 3-manifold triangulations, case is important for isomorphism signatures. |
bool regina::NGenericTriangulation< dim >::makeCanonical | ( | ) |
Relabel the top-dimensional simplices and their vertices so that this triangulation is in canonical form.
This is essentially the lexicographically smallest labelling when the facet gluings are written out in order.
Two triangulations are isomorphic if and only if their canonical forms are identical.
The lexicographic ordering assumes that the facet gluings are written in order of simplex index and then facet number. Each gluing is written as the destination simplex index followed by the gluing permutation (which in turn is written as the images of 0,1,...,dim in order).
true
if the triangulation was changed, or false
if the triangulation was in canonical form to begin with.