Regina Calculation Engine
Public Types | Public Member Functions | Protected Attributes | Friends | List of all members
regina::FacetPairing< 3 > Class Reference

Represents the dual graph of a 3-manifold triangulation. More...

#include <triangulation/facetpairing3.h>

Inheritance diagram for regina::FacetPairing< 3 >:
regina::detail::FacetPairingBase< 3 > regina::ShortOutput< FacetPairingBase< dim > > regina::Output< T, supportsUtf8 >

Public Types

typedef std::list< Isomorphism< dim > * > IsoList
 A list of isomorphisms on facet pairings. More...
 
typedef void(* Use) (const FacetPairing< dim > *, const IsoList *, void *)
 A routine that can do arbitrary processing upon a facet pairing and its automorphisms. More...
 

Public Member Functions

 FacetPairing (const FacetPairing &cloneMe)
 Creates a new face pairing that is a clone of the given face pairing. More...
 
 FacetPairing (const Triangulation< 3 > &tri)
 Creates the face pairing of the given 3-manifold triangulation. More...
 
void followChain (size_t &tet, FacePair &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...
 
void writeTextLong (std::ostream &out) const
 A default implementation for detailed output. More...
 
std::string str () const
 Returns a short text representation of this object. More...
 
std::string utf8 () const
 Returns a short text representation of this object using unicode characters. More...
 
std::string detail () const
 Returns a detailed text representation of this object. More...
 
Basic Queries
size_t size () const
 Returns the number of simplices whose facets are described by this facet pairing. More...
 
const FacetSpec< dim > & dest (const FacetSpec< dim > &source) const
 Returns the other facet to which the given simplex facet is paired. More...
 
const FacetSpec< dim > & dest (size_t simp, unsigned facet) const
 Returns the other facet to which the given simplex facet is paired. More...
 
const FacetSpec< dim > & operator[] (const FacetSpec< dim > &source) const
 Returns the other facet to which the given simplex facet is paired. More...
 
bool isUnmatched (const FacetSpec< dim > &source) const
 Determines whether the given simplex facet has been left deliberately unmatched. More...
 
bool isUnmatched (size_t 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...
 

Protected Attributes

size_t size_
 The number of simplices under consideration. More...
 
FacetSpec< dim > * pairs_
 The other facet to which each simplex facet is paired. More...
 

Friends

class detail::FacetPairingBase< 3 >
 

Input and Output

void writeTextShort (std::ostream &out) const
 Writes a human-readable representation of this facet pairing to the given output stream. 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...
 
FacetSpec< dim > & dest (const FacetSpec< dim > &source)
 Returns the other facet to which the given simplex facet is paired. More...
 
FacetSpec< dim > & dest (size_t simp, unsigned facet)
 Returns the other facet to which the given simplex facet is paired. More...
 
FacetSpec< dim > & operator[] (const FacetSpec< dim > &source)
 Returns the other facet to which the given simplex facet is paired. More...
 
bool noDest (const FacetSpec< dim > &source) const
 Determines whether the matching for the given simplex facet has not yet been determined. More...
 
bool noDest (size_t 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...
 
static FacetPairing< dim > * 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 void findAllPairings (size_t nSimplices, BoolSet boundary, int nBdryFacets, Use use, void *useArgs=0)
 Generates all possible facet pairings satisfying the given constraints. More...
 

Detailed Description

Represents the dual graph of a 3-manifold triangulation.

This is a specialisation of the generic FacetPairing class template; see the FacetPairing documentation for an overview of how this class works.

This 3-dimensional specialisation contains some extra functionality. In particular, it provides routines for finding informative subgraphs within the dual graph.

Member Typedef Documentation

◆ IsoList

typedef std::list<Isomorphism<dim>*> regina::detail::FacetPairingBase< dim >::IsoList
inherited

A list of isomorphisms on facet pairings.

Such an isomorphism can be used to convert one facet pairing into another.

This type is used to store all automorphisms of a facet pairing; that is, all isomorphisms that map the facet pairing to itself.

◆ Use

typedef void(* regina::detail::FacetPairingBase< dim >::Use) (const FacetPairing< dim > *, const IsoList *, void *)
inherited

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

Note that the first two parameters passed might be null to signal that facet pairing generation has finished.

Member Function Documentation

◆ dest() [1/4]

FacetSpec< dim > & regina::detail::FacetPairingBase< dim >::dest ( const FacetSpec< dim > &  source)
inlineprotectedinherited

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 FacetSpec<dim>::isBoundary()).

Precondition
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe facet under investigation.
Returns
the other facet to which the given facet is paired.

◆ dest() [2/4]

const FacetSpec< dim > & regina::detail::FacetPairingBase< dim >::dest ( const FacetSpec< dim > &  source) const
inlineinherited

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 FacetSpec<dim>::isBoundary()).

Precondition
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe facet under investigation.
Returns
the other facet to which the given facet is paired.

◆ dest() [3/4]

FacetSpec< dim > & regina::detail::FacetPairingBase< dim >::dest ( size_t  simp,
unsigned  facet 
)
inlineprotectedinherited

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 FacetSpec<dim>::isBoundary()).

