template<typename PresentationType>
class libsemigroups::Stephen< PresentationType >

Defined in sims.hpp.

This class implements Stephen's procedure for constructing the WordGraph corresponding to the left factors of a word in a finitely presented semigroup or a finitely presented inverse semigroup. The algorithm implemented in this class is closely related to the Todd-Coxeter algorithm (as implemented in ToddCoxeter) and originates in [56].

Template Parameters

PresentationType a type derived from PresentationBase. This is the type of the underlying presentation used in the Stephen algorithm. Common choices include Presentation<word_type>, Presentation<std::string>, InversePresentation<word_type> and InversePresentation<std::string>. If an InversePresentation is supplied, then the Stephen class will use the Stephen procedure for inverse semigroups when run. Otherwise the Stephen procedure for general semigroups is used instead.

Inheritance diagram for Stephen< PresentationType >:

[legend]

Public Types
using	node_type = word_graph_type::node_type
	The node type of word_graph_type.

using	presentation_type = PresentationType
	The underlying presentation type.

using	word_graph_type = WordGraph<uint32_t>
	The return type of the function word_graph.

Public Types inherited from Runner
enum class	state { never_run = 0 , running_to_finish = 1 , running_for = 2 , running_until = 3 , timed_out = 4 , stopped_by_predicate = 6 , not_running = 7 , dead = 8 }
	Enum class for the state of the Runner. More...

Public Types inherited from Reporter
using	nanoseconds = std::chrono::nanoseconds
	Alias for std::chrono::nanoseconds.

using	time_point = std::chrono::high_resolution_clock::time_point
	Alias for std::chrono::high_resolution_clock::time_point.

Public Member Functions
	Stephen ()
	Default constructor.

	Stephen (PresentationType &&p)
	Construct from a presentation (move).

	Stephen (PresentationType const &p)
	Construct from a presentation (copy).

	Stephen (std::shared_ptr< PresentationType > const &ptr)
	Construct from a shared pointer to presentation (copy).

	Stephen (Stephen &&)=default
	Default move constructor.

	Stephen (Stephen const &that)=default
	Default copy constructor.

node_type	accept_state ()
	Get the accept state of the word graph.

void	append_no_checks (Stephen< PresentationType > &that)
	Append a Stephen instance (no checks).

Stephen &	init ()
	Reinitialize an existing Stephen instance.

Stephen &	init (PresentationType &&p)
	Initialize from a presentation (move).

Stephen &	init (PresentationType const &p)
	Initialize from a presentation (copy).

Stephen &	init (std::shared_ptr< PresentationType > const &ptr)
	Initialize from a shared pointer to presentation (copy).

bool	is_word_set () const noexcept
	Check if the initial word is set.

void	operator*= (Stephen< PresentationType > &that)
	Append a Stephen instance.

Stephen &	operator= (Stephen &&)=default
	Default move assignment operator.

Stephen &	operator= (Stephen const &)=default
	Default copy assignment operator.

presentation_type const &	presentation () const noexcept
	Get the input presentation.

template<typename Iterator1, typename Iterator2>
Stephen &	set_word (Iterator1 first, Iterator2 last)
	Set the initial word.

template<typename Iterator1, typename Iterator2>
Stephen &	set_word_no_checks (Iterator1 first, Iterator2 last)
	Set the initial word (no checks).

word_type const &	word () const
	Get the initial word.

word_graph_type const &	word_graph () const
	Get the word graph.

Public Member Functions inherited from Runner
	Runner ()
	Default constructor.

	Runner (Runner &&other)
	Move constructor.

	Runner (Runner const &other)
	Copy constructor.

state	current_state () const noexcept
	Return the current state.

bool	dead () const noexcept
	Check if the runner is dead.

bool	finished () const
	Check if run has been run to completion or not.

Runner &	init ()
	Initialize an existing Runner object.

void	kill () noexcept
	Stop run from running (thread-safe).

Runner &	operator= (Runner &&other)
	Move assignment operator.

Runner &	operator= (Runner const &other)
	Copy assignment operator.

void	report_why_we_stopped () const
	Report why run stopped.

void	run ()
	Run until finished.

void	run_for (std::chrono::nanoseconds t)
	Run for a specified amount of time.

template<typename Time>
void	run_for (Time t)
	Run for a specified amount of time.

void	run_until (bool(*func)())
	Run until a nullary predicate returns `true` or finished.

template<typename Func>
void	run_until (Func &&func)
	Run until a nullary predicate returns `true` or finished.

bool	running () const noexcept
	Check if currently running.

bool	running_for () const noexcept
	Check if the runner is currently running for a particular length of time.

