# Settings¶

This page contains information about the member functions of the ToddCoxeter that control various settings that influence the coset enumeration process.

options::deductions libsemigroups::congruence::ToddCoxeter::deduction_policy() const noexcept

The current value of the deduction policy setting.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type options::deductions.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::deduction_policy(options::deductions val)

Specify how to handle deductions.

This function can be used to specify how to handle deductions. For details see options::deductions.

The default value of this setting is options::deductions::no_stack_if_no_space | options::deductions::v2.

Parameters

val – the policy to use.

Throws

LibsemigroupsException – if val is not valid (i.e. if for example options::deductions::v1 & options::deductions::v2 returns true).

Returns

A reference to *this.

size_t libsemigroups::congruence::ToddCoxeter::f_defs() const noexcept

The current value of the f_defs setting.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type size_t.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::f_defs(size_t val)

The approx number of Felsch style definitions in ACE strategies.

If the strategy being used is any of those mimicking ACE, then the value of this setting is used to determine the number of nodes defined in any Felsch phase of the strategy.

The default value of this setting is 100'000.

Parameters

val – the value to use.

Throws

LibsemigroupsException – if val is 0.

Returns

A reference to *this.

options::froidure_pin libsemigroups::congruence::ToddCoxeter::froidure_pin_policy() const noexcept

The current value of the Froidure-Pin policy setting.

If the ToddCoxeter instance is not created from a FroidurePin instance, or from an object that has an already computed FroidurePin instance, then the value of this setting is ignored.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type options::froidure_pin.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::froidure_pin_policy(options::froidure_pin val) noexcept

Specify whether to use the relations or the Cayley graph.

Sets whether to use the defining relations or the Cayley graph of the FroidurePin instance used to initialise the object.

If the ToddCoxeter instance is not created from a FroidurePin instance, then the value of this setting is ignored.

The default value is options::froidure_pin::use_cayley_graph.

Parameters

val – value indicating whether to use relations or Cayley graph (options::froidure_pin::use_cayley_graph or options::froidure_pin::use_relations).

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

size_t libsemigroups::congruence::ToddCoxeter::hlt_defs() const noexcept

The current value of the hlt_defs setting.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type size_t.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::hlt_defs(size_t val)

The approx number of HLT style definitions in ACE strategies.

If the strategy being used is any of those mimicking ACE, then the value of this setting is used to determine the number of nodes defined in any HLT phase of the strategy.

The default value of this setting is 200'000.

Parameters

val – the value to use.

Throws

LibsemigroupsException – if val is less than length_of_generating_pairs().

Returns

A reference to *this.

size_t libsemigroups::congruence::ToddCoxeter::large_collapse() const noexcept

The current value of the large collapse setting.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type size_t.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::large_collapse(size_t val) noexcept

Specify what should be considered a large collapse.

By default when processing coincidences nodes are merged in the word graph one pair at a time, and the in-neighbours of the surviving node are updated at the same time. If the number of coincidences is large, then it might be that a pair of nodes are merged at one step, then the surviving node is merged with another node at a future step, and this may happen many many times. This results in the in-neighbours of the surviving nodes being repeatedly traversed, which can result in a significant performance penalty. It can be beneficial to stop updating the in-neighbours as nodes are merged, and to just rebuild the entire in-neighbours data structure by traversing the entire word graph after all coincidences have been processed. This is beneficial if the number of surviving nodes is relatively small in comparison to the number of nodes merged. The purpose of this setting is to specify what should be considered a “large” collapse, or more precisely, what number of coincidences in the stack will trigger a change from updating the in-neighbours one-by-one to traversing the entire graph once after all coincidences have been processed.

The default value of this setting is 100'000.

Parameters

val – the value to use.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

The current value of the setting for lookaheads.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

Set the style of lookahead to use in HLT.

If the strategy is not HLT, then the value of this setting is ignored.

Parameters

val – value indicating whether to perform a full or partial lookahead in HLT or Felsch style.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

The current value of the lookahead growth factor.

Parameters

None

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type float.

This setting determines by what factor the number of nodes required to trigger a lookahead grows. More specifically, at the end of any lookahead if the number of active nodes already exceeds the value of next_lookahead() or the number of nodes killed during the lookahead is less than the number of active nodes divided by lookahead_growth_threshold(), then the value of ToddCoxeter::next_lookhead is increased by a multiple of the value.

Parameters

val – the value indicating the lookahead growth factor. The default value is 2.0.

Throws

LibsemigroupsException – if val is less than 1.0.

Returns

A reference to *this.

The current value of the lookahead growth threshold.

Parameters

None

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type size_t.

This setting determines by what threshold for changing the number of nodes required to trigger a lookahead grows. More specifically, at the end of any lookahead if the number of active nodes already exceeds the value of next_lookahead() or the number of nodes killed during the lookahead is less than the number of active nodes divided by lookahead_growth_threshold, then the value of ToddCoxeter::next_lookhead() is increased.

