ToddCoxeter helper functions

Defined in todd-coxeter-helpers.hpp.

This page contains documentation for many helper functions for the ToddCoxeter class. In particular, these functions include versions of several of the member functions of ToddCoxeter (that accept iterators) whose parameters are not iterators, but objects instead. The helpers documented on this page all belong to the namespace todd_coxeter.

See also

Common congruence helpers

Functions
template<typename Word>
auto	class_by_index (ToddCoxeter< Word > &tc, index_type n)
	Returns a range object containing every word in the congruence class with given index.
template<typename Word>
auto	class_by_index_no_checks (ToddCoxeter< Word > &tc, index_type n)
	Returns a range object containing every word in the congruence class with given index.
template<typename Word>
auto	class_of (ToddCoxeter< Word > &tc, char const *w)
	Returns a range object containing every word in the congruence class of a given word.
template<typename Word, typename Iterator1, typename Iterator2>
auto	class_of (ToddCoxeter< Word > &tc, Iterator1 first, Iterator2 last)
	Returns a range object containing every word in the congruence class of a word given by iterators.
template<typename Word, typename Int>
auto	class_of (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns a range object containing every word in the congruence class of a given word.
template<typename Word>
auto	class_of (ToddCoxeter< Word > &tc, Word const &w)
	Returns a range object containing every word in the congruence class of a given word.
template<typename Word>
auto	class_of_no_checks (ToddCoxeter< Word > &tc, char const *w)
	Returns a range object containing every word in the congruence class of a given word.
template<typename Word, typename Iterator1, typename Iterator2>
auto	class_of_no_checks (ToddCoxeter< Word > &tc, Iterator1 first, Iterator2 last)
	Returns a range object containing every word in the congruence class of a word given by iterators.
template<typename Word, typename Int>
auto	class_of_no_checks (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns a range object containing every word in the congruence class of a given word.
template<typename Word>
auto	class_of_no_checks (ToddCoxeter< Word > &tc, Word const &w)
	Returns a range object containing every word in the congruence class of a given word.
template<typename Word>
index_type	current_index_of (ToddCoxeter< Word > &tc, char const *w)
	Returns the current index of the class containing a word.
template<typename Word, typename Int>
index_type	current_index_of (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns the current index of the class containing a word.
template<typename Word>
index_type	current_index_of (ToddCoxeter< Word > const &tc, Word const &w)
	Returns the current index of the class containing a word.
template<typename Word>
index_type	current_index_of_no_checks (ToddCoxeter< Word > &tc, char const *w)
	Returns the current index of the class containing a word.
template<typename Word, typename Int>
index_type	current_index_of_no_checks (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns the current index of the class containing a word.
template<typename Word>
index_type	current_index_of_no_checks (ToddCoxeter< Word > const &tc, Word const &w)
	Returns the current index of the class containing a word.
template<typename Word>
Word	current_word_of (ToddCoxeter< Word > &tc, index_type i)
	Returns a word representing a class with given index.
template<typename Word>
Word	current_word_of_no_checks (ToddCoxeter< Word > &tc, index_type i)
	Returns a word representing a class with given index.
template<typename Word>
index_type	index_of (ToddCoxeter< Word > &tc, char const *w)
	Returns the index of the class containing a word.
template<typename Word, typename Int>
index_type	index_of (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns the index of the class containing a word.
template<typename Word>
index_type	index_of (ToddCoxeter< Word > &tc, Word const &w)
	Returns the index of the class containing a word.
template<typename Word>
index_type	index_of_no_checks (ToddCoxeter< Word > &tc, char const *w)
	Returns the index of the class containing a word.
template<typename Word, typename Int>
index_type	index_of_no_checks (ToddCoxeter< Word > &tc, std::initializer_list< Int > const &w)
	Returns the index of the class containing a word.
template<typename Word>
index_type	index_of_no_checks (ToddCoxeter< Word > &tc, Word const &w)
	Returns the index of the class containing a word.
tril	is_non_trivial (ToddCoxeter &tc, size_t tries=10, std::chrono::milliseconds try_for=std::chrono::milliseconds(100), float threshold=0.99)
	Check if the congruence has more than one class.
template<typename Word, typename Time>
std::vector< Word >::const_iterator	redundant_rule (Presentation< Word > const &p, Time t)
	Return an iterator pointing at the left hand side of a redundant rule.
template<typename Word>
Word	word_of (ToddCoxeter< Word > &tc, index_type i)
	Returns a word representing a class with given index.
template<typename Word>
Word	word_of_no_checks (ToddCoxeter< Word > &tc, index_type i)
	Returns a word representing a class with given index.

Function Documentation

class_by_index()

template<typename Word>

auto class_by_index ( ToddCoxeter< Word > & tc, index_type n )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the class with index n in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Parameters

tc	the ToddCoxeter instance.
n	the index of the class.

Returns

A range object containing the class with index n.

Exceptions

LibsemigroupsException

if n is greater than or equal to tc.number_of_classes().

Warning

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

class_by_index_no_checks()

template<typename Word>

auto class_by_index_no_checks ( ToddCoxeter< Word > & tc, index_type n )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the class with index n in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Parameters

tc	the ToddCoxeter instance.
n	the index of the class.

Returns

A range object containing the class with index n.

Warning

This function does not check its arguments. In particular, it is assumed that n is strictly less than tc.number_of_classes().

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

class_of() [1/4]

template<typename Word>

auto class_of ( ToddCoxeter< Word > & tc, char const * w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the same class as the input word w in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Parameters

tc	the ToddCoxeter instance.
w	pointer to first letter.

Returns

A range object containing the words in the class of the input word.

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.

class_of() [2/4]

template<typename Word, typename Iterator1, typename Iterator2>

auto class_of ( ToddCoxeter< Word > & tc, Iterator1 first, Iterator2 last )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the same class as the word (contained in the range from first to last) in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Template Parameters

Iterator1	the type of the 2nd argument first.
Iterator2	the type of the 3rd argument last.

Parameters

tc	the ToddCoxeter instance.
first	iterator pointing at the first letter of the word.
last	iterator pointing one beyond the last letter of the word.

Returns

A range object containing the words in the class of the input word.

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.

class_of() [3/4]

template<typename Word, typename Int>

auto class_of ( ToddCoxeter< Word > & tc, std::initializer_list< Int > const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the same class as the input word w in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Template Parameters

Int	the type of the letters in the word w.

Parameters

tc	the ToddCoxeter instance.
w	the input word.

Returns

A range object containing the words in the class of the input word.

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.

class_of() [4/4]

template<typename Word>

auto class_of ( ToddCoxeter< Word > & tc, Word const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the same class as the input word w in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Template Parameters

Word	the type of the 2nd argument w.

Parameters

tc	the ToddCoxeter instance.
w	the input word.

Returns

A range object containing the words in the class of the input word.

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.

class_of_no_checks() [1/4]

template<typename Word>

auto class_of_no_checks ( ToddCoxeter< Word > & tc, char const * w )

inlinenodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the same class as the input word w in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Parameters

tc	the ToddCoxeter instance.
w	pointer to first letter.

Returns

A range object containing the words in the class of the input word.

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.

class_of_no_checks() [2/4]

template<typename Word, typename Iterator1, typename Iterator2>

auto class_of_no_checks ( ToddCoxeter< Word > & tc, Iterator1 first, Iterator2 last )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the same class as the word (contained in the range from first to last) in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Template Parameters

Iterator1	the type of the 2nd argument first.
Iterator2	the type of the 3rd argument last.

Parameters

tc	the ToddCoxeter instance.
first	iterator pointing at the first letter of the word.
last	iterator pointing one beyond the last letter of the word.

Returns

A range object containing the words in the class of the input word.

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.

class_of_no_checks() [3/4]

template<typename Word, typename Int>

auto class_of_no_checks ( ToddCoxeter< Word > & tc, std::initializer_list< Int > const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the same class as the input word w in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Template Parameters

Int	the type of the letters in the word w.

Parameters

tc	the ToddCoxeter instance.
w	the input word.

Returns

A range object containing the words in the class of the input word.

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.

class_of_no_checks() [4/4]

template<typename Word>

auto class_of_no_checks ( ToddCoxeter< Word > & tc, Word const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function returns a range object containing every word in belonging to the same class as the input word w in the congruence represented by the ToddCoxeter instance tc. Calls to this function trigger a full enumeration of tc.

Template Parameters

Word	the type of the 2nd argument w.

Parameters

tc	the ToddCoxeter instance.
w	the input word.

Returns

A range object containing the words in the class of the input word.

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.

current_index_of() [1/3]

template<typename Word>

index_type current_index_of ( ToddCoxeter< Word > & tc, char const * w )

inlinenodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.current_index_of(w, w + std::strlen(w));

See ToddCoxeter::current_index_of for details.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The current index of the class containing the word.

current_index_of() [2/3]

template<typename Word, typename Int>

index_type current_index_of ( ToddCoxeter< Word > & tc, std::initializer_list< Int > const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.current_index_of(std::begin(w), std::end(w));

See current_index_of for details.

Template Parameters

Int	the type of items in the second argument w.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The current index of the class containing the word.

current_index_of() [3/3]

template<typename Word>

index_type current_index_of ( ToddCoxeter< Word > const & tc, Word const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.current_index_of(std::begin(w), std::end(w));

See current_index_of for details.

Template Parameters

Word	the type of the second argument w.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The current index of the class containing the word.

current_index_of_no_checks() [1/3]

template<typename Word>

index_type current_index_of_no_checks ( ToddCoxeter< Word > & tc, char const * w )

inlinenodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.current_index_of_no_checks(w, w + std::strlen(w));

See ToddCoxeter::current_index_of_no_checks for details.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The current index of the class containing the word.

current_index_of_no_checks() [2/3]

template<typename Word, typename Int>

index_type current_index_of_no_checks ( ToddCoxeter< Word > & tc, std::initializer_list< Int > const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.current_index_of_no_checks(std::begin(w), std::end(w));

See ToddCoxeter::current_index_of_no_checks for details.

Template Parameters

Int	the type of items in the second argument w.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The current index of the class containing the word.

current_index_of_no_checks() [3/3]

template<typename Word>

index_type current_index_of_no_checks ( ToddCoxeter< Word > const & tc, Word const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.current_index_of_no_checks(std::begin(w), std::end(w));

See ToddCoxeter::current_index_of_no_checks for details.

Template Parameters

Word	the type of the second argument w.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The current index of the class containing the word.

current_word_of()

template<typename Word>

Word current_word_of ( ToddCoxeter< Word > & tc, index_type i )

nodiscard

Defined in todd-coxeter-helpers.hpp.

See ToddCoxeter::word_of for details.

Template Parameters

Word	the type of the returned word (default: word_type).

Parameters

tc	the ToddCoxeter instance.
i	the index of the class.

Returns

A representative of the class with given index.

current_word_of_no_checks()

template<typename Word>

Word current_word_of_no_checks ( ToddCoxeter< Word > & tc, index_type i )

nodiscard

Defined in todd-coxeter-helpers.hpp.

See ToddCoxeter::word_of_no_checks for details.

Template Parameters

Word	the type of the returned word (default: word_type).

Parameters

tc	the ToddCoxeter instance.
i	the index of the class.

Returns

A representative of the class with given index.

index_of() [1/3]

template<typename Word>

index_type index_of ( ToddCoxeter< Word > & tc, char const * w )

inlinenodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.index_of(w, w + std::strlen(w));

See ToddCoxeter::index_of for details.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The current index of the class containing the word.

index_of() [2/3]

template<typename Word, typename Int>

index_type index_of ( ToddCoxeter< Word > & tc, std::initializer_list< Int > const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.index_of(std::begin(w), std::end(w));

See index_of for details.

Template Parameters

Int	the type of items in the second argument w.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The index of the class containing the word.

index_of() [3/3]

template<typename Word>

index_type index_of ( ToddCoxeter< Word > & tc, Word const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.index_of(std::begin(w), std::end(w));

See index_of for details.

Template Parameters

Word	the type of the second argument w.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The index of the class containing the word.

index_of_no_checks() [1/3]

template<typename Word>

index_type index_of_no_checks ( ToddCoxeter< Word > & tc, char const * w )

inlinenodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.index_of_no_checks(w, w + std::strlen(w));

See ToddCoxeter::index_of_no_checks for details.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The current index of the class containing the word.

index_of_no_checks() [2/3]

template<typename Word, typename Int>

index_type index_of_no_checks ( ToddCoxeter< Word > & tc, std::initializer_list< Int > const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.index_of_no_checks(std::begin(w), std::end(w));

See index_of_no_checks for details.

Template Parameters

Int	the type of items in the second argument w.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The index of the class containing the word.

index_of_no_checks() [3/3]

template<typename Word>

index_type index_of_no_checks ( ToddCoxeter< Word > & tc, Word const & w )

nodiscard

Defined in todd-coxeter-helpers.hpp.

This function just calls

tc.index_of_no_checks(std::begin(w), std::end(w));

See ToddCoxeter::index_of_no_checks for details.

Template Parameters

Word	the type of the second argument w.

Parameters

tc	the ToddCoxeter instance.
w	the word.

Returns

The index of the class containing the word.

is_non_trivial()

tril is_non_trivial ( ToddCoxeter & tc, size_t tries = 10, std::chrono::milliseconds try_for = std::chrono::milliseconds(100), float threshold = 0.99 )

nodiscard

Defined in todd-coxeter-helpers.hpp.

Returns tril::TRUE if it is possible to show that the congruence is non-trivial; tril::FALSE if the congruence is already known to be trivial; and tril::unknown if it is not possible to show that the congruence is non-trivial.

This function attempts to find a non-trivial congruence containing the congruence represented by a ToddCoxeter instance by repeating the following steps on a copy until the enumeration concludes:

1. running the enumeration for the specified amount of time
2. repeatedly choosing a random pair of nodes and identifying them, until the number of nodes remaining in the quotient is smaller than threshold times the initial number of nodes for this step.

If at the end of this process, the ToddCoxeter instance is non-trivial, then the original ToddCoxeter is also non-trivial. Otherwise, the entire process is repeated again up to a total of tries times.

Parameters

tc	the ToddCoxeter instance.
tries	the number of attempts to find non-trivial super-congruence.
try_for	the amount of time in millisecond to enumerate the congruence after choosing a random pair of representatives and identifying them.
threshold	the threshold (see description).

Returns

A value of type tril

redundant_rule()

template<typename Word, typename Time>

std::vector< Word >::const_iterator redundant_rule ( Presentation< Word > const & p, Time t )

nodiscard

Defined in todd-coxeter-helpers.hpp.

Starting with the last rule in the presentation, this function attempts to run the Todd-Coxeter algorithm on the rules of the presentation except for a given omitted rule. For every such omitted rule, Todd-Coxeter is run for the length of time indicated by the second parameter t, and then it is checked if the omitted rule can be shown to be redundant.

If the omitted rule can be shown to be redundant in this way, then an iterator pointing to its left hand side is returned.

If no rule can be shown to be redundant in this way, then an iterator pointing to p.rules.cend() is returned.

Template Parameters

Word	type of words in the Presentation.
Time	type of the 2nd parameter (time to try running Todd-Coxeter).

Parameters

p	the presentation.
t	time to run Todd-Coxeter for every omitted rule.

Returns

An iterator pointing at the left-hand side of a redundant rule of p.rules.cend().

Warning

The progress of the Todd-Coxeter algorithm may differ between different calls to this function even if the parameters are identical. As such this function is non-deterministic, and may produce different results with the same input.

word_of()

template<typename Word>

Word word_of ( ToddCoxeter< Word > & tc, index_type i )

nodiscard

Defined in todd-coxeter-helpers.hpp.

See ToddCoxeter::word_of for details.

Template Parameters

Word	the type of the returned word (default: word_type).

Parameters

tc	the ToddCoxeter instance.
i	the index of the class.

Returns

A representative of the class with given index.

word_of_no_checks()

template<typename Word>

Word word_of_no_checks ( ToddCoxeter< Word > & tc, index_type i )

nodiscard

Defined in todd-coxeter-helpers.hpp.

See ToddCoxeter::word_of_no_checks for details.

Template Parameters

Word	the type of the returned word (default: word_type).

Parameters

tc	the ToddCoxeter instance.
i	the index of the class.

Returns

A representative of the class with given index.