bool	running_until () const noexcept
	Check if the runner is currently running until a nullary predicate returns `true`.

bool	started () const noexcept
	Check if run has been called at least once before.

bool	stopped () const
	Check if the runner is stopped.

bool	stopped_by_predicate () const
	Check if the runner was stopped, or should stop, because of the argument last passed to run_until.

virtual bool	success () const
	Check if run has been run to completion successfully.

bool	timed_out () const
	Check if the amount of time passed to run_for has elapsed.

Public Member Functions inherited from Reporter
	Reporter ()
	Default constructor.

	Reporter (Reporter &&that)
	Default move constructor.

	Reporter (Reporter const &that)
	Default copy constructor.

void	emit_divider ()

Reporter &	init ()
	Initialize an existing Reporter object.

time_point	last_report () const noexcept
	Get the time point of the last report.

Reporter &	operator= (Reporter &&that)
	Default move assignment operator.

Reporter &	operator= (Reporter const &that)
	Default copy assignment operator.

bool	report () const
	Check if it is time to report.

std::string const &	report_divider () const noexcept

Reporter &	report_divider (std::string const &val)

nanoseconds	report_every () const noexcept
	Get the minimum elapsed time between reports.

Reporter &	report_every (nanoseconds val) noexcept
	Set the minimum elapsed time between reports in nanoseconds.

template<typename Time>
Reporter &	report_every (Time t) noexcept
	Set the minimum elapsed time between reports in a unit of time other than nanoseconds.

std::string const &	report_prefix () const noexcept
	Get the current prefix string for reporting.

Reporter &	report_prefix (std::string const &val)
	Set the prefix string for reporting.

Reporter const &	reset_last_report () const
	Set the last report time point to now.

Reporter const &	reset_start_time () const
	Reset the start time (and last report) to now.

time_point	start_time () const noexcept
	Get the start time.

Static Public Member Functions
static constexpr node_type	initial_state () noexcept
	Get the initial state of the word graph.

Additional Inherited Members
Related Symbols inherited from Reporter
static std::chrono::nanoseconds	delta (std::chrono::high_resolution_clock::time_point const &t)
	The time between a given point and now.

Constructor & Destructor Documentation

◆ Stephen() [1/4]

template<typename PresentationType>

Stephen ( )

Default constructs an empty instance, use init and set_word to specify the presentation and the word, respectively.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ Stephen() [2/4]

template<typename PresentationType>

Stephen ( PresentationType const & p )

inlineexplicit

Construct an instance from the presentation p. This constructor copies p.

Template Parameters

PresentationType a type derived from PresentationBase.

Parameters

p	the presentation.

◆ Stephen() [3/4]

template<typename PresentationType>

Stephen ( PresentationType && p )

inlineexplicit

Construct an instance from the presentation p. This constructor moves p.

Template Parameters

PresentationType a type derived from PresentationBase.

Parameters

p	the presentation.

◆ Stephen() [4/4]

template<typename PresentationType>

Stephen ( std::shared_ptr< PresentationType > const & ptr )

inlineexplicit

Construct an instance from the shared pointer ptr to a shared presentation object. This constructor copies ptr.

Template Parameters

PresentationType a type derived from PresentationBase.

Parameters

ptr	a shared pointer to a presentation.

Member Function Documentation

◆ accept_state()

template<typename PresentationType>

node_type accept_state ( )

