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 exampleoptions::deductions::v1 & options::deductions::v2
returnstrue
).- 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
is0
.- 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
- 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 than1.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
- 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
- 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
is0
, 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
- 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
- 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 to0
.- 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 inthis
(if any) are also sorted according tofunc
.- 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 inthis
(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
- 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, ifthis
was defined over a finitely presented semigroup, then the copy of the defining relations of that semigroup contained inthis
(if any) are also sorted according tofunc
.See also
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 byfunc
.- 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, ifthis
was defined over a finitely presented semigroup, then the copy of the defining relations of that semigroup contained inthis
(if any) are also sorted according tofunc
.See also
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 byfunc
.- 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
- 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
.