The default value is 4.

Parameters

val – the value indicating the lookahead growth threshold.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

size_t libsemigroups::congruence::ToddCoxeter::lower_bound() const noexcept

The current value of the lower bound setting.

Parameters

None

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type size_t.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::lower_bound(size_t val) noexcept

Specify minimum number of classes that may trigger early stop.

Set a lower bound for the number of classes of the congruence represented by a ToddCoxeter instance. If the number of active cosets becomes at least the value of the argument, and the table is complete (complete returns true), then the enumeration is terminated. When the given bound is equal to the number of classes, this may save tracing relations at many cosets when there is no possibility of finding coincidences.

The default value is UNDEFINED.

Parameters

val – value indicating the lower bound.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

size_t libsemigroups::congruence::ToddCoxeter::max_deductions() const noexcept

The current value of the setting for the maximum number of deductions.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type size_t.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::max_deductions(size_t val) noexcept

The maximum number of deductions in the stack.

This setting specifies the maximum number of deductions that can be in the stack at any given time. What happens if there are the maximum number of deductions in the stack and a new deduction is generated is governed by deduction_policy().

The default value of this setting is 2'000.

Parameters

val – the maximum size of the deduction stack.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

size_t libsemigroups::congruence::ToddCoxeter::max_preferred_defs() const noexcept

The current value of the maximum preferred definitions setting.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type size_t.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::max_preferred_defs(size_t val) noexcept

Specify the maximum number of preferred definitions.

This function can be used to specify the maximum number of preferred definitions that are held in the circular buffer at any time. For details see options::preferred_defs.

The default value of this setting is 256.

Note

If val is 0, then preferred_defs() is set to options::preferred_defs::none.

Parameters

val – the value to use.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

The current value of the minimum lookahead setting.

Parameters

None

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type size_t.

Set the minimum value of next_lookahead().

After a lookahead is performed the value of next_lookahead() is modified depending on the outcome of the current lookahead. If the return value next_lookahead() of is too small or too large, then the value is adjusted according to lookahead_growth_factor() and lookahead_growth_threshold(). This setting specified the minimum possible value for next_lookahead().

The default value is 10'000.

Parameters

val – value indicating the minimum value of next_lookahead().

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

The current value of the next lookahead setting.

Parameters

None

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type size_t.

Set the threshold that will trigger a lookahead in HLT.

If the number of cosets active exceeds the value set by this function, then a lookahead, of the type set using the function lookahead, is triggered. This only applies when using the HLT strategy.

The default value is 5 million.

Parameters

val – value indicating the initial threshold.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

options::preferred_defs libsemigroups::congruence::ToddCoxeter::preferred_defs() const noexcept

The current value of the preferred definitions setting.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type options::preferred_defs.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::preferred_defs(options::preferred_defs val) noexcept

Specify how to handle preferred definitions.

This function can be used to specify how to handle preferred definitions. For details see options::preferred_defs.

The default value of this setting is options::preferred_defs::deferred.

Note

If val is options::preferred_defs::none, then max_preferred_defs() is set to 0.

Parameters

val – the value to use.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

std::chrono::nanoseconds libsemigroups::congruence::ToddCoxeter::random_interval() const noexcept

The current value of the random interval setting.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type std::chrono::nanoseconds.

template<typename T>
inline ToddCoxeter &libsemigroups::congruence::ToddCoxeter::random_interval(T val) noexcept

Set the amount of time per strategy for options::strategy::random.

Sets the duration (by converting to nanoseconds) that a given randomly selected strategy will run for, when using the random strategy (options::strategy::random).

The default value is 200ms.

Template Parameters
Parameters

val – the duration per strategy if the strategy is random.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::random_interval(std::chrono::nanoseconds val) noexcept

Set the amount of time per strategy for options::strategy::random.

Sets the duration in nanoseconds that a given randomly selected strategy will run for, when using the random strategy (options::strategy::random).

The default value is 200ms.

Parameters

val – the number of nanoseconds used per strategy if the strategy is random.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::random_shuffle_generating_pairs()

Randomly shuffle the generating pairs.

Additionally, if this was defined over a finitely presented semigroup, then the copy of the defining relations of that semigroup contained in this (if any) are also sorted according to func.

Parameters

(None)

Throws

LibsemigroupsException – if started() returns true.

Returns

A reference to *this.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::remove_duplicate_generating_pairs()

Remove duplicate generating pairs.

Additionally, if this was defined over a finitely presented semigroup, then the copy of the defining relations of that semigroup contained in this (if any) also have duplicates removed.

Parameters

(None)

Throws

LibsemigroupsException – if started() returns true.

Returns

A reference to *this.

