Regina Calculation Engine
Classes | Public Member Functions | Protected Attributes | List of all members
regina::NGroupPresentation Class Reference

Represents a finite presentation of a group. More...

#include <algebra/ngrouppresentation.h>

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

Public Member Functions

 NGroupPresentation ()
 Creates a new presentation with no generators and no relations. More...
 
 NGroupPresentation (const NGroupPresentation &cloneMe)
 Creates a clone of the given group presentation. More...
 
virtual ~NGroupPresentation ()
 Destroys the group presentation. More...
 
NGroupPresentationoperator= (const NGroupPresentation &copyMe)
 Assignment operator. More...
 
unsigned long addGenerator (unsigned long numToAdd=1)
 Adds one or more generators to the group presentation. More...
 
void addRelation (NGroupExpression *rel)
 Adds the given relation to the group presentation. More...
 
unsigned long getNumberOfGenerators () const
 Returns the number of generators in this group presentation. More...
 
unsigned long getNumberOfRelations () const
 Returns the number of relations in this group presentation. More...
 
const NGroupExpressiongetRelation (unsigned long index) const
 Returns the relation at the given index in this group presentation. More...
 
bool intelligentSimplify ()
 Attempts to simplify the group presentation as intelligently as possible without further input. More...
 
std::auto_ptr
< NHomGroupPresentation
intelligentSimplifyDetail ()
 Attempts to simplify the group presentation as intelligently as possible without further input. More...
 
void proliferateRelators (unsigned long depth=1)
 A routine that attempts to simplify presentations, which can help when small cancellation theory can't find the simplest relators. More...
 
std::string recogniseGroup () const
 Attempts to recognise the group corresponding to this presentation. More...
 
void writeXMLData (std::ostream &out) const
 Writes a chunk of XML containing this group presentation. More...
 
unsigned long relatorLength () const
 The sum of the word lengths of the relators. More...
 
std::auto_ptr< NAbelianGroupabelianisation () const
 Computes the abelianisation of this group. More...
 
std::auto_ptr
< NMarkedAbelianGroup
markedAbelianisation () const
 Computes the abelianisation of this group. More...
 
std::string toTeX () const
 Returns a TeX representation of this group presentation. More...
 
void writeTeX (std::ostream &out) const
 Writes a TeX represesentation of this group presentation to the given output stream. More...
 
std::string toStringCompact () const
 A deprecated alias for compact(), which returns a compact one-line representation of this group presentation. More...
 
std::string compact () const
 Returns a compact one-line representation of this group presentation, including details of all generators and relations. More...
 
void writeTextCompact (std::ostream &out) const
 Writes a compact represesentation of this group to the given output stream. More...
 
virtual void writeTextShort (std::ostream &out) const
 Writes this object in short text format to the given output stream. More...
 
virtual void writeTextLong (std::ostream &out) const
 Writes this object in long text format to the given output stream. More...
 
- Public Member Functions inherited from regina::ShareableObject
 ShareableObject ()
 Default constructor that does nothing. More...
 
virtual ~ShareableObject ()
 Default destructor that does nothing. 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...
 

Protected Attributes

unsigned long nGenerators
 The number of generators. More...
 
std::vector< NGroupExpression * > relations
 The relations between the generators. More...
 

Additional Inherited Members

- Protected Member Functions inherited from regina::boost::noncopyable
 noncopyable ()
 A constructor which does nothing. More...
 
 ~noncopyable ()
 A destructor which does nothing. More...
 

Detailed Description

Represents a finite presentation of a group.

A presentation consists of a number of generators and a set of relations between these generators that together define the group.

If there are g generators, they will be numbered 0, 1, ..., g-1.

Test:
Included in the test suite.
Todo:
Implement a procedure to attempt Reidemeister-Schreir, perhaps with respect to a homomorphism to a known group. Something good-enough to detect if the group is a semi-direct product, for 2 and 3-manifold groups.

Constructor & Destructor Documentation

regina::NGroupPresentation::NGroupPresentation ( )
inline

Creates a new presentation with no generators and no relations.

regina::NGroupPresentation::NGroupPresentation ( const NGroupPresentation cloneMe)

Creates a clone of the given group presentation.

Parameters
cloneMethe presentation to clone.
regina::NGroupPresentation::~NGroupPresentation ( )
inlinevirtual

Destroys the group presentation.

All relations that are stored will be deallocated.

Member Function Documentation

std::auto_ptr<NAbelianGroup> regina::NGroupPresentation::abelianisation ( ) const

Computes the abelianisation of this group.

Returns
a newly allocated abelianisation of this group.
unsigned long regina::NGroupPresentation::addGenerator ( unsigned long  numToAdd = 1)
inline

Adds one or more generators to the group presentation.

If the new presentation has g generators, the new generators will be numbered g-1, g-2 and so on.

Parameters
numToAddthe number of generators to add.
Returns
the number of generators in the new presentation.
void regina::NGroupPresentation::addRelation ( NGroupExpression rel)
inline

Adds the given relation to the group presentation.

The relation must be of the form expression = 1.

This presentation will take ownership of the given expression, may change it and will be responsible for its deallocation.

Python:
Since this group presentation takes ownership of the given expression, the python object containing the given expression becomes a null object and should no longer be used.
Parameters
relthe expression that the relation sets to 1; for instance, if the relation is g1^2 g2 = 1 then this parameter should be the expression g1^2 g2.
std::string regina::NGroupPresentation::compact ( ) const

Returns a compact one-line representation of this group presentation, including details of all generators and relations.

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

Returns
a compact representation of this group presentation.
unsigned long regina::NGroupPresentation::getNumberOfGenerators ( ) const
inline

Returns the number of generators in this group presentation.

