Common member functions

This page contains documentation of the member functions of ToddCoxeter that are implemented in all of the classes Congruence, Kambites, KnuthBendix, and ToddCoxeter.

Functions
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
ToddCoxeter &	add_generating_pair (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Add generating pair via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
ToddCoxeter &	add_generating_pair_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Add generating pair via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
bool	contains (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Check containment of a pair of words via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
bool	contains_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Check containment of a pair of words via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
tril	currently_contains (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
	Check containment of a pair of words via iterators.
template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
tril	currently_contains_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
	Check containment of a pair of words via iterators.
std::vector< Word > const &	generating_pairs () const noexcept
	Get the generating pairs of the congruence.
congruence_kind	kind () const noexcept
	The kind of the congruence (1- or 2-sided).
uint64_t	number_of_classes ()
	Compute the number of classes in the congruence.
size_t	number_of_generating_pairs () const noexcept
	Returns the number of generating pairs.
Presentation< Word > const &	presentation () const noexcept
	Get the presentation used to define a ToddCoxeter instance (if any).
template<typename OutputIterator, typename InputIterator1, typename InputIterator2>
OutputIterator	reduce (OutputIterator d_first, InputIterator1 first, InputIterator2 last)
	Reduce a word.
template<typename OutputIterator, typename InputIterator1, typename InputIterator2>
OutputIterator	reduce_no_checks (OutputIterator d_first, InputIterator1 first, InputIterator2 last)
	Reduce a word with no checks.
template<typename OutputIterator, typename InputIterator1, typename InputIterator2>
OutputIterator	reduce_no_run (OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
	Reduce a word with no enumeration.
template<typename OutputIterator, typename InputIterator1, typename InputIterator2>
OutputIterator	reduce_no_run_no_checks (OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
	Reduce a word with no enumeration or checks.

Function Documentation

add_generating_pair()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

ToddCoxeter & add_generating_pair ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 )

inline

This function adds a generating pair to the congruence represented by a ToddCoxeter instance.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

A reference to *this.

Exceptions

LibsemigroupsException	if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.
LibsemigroupsException	if started returns true.

add_generating_pair_no_checks()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

ToddCoxeter & add_generating_pair_no_checks	(	Iterator1	first1,
		Iterator2	last1,
		Iterator3	first2,
		Iterator4	last2 )

This function adds a generating pair to the congruence represented by a ToddCoxeter instance.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

A reference to *this.

Warning

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().

It is assumed that started returns false. Adding generating pairs after started is not permitted (but also not checked by this function).

contains()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

bool contains	(	Iterator1	first1,
		Iterator2	last1,
		Iterator3	first2,
		Iterator4	last2 )

This function checks whether or not the words represented by the ranges first1 to last1 and first2 to last2 are contained in the congruence represented by a ToddCoxeter instance. This function triggers a full enumeration, which may never terminate.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

Whether or not the pair belongs to the congruence.

Warning

Termination of the Todd-Coxeter algorithm is undecidable in general, and this function may never terminate.

Exceptions

LibsemigroupsException

if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.

contains_no_checks()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

bool contains_no_checks ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 )

inline

This function checks whether or not the words represented by the ranges first1 to last1 and first2 to last2 are contained in the congruence represented by a ToddCoxeter instance. This function triggers a full enumeration, which may never terminate.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

Whether or not the pair belongs to the congruence.

Warning

Termination of the Todd-Coxeter algorithm is undecidable in general, and this function may never terminate.

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().

currently_contains()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

tril currently_contains ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 ) const

inline

This function checks whether or not the words represented by the ranges first1 to last1 and first2 to last2 are already known to be contained in the congruence represented by a ToddCoxeter. This function performs no enumeration, so it is possible for the words to be contained in the congruence, but that this is not currently known.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

• tril::TRUE if the words are known to belong to the congruence;
• tril::FALSE if the words are known to not belong to the congruence;
• tril::unknown otherwise.

Exceptions

LibsemigroupsException

if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.

currently_contains_no_checks()

template<typename Word>

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>

tril currently_contains_no_checks ( Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2 ) const

inline

This function checks whether or not the words represented by the ranges first1 to last1 and first2 to last2 are already known to be contained in the congruence represented by a ToddCoxeter instance. This function performs no enumeration, so it is possible for the words to be contained in the congruence, but that this is not currently known.

Template Parameters

Iterator1	the type of the argument first1.
Iterator2	the type of the argument last1.
Iterator3	the type of the argument first2.
Iterator4	the type of the argument last2.

Parameters

first1	iterator pointing at the first letter of the first word.
last1	iterator pointing one beyond the last letter in the first word.
first2	iterator pointing at the first letter of the second word.
last2	iterator pointing one beyond the last letter in the second word.

Returns

• tril::TRUE if the words are known to belong to the congruence;
• tril::FALSE if the words are known to not belong to the congruence;
• tril::unknown otherwise.

Warning

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().

generating_pairs()

template<typename Word>

std::vector< Word > const & generating_pairs ( ) const

inlinenodiscardnoexcept

This function returns the generating pairs of the congruence. The words comprising the generating pairs are converted to native_word_type as they are added via add_generating_pair. This function returns the std::vector of these native_word_type.

Returns

The std::vector of generating pairs.

Exceptions

This function is noexcept and is guaranteed never to throw.

kind()

template<typename Word>

congruence_kind kind ( ) const

nodiscardnoexcept

This function returns the kind of the congruence represented by a ToddCoxeter instance; see congruence_kind for details.

Returns

The kind of the congruence (1- or 2-sided).

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

number_of_classes()

uint64_t number_of_classes ( )

nodiscard

This function computes the number of classes in the congruence represented by a ToddCoxeter instance by running the congruence enumeration until it terminates.

Returns

The number of congruences classes of a ToddCoxeter instance if this number is finite, or POSITIVE_INFINITY in some cases if this number is not finite.

Warning

Termination of the Todd-Coxeter algorithm is undecidable in general, and this function may never terminate.

number_of_generating_pairs()

template<typename Word>

size_t number_of_generating_pairs ( ) const

nodiscardnoexcept

This function returns the number of generating pairs, which is the size of generating_pairs divided by \(2\).

Returns

The number of generating pairs.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

presentation()

template<typename Word>

Presentation< Word > const & presentation ( ) const

inlinenodiscardnoexcept

If a ToddCoxeter instance is constructed or initialised using a presentation, then a const reference to this presentation is returned by this function.

If the ToddCoxeter instance was constructed or initialised from a WordGraph, then this presentation will be empty.

Returns

A const reference to the presentation.

Exceptions

This function is noexcept and is guaranteed never to throw.

reduce()

template<typename Word>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

OutputIterator reduce ( OutputIterator d_first, InputIterator1 first, InputIterator2 last )

inline

This function triggers a full enumeration and then writes a reduced word equivalent to the input word described by the iterator first and last to the output iterator d_first. The word output by this function is equivalent to the input word in the congruence defined by a ToddCoxeter instance. In other words, the output word is a normal form for the input word or equivalently a canconical representative of its congruence class.

Template Parameters

OutputIterator	the type of the argument d_first.
InputIterator1	the type of the argument first.
InputIterator2	the type of the argument last.

Parameters

d_first	output iterator.
first	iterator pointing at the first letter of the input word.
last	iterator pointing one beyond the last letter in the input word.

Returns

An OutputIterator pointing one beyond the last letter inserted into d_first.

Exceptions

LibsemigroupsException

if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.

Warning

Termination of the Todd-Coxeter algorithm is undecidable in general, and this function may never terminate.

reduce_no_checks()

template<typename Word>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

OutputIterator reduce_no_checks ( OutputIterator d_first, InputIterator1 first, InputIterator2 last )

inline

This function triggers a full enumeration and then writes a reduced word equivalent to the input word described by the iterator first and last to the output iterator d_first. The word output by this function is equivalent to the input word in the congruence defined by a ToddCoxeter instance. In other words, the output word is a normal form for the input word or equivalently a canconical representative of its congruence class.

Template Parameters

OutputIterator	the type of the argument d_first.
InputIterator1	the type of the argument first.
InputIterator2	the type of the argument last.

Parameters

d_first	output iterator.
first	iterator pointing at the first letter of the input word.
last	iterator pointing one beyond the last letter in the input word.

Returns

An OutputIterator pointing one beyond the last letter inserted into d_first.

Warning

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().

Termination of the Todd-Coxeter algorithm is undecidable in general, and this function may never terminate.

reduce_no_run()

template<typename Word>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

OutputIterator reduce_no_run ( OutputIterator d_first, InputIterator1 first, InputIterator2 last ) const

inline

This function writes a reduced word equivalent to the input word described by the iterator first and last to the output iterator d_first. This function triggers no enumeration. The word output by this function is equivalent to the input word in the congruence defined by a ToddCoxeter instance. If the ToddCoxeter instance is finished, then the output word is a normal form for the input word. If the ToddCoxeter instance is not finished, then it might be that equivalent input words produce different output words.

Template Parameters

OutputIterator	the type of the argument d_first.
InputIterator1	the type of the argument first.
InputIterator2	the type of the argument last.

Parameters

d_first	output iterator.
first	iterator pointing at the first letter of the input word.
last	iterator pointing one beyond the last letter in the input word.

Returns

An OutputIterator pointing one beyond the last letter inserted into d_first.

Exceptions

LibsemigroupsException

if any of the values pointed at by the iterators is out of range, i.e. they do not belong to presentation().alphabet() and Presentation::validate_word throws.

reduce_no_run_no_checks()

template<typename Word>

template<typename OutputIterator, typename InputIterator1, typename InputIterator2>

OutputIterator reduce_no_run_no_checks ( OutputIterator d_first, InputIterator1 first, InputIterator2 last ) const

inline

This function writes a reduced word equivalent to the input word described by the iterator first and last to the output iterator d_first. This function triggers no enumeration. The word output by this function is equivalent to the input word in the congruence defined by a ToddCoxeter instance. If the ToddCoxeter instance is finished, then the output word is a normal form for the input word. If the ToddCoxeter instance is not finished, then it might be that equivalent input words produce different output words.

Template Parameters

OutputIterator	the type of the argument d_first.
InputIterator1	the type of the argument first.
InputIterator2	the type of the argument last.

Parameters

d_first	output iterator.
first	iterator pointing at the first letter of the input word.
last	iterator pointing one beyond the last letter in the input word.

Returns

An OutputIterator pointing one beyond the last letter inserted into d_first.

Warning

This function does not check that the arguments are valid. In particular, it is assumed that every value pointed at by the iterators belongs to presentation().alphabet().