Regina Calculation Engine
Public Member Functions | List of all members
regina::NGroupExpression Class Reference

Represents an expression involving generators from a group presentation or a free group. More...

#include <algebra/ngrouppresentation.h>

Inheritance diagram for regina::NGroupExpression:
regina::ShareableObject regina::boost::noncopyable

Public Member Functions

 NGroupExpression ()
 The terms that make up this expression. More...
 
 NGroupExpression (const NGroupExpression &cloneMe)
 Creates a new expression that is a clone of the given expression. More...
 
 NGroupExpression (const std::string &input, bool *valid=NULL)
 Attempts to interpret the given input string as a word in a group. More...
 
NGroupExpressionoperator= (const NGroupExpression &cloneMe)
 Makes this expression a clone of the given expression. More...
 
bool operator== (const NGroupExpression &comp) const
 Equality operator. More...
 
std::list< NGroupExpressionTerm > & getTerms ()
 Returns the list of terms in this expression. More...
 
const std::list
< NGroupExpressionTerm > & 
getTerms () const
 Returns a constant reference to the list of terms in this expression. More...
 
unsigned long getNumberOfTerms () const
 Returns the number of terms in this expression. More...
 
unsigned long wordLength () const
 Returns the length of the word, i.e. More...
 
bool isTrivial () const
 Tests whether this is the trivial (unit) word. More...
 
void erase ()
 Erases all terms from this this word. More...
 
NGroupExpressionTermgetTerm (unsigned long index)
 Returns the term at the given index in this expression. More...
 
const NGroupExpressionTermgetTerm (unsigned long index) const
 Returns a constant reference to the term at the given index in this expression. More...
 
unsigned long getGenerator (unsigned long index) const
 Returns the generator corresonding to the term at the given index in this expression. More...
 
long getExponent (unsigned long index) const
 Returns the exponent corresonding to the term at the given index in this expression. More...
 
void addTermFirst (const NGroupExpressionTerm &term)
 Adds the given term to the beginning of this expression. More...
 
void addTermFirst (unsigned long generator, long exponent)
 Adds the given term to the beginning of this expression. More...
 
void addTermLast (const NGroupExpressionTerm &term)
 Adds the given term to the end of this expression. More...
 
void addTermLast (unsigned long generator, long exponent)
 Adds the given term to the end of this expression. More...
 
void addTermsFirst (const NGroupExpression &word)
 Multiplies this expression on the left by the given word. More...
 
void addTermsLast (const NGroupExpression &word)
 Multiplies this expression on the right by the given word. More...
 
bool addStringFirst (const std::string &input)
 Multiplies this expression on the left by the word respresented by the given string. More...
 
bool addStringLast (const std::string &input)
 Multiplies this expression on the right by the word respresented by the given string. More...
 
void cycleRight ()
 Cycles this word by moving the leftmost term around to the rightmost. More...
 
void cycleLeft ()
 Cycles this word by moving the rightmost term around to the leftmost. More...
 
NGroupExpressioninverse () const
 Returns a newly created expression that is the inverse of this expression. More...
 
void invert ()
 Inverts this expression. More...
 
NGroupExpressionpower (long exponent) const
 Returns a newly created expression that is this expression raised to the given power. More...
 
bool simplify (bool cyclic=false)
 Simplifies this expression. More...
 
bool substitute (unsigned long generator, const NGroupExpression &expansion, bool cyclic=false)
 Replaces every occurrence of the given generator with the given substite expression. More...
 
std::list< std::map< unsigned
long, NGroupExpressionTerm > > 
relabellingsThisToOther (const NGroupExpression &other, bool cyclic=false) const
 Determines whether or not one can relabel the generators in this word to obtain the given other word. More...
 
void writeXMLData (std::ostream &out) const
 Writes a chunk of XML containing this expression. More...
 
std::string toTeX () const
 Returns a TeX representation of this expression. More...
 
void writeTeX (std::ostream &out) const
 Writes a TeX represesentation of this expression to the given output stream. More...
 
