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.

options::lookahead libsemigroups::congruence::ToddCoxeter::lookahead() const noexcept¶

The current value of the setting for lookaheads.

Parameters: (None)

Throws: (None) – This function is noexcept and is guaranteed never to throw.
Returns: A value of type options::lookahead.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::lookahead(options::lookahead val) noexcept¶

Set the style of lookahead to use in HLT.

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

The default value is options::lookahead::partial | options::lookahead::hlt. The other possible value are documented in options::lookahead.

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.

float libsemigroups::congruence::ToddCoxeter::lookahead_growth_factor() const noexcept¶

The current value of the lookahead growth factor.

See also

lookahead_growth_factor(float)

Parameters: None

Throws: (None) – This function is noexcept and is guaranteed never to throw.
Returns: A value of type float.

ToddCoxeter &libsemigroups::congruence::ToddCoxeter::lookahead_growth_factor(float val)¶

Set the lookahead growth factor.

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.

size_t libsemigroups::congruence::ToddCoxeter::lookahead_growth_threshold() const noexcept¶

The current value of the lookahead growth threshold.

See also

lookahead_growth_threshold()

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::lookahead_growth_threshold(size_t val) noexcept¶

Set the lookahead growth threshold.

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.

See also

lower_bound(size_t)

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.

size_t libsemigroups::congruence::ToddCoxeter::min_lookahead() const noexcept¶

The current value of the minimum lookahead setting.

See also

min_lookahead(size_t)

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::min_lookahead(size_t val) noexcept¶

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.

size_t libsemigroups::congruence::ToddCoxeter::next_lookahead() const noexcept¶

The current value of the next lookahead setting.

See also

next_lookahead(size_t)

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::next_lookahead(size_t val) noexcept¶

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: T – std::chrono::duration
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.

See also

save(bool)

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

LibsemigroupsException – if prefill was used to initialise this.
LibsemigroupsException – if the parent FroidurePin (if any) is finite, and the value of froidure_pin_policy() is not options::froidure_pin::use_relations.

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:

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\).
Removes duplicate relation words.
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

LibsemigroupsException – if started() returns true.
LibsemigroupsException – if the ToddCoxeter instance was prefilled.

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.

See also

random_shuffle_generating_pairs

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.

See also

random_shuffle_generating_pairs

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.

See also

standardize(bool)

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:

prefill was used to initialise this
if the parent FroidurePin (if any) is finite, and the value of froidure_pin_policy() is not options::froidure_pin::use_relations.

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.