bool libsemigroups::congruence::ToddCoxeter::restandardize() const noexcept

The current value of the restandardize setting.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type bool.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::restandardize(bool val) noexcept

Specify whether to standardize between HLT and Felsch.

This setting allows the word graph to be standardized when switching between an HLT and Felsch phase (or vice versa) in an enumeration.

The default value of this setting is false.

Parameters

val – the value to use.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

bool libsemigroups::congruence::ToddCoxeter::save() const noexcept

The current value of save setting.

Parameters

None

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type bool.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::save(bool val)

Process deductions during HLT.

If the argument of this function is true and the HLT strategy is being used, then deductions are processed during the enumeration.

The default value is false.

Parameters

val – value indicating whether or not to process deductions.

Throws
Returns

A reference to *this.

std::string libsemigroups::congruence::ToddCoxeter::settings_string() const

Returns a string containing a tabularized summary of all the settings.

This function returns a string containing a tabularized summary of the settings of a ToddCoxeter instance.

Parameters

(None)

Returns

A std::string.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::simplify(size_t n = 1)

Simplify defining relations and/or generating pairs.

In the following description we refer to the defining relations and generating pairs of a ToddCoxeter instance (if any) as the relation words. In many examples the performance of the Todd-Coxeter algorithm is improved by reducing the length of the relation words. This seems to particularly be the case when using the Felsch strategy. This function does three things:

1. Attempts to reduce the length of the words by finding the equivalence relation on the relation words generated by the pairs of relation words. If $$A = \{u_1, u_2, \ldots, u_n\}$$ are the distinct words in an equivalence class and $$u_1$$ is the short-lex minimum word in the class, then the relation words are replaced by $$u_1 = u_2, u_1 = u_3, \cdots, u_1 = u_n$$.

2. Removes duplicate relation words.

3. Repeatedly finds the subword of the relation words that will result in the maximum reduction in the overall length of the relation words when replaced by a redundant generator (if any such subword exists). This step is performed at most n times.

Warning

This function might change the generators and relation words of a ToddCoxeter instance.

Parameters

n – the number of repeats for step c.

Throws
Returns

A reference to this.

inline ToddCoxeter &libsemigroups::congruence::ToddCoxeter::sort_generating_pairs(sort_free_function_type func = shortlex_compare)

Sort generating pairs.

Sorts all existing generating pairs according to the binary function func. Additionally, if this was defined over a finitely presented semigroup, then the copy of the defining relations of that semigroup contained in this (if any) are also sorted according to func.

Warning

If add_pair is called after this function, then it may no longer be the case that the defining relations and generating pairs of this are sorted by func.

Parameters

func – a value of type sort_function_type that defines a linear order on the relations in a ToddCoxeter instance.

Throws

LibsemigroupsException – if started() returns true.

Returns

A reference to *this.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::sort_generating_pairs(sort_function_type func)

Sort generating pairs.

Sorts all existing generating pairs according to the binary function func. Additionally, if this was defined over a finitely presented semigroup, then the copy of the defining relations of that semigroup contained in this (if any) are also sorted according to func.

Warning

If add_pair is called after this function, then it may no longer be the case that the defining relations and generating pairs of this are sorted by func.

Parameters

func – a value of type sort_function_type that defines a linear order on the relations in a ToddCoxeter instance.

Throws

LibsemigroupsException – if started() returns true.

Returns

A reference to *this.

bool libsemigroups::congruence::ToddCoxeter::standardize() const noexcept

The current value of the standardize setting.

Parameters

None

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A value of type bool.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::standardize(bool val) noexcept

Partially short-lex standardize the table during enumeration.

If the argument of this function is true, then the coset table is partially standardized (according to the short-lex order) during the coset enumeration.

The default value is false.

Parameters

val – value indicating whether or not to standardize.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.

options::strategy libsemigroups::congruence::ToddCoxeter::strategy() const noexcept

The current strategy for enumeration.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current strategy, a value of type options::strategy.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::strategy(options::strategy val)

Specify the strategy.

The strategy used during the enumeration can be specified using this function.

The default value is options::strategy::hlt.

Parameters

val – value indicating which strategy to use

Throws

LibsemigroupsException – if val is options::strategy::felsch and any of the following conditions apply:

Returns

A reference to *this.

bool libsemigroups::congruence::ToddCoxeter::use_relations_in_extra() const noexcept

The current value of the setting for using relations.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The current value of the setting, a value of type bool.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::use_relations_in_extra(bool val) noexcept

Perform an HLT-style push of the defining relations at the identity.

If a ToddCoxeter instance is defined over a finitely presented semigroup and the Felsch strategy is being used, it can be useful to follow all the paths from the identity labelled by the underlying relations of the semigroup (if any). The setting specifies whether or not to do this.

The default value of this setting is false.

Parameters

val – the boolean value.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A reference to *this.