void writeText (std::ostream &out, bool shortword=false) const
 Writes a text representation of this expression to the given output stream, using either numbered generators or alphabetic generators. More...
 
virtual void writeTextShort (std::ostream &out) const
 The text representation will be of the form g2^4 g13^-5 g4. More...
 
Input and Output
virtual void writeTextLong (std::ostream &out) const
 Writes this object in long text format to the given output stream. More...
 
std::string str () const
 Returns the output from writeTextShort() as a string. More...
 
std::string toString () const
 A deprecated alias for str(), which returns the output from writeTextShort() as a string. More...
 
std::string detail () const
 Returns the output from writeTextLong() as a string. More...
 
std::string toStringLong () const
 A deprecated alias for detail(), which returns the output from writeTextLong() as a string. More...
 

Detailed Description

Represents an expression involving generators from a group presentation or a free group.

An expression is represented as word, i.e, a sequence of powers of generators all of which are multiplied in order. Each power of a generator corresponds to an individual NGroupExpressionTerm.

For instance, the expression g1^2 g3^-1 g6 contains the three terms g1^2, g3^-1 and g6^1 in that order.

Constructor & Destructor Documentation

regina::NGroupExpression::NGroupExpression ( )
inline

The terms that make up this expression.

Creates a new expression with no terms.

regina::NGroupExpression::NGroupExpression ( const NGroupExpression cloneMe)
inline

Creates a new expression that is a clone of the given expression.

Parameters
cloneMethe expression to clone.
regina::NGroupExpression::NGroupExpression ( const std::string &  input,
bool *  valid = NULL 
)

Attempts to interpret the given input string as a word in a group.

Regina can recognise strings in the following four basic forms:

  • a^7b^-2
  • aaaaaaaBB
  • a^7B^2
  • g0^7g1^-2

The string may contain whitespace, which will simply be ignored.

The argument valid may be null, but if it is non-null then the boolean it points to will be used for error reporting. This routine sets valid to true if the string was successfully interpreted, or false if the algorithm failed to interpret the string.

Regardless of whether valid is null, if the string could not be interpreted then this expression will be initialised to the trivial word.

Python:
The second argument valid is not present, and will be assumed to be null.
Parameters
inputthe input string that is to be interpreted.
validused for error reporting as described above, or null if no error reporting is required.

Member Function Documentation

bool regina::NGroupExpression::addStringFirst ( const std::string &  input)

Multiplies this expression on the left by the word respresented by the given string.

See the string-based constructor NGroupExpression(const std::string&, bool*) for further information on how this string should be formatted.

If the given string cannot be interpreted as a word in a group, then this expression will be left untouched.

Parameters
inputa string representation of the word to multiply with this expression.
Returns
true if the given string could interpreted (and therefore the multiplication was completed successfully), or false if the given string could not be interpreted (in which case this expression will be left untouched).
bool regina::NGroupExpression::addStringLast ( const std::string &  input)

Multiplies this expression on the right by the word respresented by the given string.

See the string-based constructor NGroupExpression(const std::string&, bool*) for further information on how this string should be formatted.

If the given string cannot be interpreted as a word in a group, then this expression will be left untouched.

Parameters
inputa string representation of the word to multiply with this expression.
Returns
true if the given string could interpreted (and therefore the multiplication was completed successfully), or false if the given string could not be interpreted (in which case this expression will be left untouched).
void regina::NGroupExpression::addTermFirst ( const NGroupExpressionTerm term)
inline

Adds the given term to the beginning of this expression.

Parameters
termthe term to add.
void regina::NGroupExpression::addTermFirst ( unsigned long  generator,
long  exponent 
)
inline

Adds the given term to the beginning of this expression.

Parameters
generatorthe number of the generator corresponding to the new term.
exponentthe exponent to which the given generator is raised.
void regina::NGroupExpression::addTermLast ( const NGroupExpressionTerm term)
inline

Adds the given term to the end of this expression.

Parameters
termthe term to add.
void regina::NGroupExpression::addTermLast ( unsigned long  generator,
long  exponent 
)
inline

Adds the given term to the end of this expression.