This function triggers the algorithm implemented in this class (if it hasn't been triggered already), and then returns the accept state of the produced word graph.

Returns: A node_type.

Exceptions

LibsemigroupsException if no presentation was set at the construction or with Stephen::init or if no word was set with Stephen::set_word .

Warning: Termination of the Stephen algorithm is undecidable in general, and this function may never terminate..

◆ append_no_checks()

template<typename PresentationType>

void append_no_checks ( Stephen< PresentationType > & that )

This function appends the Stephen instance that to this. This modifies the current Stephen instance in-place. The result is a Stephen instance with underlying word equal to the concatenation of this.word() and that.word().

The advantage of this is that if either this or that have already been (partially) run, then we can reuse the underlying word graphs instead of having to recompute them completely from scratch.

Parameters

that	the Stephen instance to append.

Warning: No checks are made on the validity of the parameters to this function. Bad things may happen if this and that have different underlying presentations or if either of them is not ready.

See also: Stephen::operator*= .

◆ init() [1/4]

template<typename PresentationType>

Stephen & init ( )

This function puts a Stephen instance 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.

◆ init() [2/4]

template<typename PresentationType>

Stephen & init ( PresentationType && p )

inline

This function puts a Stephen instance back into the same state as if it had been newly constructed from the presentation p. This initializer moves p.

Template Parameters

PresentationType a type derived from PresentationBase.

Parameters

p	the presentation.

Returns: A reference to this.

◆ init() [3/4]

template<typename PresentationType>

Stephen & init ( PresentationType const & p )

inline

This function puts a Stephen instance back into the same state as if it had been newly constructed from the presentation p. This initializer copies p.

Template Parameters

PresentationType a type derived from PresentationBase.

Parameters

p	the presentation.

Returns: A reference to this.

◆ init() [4/4]

template<typename PresentationType>

Stephen & init ( std::shared_ptr< PresentationType > const & ptr )

This function puts a Stephen instance back into the same state as if it had been newly constructed from the shared pointer to a presentation ptr. This initializer copies ptr.

Template Parameters

PresentationType a type derived from PresentationBase.

Parameters

ptr	a shared pointer to a presentation.

Returns: A reference to this.

◆ initial_state()

template<typename PresentationType>

static constexpr node_type initial_state ( )

inlinestaticconstexprnoexcept

This function return the initial state of word_graph.

Returns: A node_type.

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

◆ is_word_set()

template<typename PresentationType>

bool is_word_set ( ) const

inlinenoexcept

Returns true if a word has been set with set_word since the last presentation change and false otherwise.

Returns: A bool.

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

◆ operator*=()

template<typename PresentationType>

void operator*= ( Stephen< PresentationType > & that )

This function appends the Stephen instance that to this. This modifies the current Stephen instance in-place. The result is a Stephen instance with underlying word equal to the concatenation of this.word() and that.word().

The advantage of this is that if either this or that have already been (partially) run, then we can reuse the underlying word graphs instead of having to recompute them completely from scratch.

Parameters

that	the Stephen instance to append.

Exceptions

LibsemigroupsException	if no presentation was set at the construction of `this` or `that` or with Stephen::init or if no word was set with Stephen::set_word .
LibsemigroupsException	if the presentations for `this` and `that` differ.

◆ presentation()

template<typename PresentationType>

presentation_type const & presentation ( ) const

inlinenoexcept

This function returns a const reference to the input presentation.

Returns: A const reference to a presentation_type.

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

◆ set_word()

template<typename PresentationType>

template<typename Iterator1, typename Iterator2>

Stephen & set_word	(	Iterator1	first,
		Iterator2	last )

inline

This function sets the word whose left factors, or equivalent words, are sought.

Template Parameters

Iterator1	the type of the argument `first1`.
Iterator2	the type of the argument `last1`.

Parameters

first	iterator pointing at the first letter of the word.
last	iterator pointing one beyond the last letter in the 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.

See also: stephen::set_word

◆ set_word_no_checks()

template<typename PresentationType>

template<typename Iterator1, typename Iterator2>

Stephen & set_word_no_checks	(	Iterator1	first,
		Iterator2	last )

This function sets the word whose left factors, or equivalent words, are sought.

Template Parameters

Iterator1	the type of the argument `first1`.
Iterator2	the type of the argument `last1`.

Parameters

first	iterator pointing at the first letter of the word.
last	iterator pointing one beyond the last letter in the 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().

See also: stephen::set_word_no_checks

◆ word()

template<typename PresentationType>

word_type const & word ( ) const

inline

Returns a const reference to the word set by set_word.

Returns: A const reference to a word_type.

Exceptions

LibsemigroupsException if no presentation was set at the construction or with Stephen::init or if no word was set with Stephen::set_word .

◆ word_graph()

template<typename PresentationType>

word_graph_type const & word_graph ( ) const

inline

Returns a const reference to the word graph in its present state. The algorithm implemented in this class is not triggered by calls to this function.

Returns: A const reference to a word_graph_type.

Exceptions

LibsemigroupsException if no presentation was set at the construction or with Stephen::init or if no word was set with Stephen::set_word .

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

/Users/jdm/libsemigroups/include/libsemigroups/stephen.hpp

Public Types

Public Member Functions

Static Public Member Functions

Additional Inherited Members

Constructor & Destructor Documentation

◆ Stephen() [1/4]

◆ Stephen() [2/4]

◆ Stephen() [3/4]

◆ Stephen() [4/4]

Member Function Documentation

◆ accept_state()

◆ append_no_checks()

◆ init() [1/4]

◆ init() [2/4]

◆ init() [3/4]

◆ init() [4/4]

◆ initial_state()

◆ is_word_set()

◆ operator*=()

◆ presentation()

◆ set_word()

◆ set_word_no_checks()

◆ word()

◆ word_graph()