template<typename Subclass>
class libsemigroups::SimsSettings< Subclass >

Defined in sims.hpp.

On this page we describe the SimsSettings class. The purpose of this class is to allow us to use the same interface for settings for Sims1, Sims2, RepOrc, and MinimalRepOrc.

See also: Sims1; Sims2; RepOrc; MinimalRepOrc

Public Types
using	label_type = typename word_graph_type::label_type
	Type for the labels in the associated WordGraph objects.

using	letter_type = typename word_type::value_type
	Type for letters in the underlying presentation.

using	node_type = typename word_graph_type::node_type
	Type for the nodes in the associated WordGraph objects.

using	size_type = typename word_graph_type::size_type
	The size_type of the associated WordGraph objects.

using	word_graph_type = WordGraph<uint32_t>
	The type of the associated WordGraph objects.

Public Member Functions
	SimsSettings ()

	SimsSettings (SimsSettings &&that)

	SimsSettings (SimsSettings const &that)

template<typename OtherSubclass>
	SimsSettings (SimsSettings< OtherSubclass > const &that)
	Construct from SimsSettings with different subclass.

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
Subclass &	add_excluded_pair (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Add an excluded pair via iterators.

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
Subclass &	add_excluded_pair_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Add an excluded pair via iterators (no checks).

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
Subclass &	add_included_pair (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Add an included pair via iterators (no checks).

template<typename Iterator1, typename Iterator2, typename Iterator3, typename Iterator4>
Subclass &	add_included_pair_no_checks (Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
	Add an included pair via iterators.

template<typename Func>
Subclass &	add_pruner (Func &&func)
	Add a pruner to the search tree.

std::vector< word_type >::const_iterator	cbegin_long_rules () const noexcept
	Get the pointer to the first long rule.

Subclass &	cbegin_long_rules (size_t pos)
	Set the beginning of the long rules (position).

Subclass &	cbegin_long_rules (std::vector< word_type >::const_iterator it)
	Set the beginning of the long rules (iterator).

Subclass &	clear_excluded_pairs ()
	Clear the set of excluded words.

Subclass &	clear_included_pairs ()
	Clear the set of included pairs.

Subclass &	clear_long_rules ()
	Clear the set of long rules.

Subclass &	clear_pruners ()
	Clear the set of pruners.

std::vector< word_type > const &	excluded_pairs () const noexcept
	Get the set of pairs that must be excluded from every congruence.

size_t	idle_thread_restarts () const noexcept
	Get the idle thread restart attempt count.

Subclass &	idle_thread_restarts (size_t val)
	Set the idle thread restart attempt count.

std::vector< word_type > const &	included_pairs () const noexcept
	Get the set of pairs that must be included in every congruence.

Subclass &	init ()
	Reinitialize an existing SimsSettings object.

template<typename OtherSubclass>
Subclass &	init (SimsSettings< OtherSubclass > const &that)
	Initialize from SimsSettings with different subclass.

Subclass &	long_rule_length (size_t val)
	Set the length of a long rule.

size_t	number_of_long_rules () const noexcept
	Returns the number of rules marked as long rules.

size_t	number_of_threads () const noexcept
	Get the number of threads.

Subclass &	number_of_threads (size_t val)
	Set the number of threads.

SimsSettings &	operator= (SimsSettings &&that)

SimsSettings &	operator= (SimsSettings const &that)

Presentation< word_type > const &	presentation () const noexcept
	Get the presentation over which the congruences produced by an instance are defined.

Subclass &	presentation (Presentation< word_type > const &p)
	Set the presentation over which the congruences produced by an instance are defined.

auto const &	pruners () const noexcept
	Get all active pruners of the search tree.

SimsSettings const &	settings () const noexcept

SimsStats &	stats () const noexcept
	Get the current stats object.

template<typename Iterator1, typename Iterator2>
void	throw_if_letter_not_in_alphabet (Iterator1 first, Iterator2 last) const
	Throws if any letter in a range is out of bounds.

Constructor & Destructor Documentation

◆ SimsSettings() [1/3]

template<typename Subclass>

SimsSettings ( )

Default constructor.

Constructs a SimsSettings object. Defaults to a single thread and 64 idle thread restarts, no other settings set. Use

presentation to set the presentation;
number_of_threads to set the number of threads;
included_pairs to set the pairs to be included;
excluded_pairs to set the pairs to be excluded;
add_pruner to add a pruner;
long_rule_length to set the length of long rules;
idle_thread_restarts to set the number of idle thread restarts.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ SimsSettings() [2/3]

template<typename Subclass>

SimsSettings ( SimsSettings< Subclass > const & that )

inline

Copy constructor.

Returns a SimsSettings object that is a copy of that. The state of the new SimsSettings object is the same as that.

Parameters

that	the SimsSettings to copy.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ SimsSettings() [3/3]

template<typename Subclass>

SimsSettings ( SimsSettings< Subclass > && that )

inline

Move constructor.

Returns a SimsSettings object that is initialized from that. The state of the new SimsSettings object is the same as that.

Parameters

that	the SimsSettings to copy.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Member Function Documentation

◆ add_excluded_pair()

template<typename Subclass>

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

Subclass & add_excluded_pair	(	Iterator1	first1,
		Iterator2	last1,
		Iterator3	first2,
		Iterator4	last2 )

inline

This function adds a pair that must be excluded from every congruence returned by a Sims1 or Sims2 instance.

Template Parameters

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

Parameters

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

Returns: A reference to this.

Exceptions

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

◆ add_excluded_pair_no_checks()

template<typename Subclass>

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

Subclass & add_excluded_pair_no_checks	(	Iterator1	first1,
		Iterator2	last1,
		Iterator3	first2,
		Iterator4	last2 )

inline

This function adds a pair that must be excluded from every congruence returned by a Sims1 or Sims2 instance.

Template Parameters

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

Parameters

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

Returns: A reference to this.

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

◆ add_included_pair()

template<typename Subclass>

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

Subclass & add_included_pair	(	Iterator1	first1,
		Iterator2	last1,
		Iterator3	first2,
		Iterator4	last2 )

inline

This function adds a pair that must be included in every congruence returned by a Sims1 or Sims2 instance.

Template Parameters

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

Parameters

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

Returns: A reference to this.

Exceptions

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

◆ add_included_pair_no_checks()

template<typename Subclass>

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

Subclass & add_included_pair_no_checks	(	Iterator1	first1,
		Iterator2	last1,
		Iterator3	first2,
		Iterator4	last2 )

inline

This function adds a pair that must be included in every congruence returned by a Sims1 or Sims2 instance.

Template Parameters

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

Parameters

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

Returns: A reference to this.

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

◆ add_pruner()

template<typename Subclass>

template<typename Func>

Subclass & add_pruner ( Func && func )

inline

Parameters

func	an rvalue reference to a pruner function.

Returns: A reference to this.

Warning: When running the Sims low-index backtrack with multiple threads, each added pruner must be guaranteed thread safe. Failing to do so could cause bad things to happen.

See also: pruners

◆ cbegin_long_rules() [1/3]

template<typename Subclass>

std::vector< word_type >::const_iterator cbegin_long_rules ( ) const

inlinenodiscardnoexcept

Returns the pointer to the first long rule.

Returns: A const reference to Presentation<word_type>.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ cbegin_long_rules() [2/3]

template<typename Subclass>

Subclass & cbegin_long_rules ( size_t pos )

Set the beginning of the long rules using a position in presentation().rules.

The "long rules" are the rules used after a complete deterministic word graph has been found in the search. If such a word graph is compatible with the long rules specified by this function, then this word graph is accepted, and if not it is rejected.

The purpose of this is to improve the backtrack search by reducing the time spent processing "long" rules in each node of the search tree, and to only check them at the leaves.

Parameters

pos	position of the the left hand side of the first long rule.

Returns: A reference to this.

Exceptions

LibsemigroupsException	if `pos` is not a valid position in `presentation().rules`
LibsemigroupsException	if the rule at position `pos` is not the left hand side of a rule (i.e. if `pos` is odd).

◆ cbegin_long_rules() [3/3]

template<typename Subclass>

Subclass & cbegin_long_rules ( std::vector< word_type >::const_iterator it )

Set the beginning of the long rules using an iterator.

The "long rules" are the rules used after a complete deterministic word graph has been found in the search. If such a word graph is compatible with the long rules specified by this function, then this word graph is accepted, and if not it is rejected.

The purpose of this is to improve the backtrack search by reducing the time spent processing "long" rules in each node of the search tree, and to only check them at the leaves.

Parameters

it	iterator pointing at the left hand side of the first long rule.

Returns: A reference to this.

Exceptions

LibsemigroupsException	if `it` does not point into `presentation().rules`
LibsemigroupsException	if `it` does not point at the left hand side of a rule (i.e. if it points at an odd indexed position in `presentation().rules`).

◆ clear_excluded_pairs()

template<typename Subclass>

Subclass & clear_excluded_pairs ( )

Returns: A reference to this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ clear_included_pairs()

template<typename Subclass>

Subclass & clear_included_pairs ( )

inline

Returns: A reference to this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ clear_long_rules()

template<typename Subclass>

Subclass & clear_long_rules ( )

inline

Returns: A reference to this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ clear_pruners()

template<typename Subclass>

Subclass & clear_pruners ( )

Returns: A reference to this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ excluded_pairs()

template<typename Subclass>

std::vector< word_type > const & excluded_pairs ( ) const

inlinenodiscardnoexcept

This function returns the set of excluded pairs.

The congruences computed by a Sims1 or Sims2 instance will never contain the pairs returned by excluded_pairs. In other words, the congruences computed by this instance are only taken among those that do not contain any of the pairs of elements of the underlying semigroup (defined by the presentation returned by presentation) represented by the relations of the presentation returned by excluded_pairs.

Returns: A const reference to std::vector<word_type>.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ idle_thread_restarts() [1/2]

template<typename Subclass>

size_t idle_thread_restarts ( ) const

inlinenodiscardnoexcept

Returns the number of times an idle thread will attempt to restart before yielding during the execution of Sims1 or Sims2.

Returns: A size_t.

Exceptions: This function is noexcept and is guaranteed never to throw.

Note: This setting has no effect if number_of_threads is 1.

◆ idle_thread_restarts() [2/2]

template<typename Subclass>

Subclass & idle_thread_restarts ( size_t val )

This function sets the idle thread restart attempt count used in Sims1 or Sims2.

The default value is 64.

Parameters

val	the maximum number of times an idle thread will attempt to restart before yielding.

Returns: A reference to this.

Exceptions

LibsemigroupsException if the argument val is 0.

Note: This setting has no effect if number_of_threads is 1.

◆ included_pairs()

template<typename Subclass>

std::vector< word_type > const & included_pairs ( ) const

inlinenodiscardnoexcept

This function returns the set of included pairs.

The congruences computed by a Sims1 or Sims2 instance always include the pairs returned by included_pairs. In other words, the congruences computed by this instance are only taken among those that contains the pairs of elements of the underlying semigroup (defined by the presentation returned by presentation) represented by the relations of the presentation returned by included_pairs.

Returns: A const reference to std::vector<word_type>.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ init()

template<typename Subclass>

Subclass & init ( )

This function puts a SimsSettings object back into the same state as if it had been newly default constructed.

Returns: A reference to this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ long_rule_length()

template<typename Subclass>

Subclass & long_rule_length ( size_t val )

Define the length of a "long" rule.

This function modifies presentation so that the rules whose length (sum of the lengths of both sides) is at least val (if any) occur at the end of presentation().rules and so that cbegin_long_rules points at the such rule.

The relative orders of the rules within presentation may not be preserved.

Parameters

val	the value of the long rule length.

Returns: A reference to this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ number_of_threads() [1/2]

template<typename Subclass>

size_t number_of_threads ( ) const

inlinenodiscardnoexcept

Returns the current number of threads.

Returns: A size_t.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ number_of_threads() [2/2]

template<typename Subclass>

Subclass & number_of_threads ( size_t val )

This function sets the number of threads to be used by Sims1 or Sims2.

The default value is 1.

Parameters

val	the maximum number of threads to use.

Returns: A reference to this.

Exceptions

LibsemigroupsException if the argument val is 0.

Note: The value of val is capped at std::thread::hardware_concurrency(). Trying to set a higher value is equivalent to setting std::thread::hardware_concurrency().

◆ operator=() [1/2]

template<typename Subclass>

SimsSettings & operator= ( SimsSettings< Subclass > && that )

inline

Move assignment operator.

Assigns a SimsSettings object that is initialized from that. The state of the new SimsSettings object is the same as that.

Parameters

that	the SimsSettings to copy.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ operator=() [2/2]

template<typename Subclass>

SimsSettings & operator= ( SimsSettings< Subclass > const & that )

inline

Copy assignment operator.

Assigns a SimsSettings object that is a copy of that. The state of the new SimsSettings object is the same as that.

Parameters

that	the SimsSettings to copy.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ presentation() [1/2]

template<typename Subclass>

Presentation< word_type > const & presentation ( ) const

inlinenodiscardnoexcept

Returns a const reference to the current relations of the underlying presentation.

This function returns the defining presentation of a Sims1 or Sims2 instance. The congruences computed by cbegin and cend of the appropriate subclass are defined over the semigroup or monoid defined by this presentation.

Returns: A const reference to Presentation<word_type>.

Exceptions: This function is noexcept and is guaranteed never to throw.

Warning: The value returned by this function is not guaranteed be the same as the presentation that was used to construct the object! A Sims1 or Sims2 object requires the generators of the defining presentation \(\mathcal{P}\) to be \(\{0, \ldots, n - 1\}\) where \(n\) is the size of the alphabet of \(\mathcal{P}\). Every occurrence of every generator a in the presentation p used to construct a Sims1 or Sims2 instance is replaced by p.index(a).

◆ presentation() [2/2]

template<typename Subclass>

Subclass & presentation ( Presentation< word_type > const & p )

Set the presentation over which the congruences produced by an instance are defined. These are the rules used at every node in the depth first search conducted by objects of this type.

Parameters

p	the presentation.

Returns: A reference to this.

Exceptions

LibsemigroupsException	if `p` is not valid.
LibsemigroupsException	if the alphabet of `p` is non-empty and not compatible with included_pairs or excluded_pairs.
Libsemigroups	if the alphabet of `p` is not normalized.
LibsemigroupsException	if `p` has 0-generators and 0-relations.

◆ pruners()

template<typename Subclass>

auto const & pruners ( ) const

inlinenoexcept

Returns a const reference to the set of pruners.

A pruner is any function that takes as input a word graph and returns a boolean. We require that if a pruner returns false for a word graph wg, then it returns false for all word graphs that are descended from wg in the Sims word graph search tree. The pruners are used to refine the congruence search tree during the execution of the Sims algorithm. As such, the congruences computed by this instance are only taken among those whose word graphs are accepted by all pruners returned by pruners.

Returns: A const reference to std::vector<std::function<bool(word_graph_type const&)>>, the set of all pruners.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ settings()

template<typename Subclass>

SimsSettings const & settings ( ) const

inlinenodiscardnoexcept

Returns the settings object of *this.

The settings object contains all the settings that are common to Sims1, Sims2, RepOrc, and MinimalRepOrc, which are currently:

presentation
long_rule_length
number_of_threads

The return value of this function can be used to initialise another Sims1, Sims2, RepOrc, or MinimalRepOrc with these settings.

Returns: A const reference to SimsSettings.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ stats()

template<typename Subclass>

SimsStats & stats ( ) const

inlinenodiscardnoexcept

Returns a const reference to the current stats object.

The value returned by this function is a SimsStats object which contains some statistics related to the current Sims1 or Sims2 instance and any part of the depth first search already conducted.

Returns: A const reference to SimsStats.

Exceptions: This function is noexcept and is guaranteed never to throw.

◆ throw_if_letter_not_in_alphabet()

template<typename Subclass>

template<typename Iterator1, typename Iterator2>

void throw_if_letter_not_in_alphabet	(	Iterator1	first,
		Iterator2	last ) const

inline

This function throws a LibsemigroupsException if any value pointed at by an iterator in the range first to last is out of bounds (i.e. does not belong to the alphabet of the presentation used to construct the Sims1 or Sims2 instance).

Template Parameters

Iterator1	the type of first argument `first`.
Iterator2	the type of second argument `last`.

Parameters

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

Exceptions

LibsemigroupsException if any letter in the range from first to last is out of bounds.

The documentation for this class was generated from the following file:

/Users/jdm/libsemigroups/include/libsemigroups/sims.hpp

Public Types

Public Member Functions

Constructor & Destructor Documentation

◆ SimsSettings() [1/3]

◆ SimsSettings() [2/3]

◆ SimsSettings() [3/3]

Member Function Documentation

◆ add_excluded_pair()

◆ add_excluded_pair_no_checks()

◆ add_included_pair()

◆ add_included_pair_no_checks()

◆ add_pruner()

◆ cbegin_long_rules() [1/3]

◆ cbegin_long_rules() [2/3]

◆ cbegin_long_rules() [3/3]

◆ clear_excluded_pairs()

◆ clear_included_pairs()

◆ clear_long_rules()

◆ clear_pruners()

◆ excluded_pairs()

◆ idle_thread_restarts() [1/2]

◆ idle_thread_restarts() [2/2]

◆ included_pairs()

◆ init()

◆ long_rule_length()

◆ number_of_threads() [1/2]

◆ number_of_threads() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ presentation() [1/2]

◆ presentation() [2/2]

◆ pruners()

◆ settings()

◆ stats()

◆ throw_if_letter_not_in_alphabet()