Parameters
simpthe simplex under investigation (this must be strictly less than the total number of simplices under consideration).
facetthe facet of the given simplex under investigation (between 0 and dim inclusive).
Returns
the other facet to which the given facet is paired.

◆ dest() [4/4]

const FacetSpec< dim > & regina::detail::FacetPairingBase< dim >::dest ( size_t  simp,
unsigned  facet 
) const
inlineinherited

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 FacetSpec<dim>::isBoundary()).

Parameters
simpthe simplex under investigation (this must be strictly less than the total number of simplices under consideration).
facetthe facet of the given simplex under investigation (between 0 and dim inclusive).
Returns
the other facet to which the given facet is paired.

◆ dot()

std::string regina::detail::FacetPairingBase< dim >::dot ( const char *  prefix = 0,
bool  subgraph = false,
bool  labels = false 
) const
inherited

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.

Returns
the output of writeDot(), as outlined above.

◆ dotHeader()

static std::string regina::detail::FacetPairingBase< dim >::dotHeader ( const char *  graphName = 0)
staticinherited

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.

Returns
the output of writeDotHeader(), as outlined above.

◆ findAllPairings()

void regina::detail::FacetPairingBase< dim >::findAllPairings ( size_t  nSimplices,
BoolSet  boundary,
int  nBdryFacets,
Use  use,
void *  useArgs = 0 
)
inlinestaticinherited

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.

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

Because this class cannot represent an empty facet pairing, if the argument nSimplices is zero then no facet pairings will be generated at all.

Todo:

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.

Python
Not present, even in the dimension-specific subclasses.
Parameters
nSimplicesthe number of simplices whose facets should be (potentially) matched.
boundarydetermines 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.
nBdryFacetsspecifies 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.
usethe 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.
useArgsthe pointer to pass as the final parameter for the function use which will be called upon each pairing found.

◆ findAutomorphisms()

void regina::detail::FacetPairingBase< dim >::findAutomorphisms ( IsoList list) const
inlineinherited

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.

Precondition
The given list is empty.
This facet pairing is connected, i.e., it is possible to reach any simplex from any other simplex via a series of matched facet pairs.
This facet pairing is in canonical form as described by isCanonical().
Python
Not present, even in the dimension-specific subclasses.
Parameters
listthe list into which the newly created automorphisms will be placed.

◆ fromTextRep()

static FacetPairing<dim>* regina::detail::FacetPairingBase< dim >::fromTextRep ( const std::string &  rep)
staticinherited

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.

Precondition
The facet pairing to be reconstructed involves at least one simplex.
Parameters
repa text-based representation of a facet pairing, as produced by routine toTextRep().
Returns
the corresponding newly constructed facet pairing, or null if the given text-based representation was invalid.

◆ isCanonical()

bool regina::detail::FacetPairingBase< dim >::isCanonical ( ) const
inherited

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

Precondition
This facet pairing is connected, i.e., it is possible to reach any simplex from any other simplex via a series of matched facet pairs.
Returns
true if and only if this facet pairing is in canonical form.

◆ isCanonicalInternal()

bool regina::detail::FacetPairingBase< dim >::isCanonicalInternal ( IsoList list) const
protectedinherited

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.

Precondition
The given list is empty.
For each simplex t, the only case in which dest(t,i) is greater than dest(t,i+1) is where facets (t,i) and (t,i+1) are paired together.
For each simplex t > 0, it is true that dest(t,0).simp < t.
The sequence dest(1,0), dest(2,0), ..., dest(n-1,0) is strictly increasing, where n is the total number of simplices under investigation.
Parameters
listthe list into which automorphisms will be placed if appropriate.
Returns
true if and only if this facet pairing is in canonical form.

◆ isClosed()

bool regina::detail::FacetPairingBase< dim >::isClosed ( ) const
inherited

Determines whether this facet pairing is closed.

A closed facet pairing has no unmatched facets.

◆ isUnmatched() [1/2]

bool regina::detail::FacetPairingBase< dim >::isUnmatched ( const FacetSpec< dim > &  source) const
inlineinherited

Determines whether the given simplex facet has been left deliberately unmatched.

Precondition
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe facet under investigation.
Returns
true if the given facet has been left unmatched, or false if the given facet is paired with some other facet.

◆ isUnmatched() [2/2]

