Regina Calculation Engine
|
A dimension-agnostic base class that represents a pairwise matching of facets of dim-dimensional simplices. More...
#include <census/ngenericfacetpairing.h>
Public Types | |
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... | |
Public Member Functions | |
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... | |
Constructors and Destructors | |
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... | |
Basic Queries | |
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... | |
Isomorphic Representations | |
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... | |
Input and Output | |
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... | |
Internal Routines | |
void * | run (void *param) |
Internal to findAllPairings(). More... | |
Static Public Member Functions | |
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 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 | |
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 | |
unsigned | size_ |
The number of simplices under consideration. More... | |
NFacetSpec< dim > * | pairs_ |
The other facet to which each simplex facet is paired. More... | |
A dimension-agnostic base class that represents a pairwise matching of facets of dim-dimensional simplices.
Each dimension that Regina works with (2 and 3) offers its own subclass with richer functionality; users typically do not need to work with this template base class directly.
Given a fixed number of dim-dimensional simplices, each facet of each simplex is either paired with some other simplex facet (which is in turn paired with it) or remains unmatched. A simplex facet cannot be paired with itself.
Such a matching models part of the structure of a dim-manifold triangulation, in which each simplex facet is either glued to some other simplex facet (which is in turn glued to it) or is an unglued boundary facet.
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.
typedef DimTraits<dim>::FacetPairing regina::NGenericFacetPairing< dim >::FacetPairing |
The facet pairing class specific to this dimension.
This is typically a subclass of NGenericFacetPairing<dim>.
typedef std::list<Isomorphism*> regina::NGenericFacetPairing< dim >::IsoList |
A list of isomorphisms on pairwise matchings of simplex facets.
Specifically, such an isomorphism can be used to convert one pairwise matching of simplex facets (as described by class NGenericFacetPairing) into another.
typedef DimTraits<dim>::Isomorphism regina::NGenericFacetPairing< dim >::Isomorphism |
The isomorphism class used for triangulations in this dimension.
typedef DimTraits<dim>::Perm regina::NGenericFacetPairing< dim >::Perm |
The permutation class used to glue together facets of simplices when building triangulations in this dimension.
typedef DimTraits<dim>::Simplex regina::NGenericFacetPairing< dim >::Simplex |
The class that represents a top-level simplex of a triangulation in this dimension.
typedef DimTraits<dim>::Triangulation regina::NGenericFacetPairing< dim >::Triangulation |
The triangulation class specific to this dimension.
typedef void(* regina::NGenericFacetPairing< dim >::Use)(const FacetPairing *, const IsoList *, void *) |
A routine that can do arbitrary processing upon a facet pairing and its automorphisms.
Such routines are used to process pairings that are found when running findAllPairings().
The first parameter passed should be a facet pairing (this should not be deallocated by this routine). The second parameter should be a list of all automorphisms of this pairing (this should not be deallocated either). The third parameter may contain arbitrary data as passed to findAllPairings().
It may be assumed that the pairing is of the appropriate dimension-specific subclass (such as NFacePairing for dimension three, or Dim2EdgePairing for dimension two).
Note that the first two parameters passed might be null
to signal that facet pairing generation has finished.
regina::NGenericFacetPairing< dim >::NGenericFacetPairing | ( | const NGenericFacetPairing< dim > & | cloneMe | ) |
Creates a new facet pairing that is a clone of the given facet pairing.
cloneMe | the facet pairing to clone. |
regina::NGenericFacetPairing< dim >::NGenericFacetPairing | ( | const Triangulation & | tri | ) |
Creates the facet pairing of given triangulation.
This is the facet pairing that describes how the facets of simplices in the given triangulation are joined together, as described in the class notes.
tri | the triangulation whose facet pairing should be constructed. |
|
inlinevirtual |
Deallocates any memory used by this structure.
|
inlineprotected |
Creates a new facet pairing.
All internal arrays will be allocated but not initialised.
size | the number of simplices under consideration in this new facet pairing. |
|
inline |
Returns the other facet to which the given simplex facet is paired.
If the given facet is left deliberately unmatched, the value returned will be boundary (as returned by NFacetSpec<dim>::isBoundary()).
source | the facet under investigation. |
|
inline |
Returns the other facet to which the given simplex facet is paired.
If the given facet is left deliberately unmatched, the value returned will be boundary (as returned by NFacetSpec<dim>::isBoundary()).
simp | the simplex under investigation (this must be strictly less than the total number of simplices under consideration). |
facet | the facet of the given simplex under investigation (between 0 and dim inclusive). |
|
inlineprotected |
Returns the other facet to which the given simplex facet is paired.
If the given facet is left deliberately unmatched, the value returned will be boundary (as returned by NFacetSpec<dim>::isBoundary()).
source | the facet under investigation. |
|
inlineprotected |
Returns the other facet to which the given simplex facet is paired.
If the given facet is left deliberately unmatched, the value returned will be boundary (as returned by NFacetSpec<dim>::isBoundary()).
simp | the simplex under investigation (this must be strictly less than the total number of simplices under consideration). |
facet | the facet of the given simplex under investigation (between 0 and dim inclusive). |
std::string regina::NGenericFacetPairing< dim >::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.
This routine simply returns the output of writeDot() as a string, instead of dumping it to an output stream.
All arguments are the same as for writeDot(); see the writeDot() notes for further details.
|
static |
Returns header information for a Graphviz DOT file that will describe the graphs for one or more facet pairings.
This routine simply returns the output of writeDotHeader() as a string, instead of dumping it to an output stream.
All arguments are the same as for writeDotHeader(); see the writeDotHeader() notes for further details.
|
static |
Generates all possible facet pairings satisfying the given constraints.
Only connected facet pairings (pairings in which each simplex can be reached from each other via a series of individual matched facets) will be produced.
Each facet pairing will be produced precisely once up to isomorphism. Facet pairings are considered isomorphic if they are related by a relabelling of the simplices and/or a renumbering of the (dim + 1) facets of each simplex. Each facet pairing that is generated will be a lexicographically minimal representative of its isomorphism class, i.e., will be in canonical form as described by isCanonical().
For each facet pairing that is generated, routine use (as passed to this function) will be called with that pairing and its automorphisms as arguments. Each pairing will be of the appropriate dimension-specific subclass (for instance, NFacePairing for dimension three, or Dim2EdgePairing for dimension two).
Once the generation of facet pairings has finished, routine use will be called once more, this time with null
as its first two arguments (for the facet pairing and its automorphisms).
The facet pairing generation may be run in the current thread or as a separate thread.
Because this class cannot represent an empty facet pairing, if the argument nSimplices is zero then no facet pairings will be generated at all.
Optimise (long-term): When generating facet pairings, do some checking to eliminate cases in which simplex (k > 0) can be swapped with simplex 0 to produce a smaller representation of the same pairing.
Feature: Allow cancellation of facet pairing generation.
nSimplices | the number of simplices whose facets should be (potentially) matched. |
boundary | determines whether any facets may be left unmatched. This set should contain true if pairings with at least one unmatched facet are to be generated, and should contain false if pairings with no unmatched facets are to be generated. |
nBdryFacets | specifies the precise number of facets 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 facets will be generated. In particular, if this parameter is positive then pairings with no unmatched facets 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 of the same parity as nSimplices * (dim+1) , and can be at most (dim-1) * nSimplices + 2 . |
use | the function to call upon each facet pairing that is found. The first parameter passed to this function will be a facet pairing. The second parameter will be a list of all its automorphisms (relabellings of simplices and individual simplex facets 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 facet 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 facet pairing generation has taken place in the current thread), or false
if the new thread could not be started.
|
inline |
Fills the given list with the set of all combinatorial automorphisms of this facet pairing.
An automorphism is a relabelling of the simplices and/or a renumbering of the (dim + 1) facets of each simplex resulting in precisely the same facet pairing.
This routine uses optimisations that can cause unpredictable breakages if this facet 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.
list | the list into which the newly created automorphisms will be placed. |
|
static |
Reconstructs a facet pairing from a text-based representation.
This text-based representation must be in the format produced by routine toTextRep().
The facet 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 facet pairing, as produced by routine toTextRep(). |
null
if the given text-based representation was invalid. bool regina::NGenericFacetPairing< dim >::isCanonical | ( | ) | const |
Determines whether this facet pairing is in canonical form, i.e., is a lexicographically minimal representative of its isomorphism class.
Isomorphisms of facet pairings correspond to relabellings of simplices and relabellings of the (dim + 1) facets within each simplex.
Facet pairings are ordered by lexicographical comparison of dest(0,0)
, dest(0,1)
, ..., dest(size()-1,dim)
.
true
if and only if this facet pairing is in canonical form.
|
protected |
Determines whether this facet pairing is in canonical (smallest lexicographical) form, given a small set of assumptions.
If this facet pairing is in canonical form, the given list will be filled with the set of all combinatorial automorphisms of this facet pairing. If not, the given list will be left empty.
dest(t,i)
is greater than dest(t,i+1)
is where facets (t,i)
and (t,i+1)
are paired together. dest(t,0).simp < t
. dest(1,0)
, dest(2,0)
, ..., dest(n-1,0)
is strictly increasing, where n is the total number of simplices under investigation.list | the list into which automorphisms will be placed if appropriate. |
true
if and only if this facet pairing is in canonical form. bool regina::NGenericFacetPairing< dim >::isClosed | ( | ) | const |
Determines whether this facet pairing is closed.
A closed facet pairing has no unmatched facets.
|
inline |
Determines whether the given simplex facet has been left deliberately unmatched.
source | the facet under investigation. |
true
if the given facet has been left unmatched, or false
if the given facet is paired with some other facet.
|
inline |
Determines whether the given simplex facet has been left deliberately unmatched.
simp | the simplex under investigation (this must be strictly less than the total number of simplices under consideration). |
facet | the facet of the given simplex under investigation (between 0 and dim inclusive). |
true
if the given facet has been left unmatched, or false
if the given facet is paired with some other facet.
|
inlineinherited |
Waits for a previously-started thread to terminate.
Once this function returns, it is guaranteed that the thread is no longer running.
false
(the default).
|
inlineprotected |
Determines whether the matching for the given simplex facet has not yet been determined.
This is signalled by a facet matched to itself.
source | the facet under investigation. |
true
if the matching for the given facet has not yet been determined, or false
otherwise.
|
inlineprotected |
Determines whether the matching for the given simplex facet has not yet been determined.
This is signalled by a facet matched to itself.
simp | the simplex under investigation (this must be strictly less than the total number of simplices under consideration). |
facet | the facet of the given simplex under investigation (between 0 and dim inclusive). |
true
if the matching for the given facet has not yet been determined, or false
otherwise.
|
inline |
Returns the other facet to which the given simplex facet is paired.
This is a convenience operator whose behaviour is identical to that of dest(const NFacetSpec<dim>&).
If the given facet is left deliberately unmatched, the value returned will be boundary (as returned by NFacetSpec<dim>::isBoundary()).
source | the facet under investigation. |
|
inlineprotected |
Returns the other facet to which the given simplex facet is paired.
This is a convenience operator whose behaviour is identical to that of dest(const NFacetSpec<dim>&).
If the given facet is left deliberately unmatched, the value returned will be boundary (as returned by NFacetSpec<dim>::isBoundary()).
source | the facet under investigation. |
|
virtual |
Internal to findAllPairings().
This routine should never be called directly.
Performs the actual generation of facet pairings, possibly as a separate thread. At most one copy of this routine should be running at any given time for a particular NGenericFacetPairing instance.
param | a structure containing the parameters that were passed to findAllPairings(). |
Implements regina::NThread.
|
inline |
Returns the number of simplices whose facets are described by this facet pairing.
|
inherited |
Starts a new thread and performs run() within this new thread.
The return value of run() is ignored.
true
, you must not attempt to access this thread object again (since it could be deleted at any time). In particular, you will not be able to call join() to wait for the new thread to terminate.args | the arguments to pass to run() when it is started. |
deleteAfterwards | true if this NThread object should be deleted once run() has finished. |
true
if and only if the new thread was successfully started.
|
staticinherited |
Starts a new thread that performs the given routine.
The return value of the given routine is currently ignored.
routine | the routine to run in the new thread. |
args | the arguments to pass to routine when it is started. |
id | a location in which the ID of the new thread will be placed, or 0 if the new thread ID is not required. If non-zero, this parameter must point to an already extisting NThreadID that may contain any value. |
true
if and only if the new thread was successfully started. std::string regina::NGenericFacetPairing< dim >::str | ( | ) | const |
Returns a human-readable representation of this facet pairing.
The string returned will contain no newlines.
__str__()
function.
|
inline |
A deprecated alias for str(), which returns a human-readable representation of this facet pairing.
std::string regina::NGenericFacetPairing< dim >::toTextRep | ( | ) | const |
Returns a text-based representation of this facet pairing that can be used to reconstruct the facet pairing.
This reconstruction is done through routine fromTextRep().
The text produced is not particularly readable; for a human-readable text representation, see routine str() instead.
The string returned will contain no newlines.
void regina::NGenericFacetPairing< dim >::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.
Every vertex of this graph represents a simplex, and every edge represents a pair of simplex facets that are joined together. Note that for a closed triangulation this graph will be entirely (dim + 1)-valent; for triangulations with boundary facets, some graph vertices will have degree dim 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 pairing_
.
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. |
labels | indicates whether graph vertices will be labelled with the corresponding simplex numbers. This feature is currently experimental, and the default is false . |
|
static |
Writes header information for a Graphviz DOT file that will describe the graphs for one or more facet 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 facet pairings. A complete DOT file can be produced by calling this routine, then calling writeDot() in subgraph mode for each facet pairing, then outputting a final closing curly brace.
Note that if you require a DOT file containing the graph for only a single facet 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. |
|
inlinestaticinherited |
Causes the currently running thread to voluntarily relinquish the processor.
Another thread of equal or higher priority will be given a turn instead.
|
protected |
The other facet to which each simplex facet is paired.
If a simplex facet is left unmatched, the corresponding element of this array will be boundary (as returned by NFacetSpec<dim>::isBoundary()). If the destination for a particular facet has not yet been decided, the facet will be paired to itself.
|
protected |
The number of simplices under consideration.