Returns
the number of generators.
unsigned long regina::NGroupPresentation::getNumberOfRelations ( ) const
inline

Returns the number of relations in this group presentation.

Returns
the number of relations.
const NGroupExpression & regina::NGroupPresentation::getRelation ( unsigned long  index) const
inline

Returns the relation at the given index in this group presentation.

The relation will be of the form expresson = 1.

Parameters
indexthe index of the desired relation; this must be between 0 and getNumberOfRelations()-1 inclusive.
Returns
the expression that the requested relation sets to 1; for instance, if the relation is g1^2 g2 = 1 then this will be the expression g1^2 g2.
bool regina::NGroupPresentation::intelligentSimplify ( )

Attempts to simplify the group presentation as intelligently as possible without further input.

See intelligentSimplifyDetail() for further details on how the simplification is done.

Returns
true if and only if the group presentation was changed.
std::auto_ptr<NHomGroupPresentation> regina::NGroupPresentation::intelligentSimplifyDetail ( )

Attempts to simplify the group presentation as intelligently as possible without further input.

The current simplification method is based on the Dehn algorithm for hyperbolic groups, i.e. small cancellation theory. This means we look to see if part of one relator can be used to simplify others. If so, make the substitution and simplify. We continue until no more presentation-shortening substitutions are available. We follow that by killing any available generators using words where generators appear a single time.

Todo:
Optimise (long-term): This routine could use some small tweaks – recognition of utility of some score==0 moves, such as commutators, for example.
Returns
a newly allocated homomorphism describing the reduction map from the original presentation to the new presentation, or a null pointer if this presentation was not changed.
std::auto_ptr<NMarkedAbelianGroup> regina::NGroupPresentation::markedAbelianisation ( ) const

Computes the abelianisation of this group.

The coordinates in the chain complex correspond to the generators and relators for this group.

Returns
a newly allocated abelianisation of this group.
NGroupPresentation& regina::NGroupPresentation::operator= ( const NGroupPresentation copyMe)

Assignment operator.

Parameters
copyMethe group presentation that this will become a copy of.
Returns
a reference to this group presentation.
void regina::NGroupPresentation::proliferateRelators ( unsigned long  depth = 1)

A routine that attempts to simplify presentations, which can help when small cancellation theory can't find the simplest relators.

Given a presentation <g_i | r_i>, this routine appends consequences of the relators {r_i} to the presentation that are of the form ab, where both a and b are cyclic permutations of relators from the collection {r_i}.

Passing depth=1 means it will only form products of two relators. Depth=2 means products of three, etc. Depth=4 is typically the last depth before the exponential growth of the operation grows out of hand. It also conveniently trivializes all the complicated trivial group presentations that we've come across so far.

Warning
Do not call this routine with depth n before having called it at depth n-1 first. Depth=0 is invalid, and depth=1 should be your first call to this routine. This routine gobbles up an exponential amount of memory (exponential in your presentation size times n). So do be careful when using it.
Parameters
depthcontrols the depth of the proliferation, as described above; this must be strictly positive.
std::string regina::NGroupPresentation::recogniseGroup ( ) const

Attempts to recognise the group corresponding to this presentation.

This routine is much more likely to be successful if you have already called intelligentSimplify().

Note that the presentation might be simplified a little during the execution of this routine, although not nearly as much as would be done by intelligentSimplify().

Currently, if successful the only groups this routine recognises is the trivial group, cyclic groups, free groups, and the free abelian group of rank two.

Return strings have the form "0" for the trivial group, "Z_n" for cyclic groups with n > 1, "Free(n generators)" for free groups with n>1, and "Z" and "Z + Z (abelian)" are the only two free abelian groups supported at present.

Todo:
Feature (long-term): Make this recognition more effective.
Returns
a simple string representation of the group if it is recognised, or an empty string if the group is not recognised.
unsigned long regina::NGroupPresentation::relatorLength ( ) const
inline

The sum of the word lengths of the relators.

Word lengths are computing using NGroupExpression::wordLength(). Used as a coarse measure of the complexity of the presentation.

Returns
the sum of word lengths.
std::string regina::NGroupPresentation::toStringCompact ( ) const

A deprecated alias for compact(), which returns a compact one-line representation of this group presentation.

Deprecated:
This routine has been deprecated; use the simpler-to-type compact() instead.
Returns
a compact representation of this group presentation.
std::string regina::NGroupPresentation::toTeX ( ) const

Returns a TeX representation of this group presentation.

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

Returns
a TeX representation of this group presentation.
void regina::NGroupPresentation::writeTeX ( std::ostream &  out) const

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

The output will be of the form < generators | relators >. There will be no final newline.

Python:
The parameter out does not exist; standard output will be used.
Parameters
outthe output stream to which to write.
void regina::NGroupPresentation::writeTextCompact ( std::ostream &  out) const

Writes a compact represesentation of this group to the given output stream.

The output will be of the form < generators | relators >. The full relations will be included, and the entire output will be written on a single line. There will be no final newline.

Python:
The parameter out does not exist; standard output will be used.
Parameters
outthe output stream to which to write.
virtual void regina::NGroupPresentation::writeTextLong ( std::ostream &  out) const
virtual

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 from regina::ShareableObject.

void regina::NGroupPresentation::writeTextShort ( std::ostream &  out) const
inlinevirtual

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

The output should be human-readable, should fit on a single line, and should not end with a newline.

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

Implements regina::ShareableObject.

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

Writes a chunk of XML containing this group presentation.

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

Member Data Documentation

unsigned long regina::NGroupPresentation::nGenerators
protected

The number of generators.

std::vector<NGroupExpression*> regina::NGroupPresentation::relations
protected

The relations between the generators.


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

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