Parameters
generatorthe number of the generator corresponding to the new term.
exponentthe exponent to which the given generator is raised.
void regina::NGroupExpression::addTermsFirst ( const NGroupExpression word)

Multiplies this expression on the left by the given word.

This expression will be modified directly.

Parameters
wordthe word to multiply with this expression.
void regina::NGroupExpression::addTermsLast ( const NGroupExpression word)

Multiplies this expression on the right by the given word.

This expression will be modified directly.

Parameters
wordthe word to multiply with this expression.
void regina::NGroupExpression::cycleLeft ( )

Cycles this word by moving the rightmost term around to the leftmost.

All other terms shift one step to the right.

If the word is of the form g_i1^j1 g_i2^j2 ... g_in^jn, this converts it into the word g_in^jn g_i1^j1 g_i1^j1 ... g_in-1^jn-1.

void regina::NGroupExpression::cycleRight ( )

Cycles this word by moving the leftmost term around to the rightmost.

All other terms shift one step to the left.

If the word is of the form g_i1^j1 g_i2^j2 ... g_in^jn, this converts it into the word g_i2^j2 ... g_in^jn g_i1^j1.

std::string regina::ShareableObject::detail ( ) const
inherited

Returns the output from writeTextLong() as a string.

Returns
a long text representation of this object.
void regina::NGroupExpression::erase ( )
inline

Erases all terms from this this word.

This effectively turns this word into the identity element.

long regina::NGroupExpression::getExponent ( unsigned long  index) const
inline

Returns the exponent corresonding to the term at the given index in this expression.

Index 0 represents the first term, index 1 represents the second term and so on.

Warning
This routine is O(n) where n is the number of terms in this expression.
Parameters
indexthe index of the term to return; this must be between 0 and getNumberOfTerms()-1 inclusive.
Returns
the requested exponent.
unsigned long regina::NGroupExpression::getGenerator ( unsigned long  index) const
inline

Returns the generator corresonding to the term at the given index in this expression.

Index 0 represents the first term, index 1 represents the second term and so on.

Warning
This routine is O(n) where n is the number of terms in this expression.
Parameters
indexthe index of the term to return; this must be between 0 and getNumberOfTerms()-1 inclusive.
Returns
the number of the requested generator.
unsigned long regina::NGroupExpression::getNumberOfTerms ( ) const
inline

Returns the number of terms in this expression.

For instance, the expression g1^2 g3^-1 g6 contains three terms. See also getWordLength().

Returns
the number of terms.
NGroupExpressionTerm& regina::NGroupExpression::getTerm ( unsigned long  index)

Returns the term at the given index in this expression.

Index 0 represents the first term, index 1 represents the second term and so on.

Warning
This routine is O(n) where n is the number of terms in this expression.
Parameters
indexthe index of the term to return; this must be between 0 and getNumberOfTerms()-1 inclusive.
Returns
the requested term.
const NGroupExpressionTerm& regina::NGroupExpression::getTerm ( unsigned long  index) const

Returns a constant reference to the term at the given index in this expression.

Index 0 represents the first term, index 1 represents the second term and so on.

Warning
This routine is O(n) where n is the number of terms in this expression.
Python:
Not present; only the non-const version of this routine is available.
Parameters
indexthe index of the term to return; this must be between 0 and getNumberOfTerms()-1 inclusive.
Returns
the requested term.
std::list< NGroupExpressionTerm > & regina::NGroupExpression::getTerms ( )
inline

Returns the list of terms in this expression.

These are the actual terms stored internally; any modifications made to this list will show up in the expression itself.

For instance, the expression g1^2 g3^-1 g6 has list consisting of three terms g1^2, g3^-1 and g6^1 in that order.

Python:
Not present; only the const version of this routine is available.
Returns
the list of terms.
const std::list< NGroupExpressionTerm > & regina::NGroupExpression::getTerms ( ) const
inline

Returns a constant reference to the list of terms in this expression.

For instance, the expression g1^2 g3^-1 g6 has list consisting of three terms g1^2, g3^-1 and g6^1 in that order.