bool regina::detail::FacetPairingBase< dim >::isUnmatched ( size_t  simp,
unsigned  facet 
) const
inlineinherited

Determines whether the given simplex facet has been left deliberately unmatched.

Parameters
simpthe simplex under investigation (this must be strictly less than the total number of simplices under consideration).
facetthe facet of the given simplex under investigation (between 0 and dim inclusive).
Returns
true if the given facet has been left unmatched, or false if the given facet is paired with some other facet.

◆ noDest() [1/2]

bool regina::detail::FacetPairingBase< dim >::noDest ( const FacetSpec< dim > &  source) const
inlineprotectedinherited

Determines whether the matching for the given simplex facet has not yet been determined.

This is signalled by a facet matched to itself.

Precondition
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe facet under investigation.
Returns
true if the matching for the given facet has not yet been determined, or false otherwise.

◆ noDest() [2/2]

bool regina::detail::FacetPairingBase< dim >::noDest ( size_t  simp,
unsigned  facet 
) const
inlineprotectedinherited

Determines whether the matching for the given simplex facet has not yet been determined.

This is signalled by a facet matched to itself.

Parameters
simpthe simplex under investigation (this must be strictly less than the total number of simplices under consideration).
facetthe facet of the given simplex under investigation (between 0 and dim inclusive).
Returns
true if the matching for the given facet has not yet been determined, or false otherwise.

◆ operator[]() [1/2]

FacetSpec< dim > & regina::detail::FacetPairingBase< dim >::operator[] ( const FacetSpec< dim > &  source)
inlineprotectedinherited

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 FacetSpec<dim>&).

If the given facet is left deliberately unmatched, the value returned will be boundary (as returned by FacetSpec<dim>::isBoundary()).

Precondition
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe facet under investigation.
Returns
the other facet to which the given facet is paired.

◆ operator[]() [2/2]

const FacetSpec< dim > & regina::detail::FacetPairingBase< dim >::operator[] ( const FacetSpec< dim > &  source) const
inlineinherited

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 FacetSpec<dim>&).

If the given facet is left deliberately unmatched, the value returned will be boundary (as returned by FacetSpec<dim>::isBoundary()).

Precondition
The given facet is a real simplex facet (not boundary, before-the-start or past-the-end).
Parameters
sourcethe facet under investigation.
Returns
the other facet to which the given facet is paired.

◆ size()

size_t regina::detail::FacetPairingBase< dim >::size
inlineinherited

Returns the number of simplices whose facets are described by this facet pairing.

Returns
the number of simplices under consideration.

◆ toTextRep()

std::string regina::detail::FacetPairingBase< dim >::toTextRep ( ) const
inherited

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.

Returns
a text-based representation of this facet pairing.

◆ writeDot()

void regina::detail::FacetPairingBase< dim >::writeDot ( std::ostream &  out,
const char *  prefix = 0,
bool  subgraph = false,
bool  labels = false 
) const
inherited

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.

Python
The out argument is not present; instead standard output is assumed.
Parameters
outthe output stream to which to write.
prefixa string to prepend to the name of each graph vertex, and to include in the graph or subgraph name; see above for details.
subgraphfalse 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.
labelsindicates whether graph vertices will be labelled with the corresponding simplex numbers. This feature is currently experimental, and the default is false.
See also
http://www.graphviz.org/

◆ writeDotHeader()

static void regina::detail::FacetPairingBase< dim >::writeDotHeader ( std::ostream &  out,
const char *  graphName = 0 
)
staticinherited

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.

Python
The out argument is not present; instead standard output is assumed.
Parameters
outthe output stream to which to write.
graphNamethe name of the graph in the DOT file. If this is null or empty then a default graph name will be used.
See also
http://www.graphviz.org/

◆ writeTextLong()

void regina::ShortOutput< FacetPairingBase< dim > , false >::writeTextLong ( std::ostream &  out) const
inlineinherited

A default implementation for detailed output.

This routine simply calls T::writeTextShort() and appends a final newline.

Python
Not present.
Parameters
outthe output stream to which to write.

◆ writeTextShort()

void regina::detail::FacetPairingBase< dim >::writeTextShort ( std::ostream &  out) const
inherited

Writes a human-readable representation of this facet pairing to the given output stream.

The string returned will contain no newlines.

Python
Not present.
Parameters
outthe output stream to which to write.

Member Data Documentation

◆ pairs_

FacetSpec<dim>* regina::detail::FacetPairingBase< dim >::pairs_
protectedinherited

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 FacetSpec<dim>::isBoundary()). If the destination for a particular facet has not yet been decided, the facet will be paired to itself.

◆ size_

size_t regina::detail::FacetPairingBase< dim >::size_
protectedinherited

The number of simplices under consideration.


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

Copyright © 1999-2021, 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@maths.uq.edu.au).