Regina Calculation Engine
Public Types | List of all members
regina::NGenericTriangulation< dim > Class Template Reference

A generic helper class for working with triangulations of arbitrary dimension. More...

#include <generic/ngenerictriangulation.h>

Inheritance diagram for regina::NGenericTriangulation< dim >:
regina::DimTraits< dim >

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

Detailed Description

template<int dim>
class regina::NGenericTriangulation< dim >

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

Warning
The API for this class has not yet been finalised. This means that the class interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please watch the detailed changelogs upon new releases to see if you need to make changes to your code.
Python:
Not present.
Precondition
The template argument dim must be one of the dimensions that Regina supports.

Member Function Documentation

template<int dim>
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.

Python:
Not present.
Parameters
otherthe triangulation to compare with this one.
resultsthe list in which any isomorphisms found will be stored.
Returns
the number of isomorphisms that were found.
template<int dim>
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.

Python:
Not present.
Parameters
otherthe triangulation in which to search for isomorphic copies of this triangulation.
resultsthe list in which any isomorphisms found will be stored.
Returns
the number of isomorphisms that were found.
template<int dim>
static DimTraits<dim>::Triangulation* regina::NGenericTriangulation< dim >::fromIsoSig ( const std::string &  sig)
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.

Warning
Do not mix isomorphism signatures between dimensions! It is possible that the same string could corresponding to both a p-dimensional triangulation and a q-dimensional triangulation for different p and q.
Parameters
sigthe isomorphism signature of the triangulation to construct. Note that, unlike dehydration strings for 3-manifold triangulations, case is important for isomorphism signatures.
Returns
a newly allocated triangulation if the reconstruction was successful, or null if the given string was not a valid isomorphism signature.
template<int dim>
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().

Parameters
otherthe triangulation in which to search for an isomorphic copy of this triangulation.
Returns
details of the isomorphism if such a copy is found, or a null pointer otherwise.
template<int dim>
bool regina::NGenericTriangulation< dim >::isEmpty ( ) const
inline

Determines whether this triangulation is empty.

An empty triangulation is one with no simplices at all.

Returns
true if and only if this triangulation is empty.
template<int dim>
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.

Parameters
otherthe triangulation to compare with this one.
Returns
true if and only if the two triangulations are combinatorially identical.
template<int dim>
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().

Todo:
Optimise: Improve the complexity by choosing a simplex mapping from each component and following gluings to determine the others.
Parameters
otherthe triangulation to compare with this one.
Returns
details of the isomorphism if the two triangulations are combinatorially isomorphic, or a null pointer otherwise.
template<int dim>
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.

Python:
The isomorphism argument is not present. Instead there are two routines: fromIsoSig(), which returns a string only, and fromIsoSigDetail(), which returns a pair (signature, relabelling).
Precondition
If relabelling is non-null, then this triangulation must be non-empty and connected. The facility to return a relabelling for disconnected triangulations may be added to Regina in a later release.
Warning
Do not mix isomorphism signatures between dimensions! It is possible that the same string could corresponding to both a p-dimensional triangulation and a q-dimensional triangulation for different p and q.
Parameters
relabellingif 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.
Returns
the isomorphism signature of this triangulation.
template<int dim>
static size_t regina::NGenericTriangulation< dim >::isoSigComponentSize ( const std::string &  sig)
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.

Warning
Do not mix isomorphism signatures between dimensions! It is possible that the same string could corresponding to both a p-dimensional triangulation and a q-dimensional triangulation for different p and q.
Parameters
sigan isomorphism signature of a dim-dimensional triangulation. Note that, unlike dehydration strings for 3-manifold triangulations, case is important for isomorphism signatures.
Returns
the number of top-dimensional simplices in the first connected component, or 0 if this could not be determined because the given string was not a valid isomorphism signature.
template<int dim>
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).

Precondition
This routine currently works only when the triangulation is connected. It may be extended to work with disconnected triangulations in later versions of Regina.
Returns
true if the triangulation was changed, or false if the triangulation was in canonical form to begin with.

The documentation for this class was generated from the following file:

Copyright © 1999-2014, 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).