Python:
This routine returns a python list of copied NGroupExpressionTerm objects. In particular, modifying this list or the terms within it will not modify the group expression from which they came.
Returns
the list of terms.
NGroupExpression* regina::NGroupExpression::inverse ( ) const

Returns a newly created expression that is the inverse of this expression.

The terms will be reversed and the exponents negated.

Returns
the inverse of this expression.
void regina::NGroupExpression::invert ( )

Inverts this expression.

Does not allocate or deallocate anything.

bool regina::NGroupExpression::isTrivial ( ) const
inline

Tests whether this is the trivial (unit) word.

No attempt is made to remove redundant terms (so the word g g^-1 will be treated as non-trivial).

Returns
true if and only if this is the trivial word.
NGroupExpression & regina::NGroupExpression::operator= ( const NGroupExpression cloneMe)
inline

Makes this expression a clone of the given expression.

Parameters
cloneMethe expression to clone.
Returns
a reference to this expression.
bool regina::NGroupExpression::operator== ( const NGroupExpression comp) const
inline

Equality operator.

Checks to see whether or not these two words represent the same literal string.

Parameters
compthe expression to compare against this.
Returns
true if this and the given string literal are identical.
NGroupExpression* regina::NGroupExpression::power ( long  exponent) const

Returns a newly created expression that is this expression raised to the given power.

Note that the given exponent may be positive, zero or negative.

Parameters
exponentthe power to which this expression should be raised.
Returns
this expression raised to the given power.
std::list< std::map< unsigned long, NGroupExpressionTerm > > regina::NGroupExpression::relabellingsThisToOther ( const NGroupExpression other,
bool  cyclic = false 
) const

Determines whether or not one can relabel the generators in this word to obtain the given other word.

If so, returns a non-empty list of all such relabellings. If not, returns an empty list.

Relabellings are partially-defined permutations on the generator set, also allowing for possible inversions if cyclic is true.

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.
Todo:
Change this to use less heavyweight types and less deep copying.
Precondition
If cyclic is true, then both this word and other have been cyclically reduced.
Python:
Not present.
Parameters
otherthe word to compare against this.
cyclicif false we get a list of exact relabellings from this word to other. If true, it can be up to cyclic permutation and inversion.
Returns
a list of permutations, implemented as maps from generator indices of this word to generator indices of other.
bool regina::NGroupExpression::simplify ( bool  cyclic = false)

Simplifies this expression.

Adjacent powers of the same generator will be combined, and terms with an exponent of zero will be removed. Note that it is not assumed that the underlying group is abelian.

You may declare that the expression is cyclic, in which case it is assumed that terms may be moved from the back to the front and vice versa. Thus expression g1 g2 g1 g2 g1 simplifies to g1^2 g2 g1 g2 if it is cyclic, but does not simplify at all if it is not cyclic.

Parameters
cyclictrue if and only if the expression may be assumed to be cyclic.
Returns
true if and only if this expression was changed.
std::string regina::ShareableObject::str ( ) const
inherited

Returns the output from writeTextShort() as a string.

Python:
This implements the __str__() function.
Returns
a short text representation of this object.
bool regina::NGroupExpression::substitute ( unsigned long  generator,
const NGroupExpression expansion,
bool  cyclic = false 
)

Replaces every occurrence of the given generator with the given substite expression.

If the given generator was found, the expression will be simplified once the substitution is complete.

Parameters
generatorthe generator to be replaced.
expansionthe substitute expression that will replace every occurrence of the given generator.
cyclictrue if and only if the expression may be assumed to be cyclic; see simplify() for further details.
Returns
true if and only if any substitutions were made.
std::string regina::ShareableObject::toString ( ) const
inlineinherited

A deprecated alias for str(), which returns the output from writeTextShort() as a string.

Deprecated:
This routine has (at long last) been deprecated; use the simpler-to-type str() instead.
Returns
a short text representation of this object.
std::string regina::ShareableObject::toStringLong ( ) const
inlineinherited

A deprecated alias for detail(), which returns the output from writeTextLong() as a string.

Deprecated:
This routine has (at long last) been deprecated; use the simpler-to-type detail() instead.
Returns
a long text representation of this object.
std::string regina::NGroupExpression::toTeX ( ) const

Returns a TeX representation of this expression.

See writeTeX() for details on how this is formed.

Returns
a TeX representation of this expression.
unsigned long regina::NGroupExpression::wordLength ( ) const
inline

Returns the length of the word, i.e.

the number of letters with exponent +1 or -1 for which this word is expressable as a product.

For instance, the expression g1^2 g3^-1 g6 is a word of length four. See also getNumberOfTerms().

No attempt is made to remove redundant terms (so the word g g^-1 will count as length two).

Returns
the length of the word.
void regina::NGroupExpression::writeTeX ( std::ostream &  out) const

Writes a TeX represesentation of this expression to the given output stream.

The text representation will be of the form g_2^4 g_{13}^{-5} g_4.

Python:
The parameter out does not exist; standard output will be used.
Parameters
outthe output stream to which to write.
void regina::NGroupExpression::writeText ( std::ostream &  out,
bool  shortword = false 
) const

Writes a text representation of this expression to the given output stream, using either numbered generators or alphabetic generators.

The text representation will be of the form g2^4 g13^-5 g4. If the shortword flag is true, it will assume your word is in an alphabet of no more than 26 letters, and will write the word using lower-case ASCII, i.e. c^4 n^-5 e.

Precondition
If shortword is true, the number of generators in the corresponding group must be 26 or fewer.
Python:
The parameter out does not exist; standard output will be used.
Parameters
outthe output stream to which to write.
shortwordindicates whether to use numbered or alphabetic generators, as described above.
void regina::ShareableObject::writeTextLong ( std::ostream &  out) const
inlinevirtualinherited

Writes this object in long text format to the given output stream.

The output should provide the user with all the information they could want. The output should be human-readable, should not contain extremely long lines (so users can read the output in a terminal), and should end with a final newline.

The default implementation of this routine merely calls writeTextShort() and adds a newline.

Python:
The parameter out does not exist; standard output will be used.
Parameters
outthe output stream to which to write.

Reimplemented in regina::NSnapPeaTriangulation, regina::NGroupPresentation, regina::NHomMarkedAbelianGroup, regina::NNormalSurfaceList, regina::NTetrahedron, regina::NSatRegion, regina::NVertex, regina::NEdge, regina::Dim2Triangle, regina::NTriangle, regina::NLayeredSolidTorus, regina::NHomGroupPresentation, regina::NGenericIsomorphism< dim >, regina::NGenericIsomorphism< 2 >, regina::NGenericIsomorphism< 3 >, regina::NTriangulation, regina::NComponent, regina::NTxICore, regina::NTriSolidTorus, regina::NAngleStructureList, regina::Dim2Edge, regina::NBoundaryComponent, regina::NLayeredChain, regina::Dim2Vertex, regina::Dim2Component, regina::NScript, regina::NAugTriSolidTorus, regina::NSpiralSolidTorus, regina::NSurfaceFilterProperties, regina::NLayeredTorusBundle, regina::NManifold, regina::NPlugTriSolidTorus, regina::NMatrixInt, regina::NBlockedSFSTriple, regina::NPluggedTorusBundle, regina::Dim2Triangulation, regina::NSurfaceSubset, regina::NLayeredLensSpace, regina::NLayeredLoop, regina::NFileInfo, regina::NBlockedSFSLoop, regina::NSnappedBall, regina::NBlockedSFSPair, regina::Dim2BoundaryComponent, regina::NTrivialTri, regina::NL31Pillow, regina::NLayeredChainPair, regina::NText, regina::NSurfaceFilterCombination, and regina::NBlockedSFS.

virtual void regina::NGroupExpression::writeTextShort ( std::ostream &  out) const
virtual

The text representation will be of the form g2^4 g13^-5 g4.

Implements regina::ShareableObject.

void regina::NGroupExpression::writeXMLData ( std::ostream &  out) const

Writes a chunk of XML containing this expression.

Python:
Not present.
Parameters
outthe output stream to which the XML should be written.

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