Konieczny

template<typename TElementType, typename TTraits = KoniecznyTraits<TElementType>>
class Konieczny : public libsemigroups::Runner, private libsemigroups::detail::BruidhinnTraits<TElementType>

Defined in konieczny.hpp.

The class template Konieczny implements Konieczny’s algorithm as described in the article ‘Green’s equivalences in finite semigroups of binary relations’ by Janusz Konieczny; see here for more details. This algorithm is similar to that of Lallement and McFadden; see this paper for more details. It differs in being applicable to subsemigroups of a non-regular semigroup, though is essentially the same algorithm for elements which happen to be regular.

A Konieczny instance is defined by a generating set, and the main function is Konieczny::run, which implements Konieczny’s Algorithm. If Konieczny::run is invoked and Konieczny::finished returns true, then the size, partial order of \(\mathscr{D}\)-classes, and frames for each \(\mathscr{D}\)-class are known.

See also

KoniecznyTraits and DClass

Template Parameters
  • TElementType – the type of the elements of the semigroup (must not be a pointer).

  • TTraits – the type of a traits class with the requirements of KoniecznyTraits.

Member types

D_class_index_type

Type of indices of \(\mathscr{D}\) -classes.

const_d_class_iterator

Return type of cbegin_D_classes and cend_D_classes .

const_element_type

The type of const elements.

const_iterator

A type for const iterators through elements.

const_reference

Type of element const references.

const_regular_d_class_iterator

Return type of cbegin_regular_D_classes and cend_regular_D_classes .

element_type

The type of elements.

lambda_orb_type

The type of the orbit of the lambda values.

lambda_value_type

The type of lambda values.

rho_orb_type

The type of the orbit of the rho values.

rho_value_type

The type of rho values.

Adapter member types

Degree

Adapter for the degree of an element.

EqualTo

Adapter for testing equality.

Lambda

Adapter for the action on LambdaValue ‘s.

Less

Adapter for comparisons.

One

Adapter for the identity element of the given type.

Product

Adapter for the product of two elements.

Rank

Adapter for calculating ranks.

Rho

Adapter for the action on RhoValue ‘s.

Swap

Adapter for swapping.

Constructors

Konieczny()

Default constructor.

Konieczny(std::vector<element_type> const&)

Construct from generators.

Deleted constructors

Konieczny(Konieczny &&) = delete

Deleted.

Konieczny(Konieczny const &) = delete

Deleted.

operator=(Konieczny &&) = delete

Deleted.

operator=(Konieczny const &) = delete

Deleted.

Initialisation

add_generator(const_reference)

Add a copy of an element to the generators.

add_generators(T const&)

Add collection of generators from container.

add_generators(T const&, T const&)

Add collection of generators from iterators.

add_generators(std::initializer_list<const_element_type>)

Add collection of generators from initializer list.

Elements

contains(const_reference)

Test membership of an element.

is_regular_element(const_reference)

Test regularity of an element.

Attributes

D_class_of_element(const_reference)

Returns the \(\mathscr{D}\) -class containing an element.

number_of_D_classes()

Returns the number of \(\mathscr{D}\) -classes.

number_of_H_classes()

Returns the number of \(\mathscr{H}\) -classes.

number_of_L_classes()

Returns the number of \(\mathscr{L}\) -classes.

number_of_R_classes()

Returns the number of \(\mathscr{R}\) -classes.

number_of_idempotents()

Returns the number of idempotents.

number_of_regular_D_classes()

Returns the number of regular \(\mathscr{D}\) -classes.

number_of_regular_L_classes()

Returns the number of regular \(\mathscr{L}\) -classes.

number_of_regular_R_classes()

Returns the number of regular \(\mathscr{R}\) -classes.

number_of_regular_elements()

Returns the number of regular elements.

size()

Returns the size.

Const Attributes

current_number_of_D_classes() const

Returns the current number of \(\mathscr{D}\) -classes.

current_number_of_H_classes() const

Returns the current number of \(\mathscr{H}\) -classes.

current_number_of_L_classes() const

Returns the current number of \(\mathscr{L}\) -classes.

current_number_of_R_classes() const

Returns the current number of regular \(\mathscr{R}\) -classes.

current_number_of_idempotents() const

Returns the current number of idempotents.

current_number_of_regular_D_classes() const

Returns the current number of regular \(\mathscr{D}\) -classes.

current_number_of_regular_L_classes() const

Returns the current number of regular \(\mathscr{L}\) -classes.

current_number_of_regular_R_classes() const

Returns the current number of regular \(\mathscr{R}\) -classes.

current_number_of_regular_elements() const

Returns the current number of regular elements.

current_size() const

Returns the current size.

degree() const noexcept

Returns the degree of elements.

generator(size_t) const

Returns a const reference to the generator given by an index.

number_of_generators() const noexcept

Returns the number of generators.

Iterators

cbegin_D_classes() const

Returns a const iterator referring to a pointer to the first \(\mathscr{D}\) -class.

cbegin_generators() const noexcept

Returns a const iterator pointing to the first generator.

cbegin_rdc() const noexcept

Shorter form of cbegin_regular_D_classes .

cbegin_regular_D_classes() const

Returns a const iterator referring to a pointer to the first regular \(\mathscr{D}\) -class.

cend_D_classes() const noexcept

Returns a const iterator referring to past the pointer to the last \(\mathscr{D}\) -class.

cend_generators() const noexcept

Returns a const iterator pointing to one past the last generator.

cend_rdc() const

Shorter form of cend_regular_D_classes .

cend_regular_D_classes() const noexcept

Returns a const iterator referring to past the pointer to the last regular \(\mathscr{D}\) -class.

Member functions inherited from Runner

dead() const noexcept

Check if the runner is dead.

finished() const

Check if run has been run to completion or not.

kill() noexcept

Stop run from running (thread-safe).

report() const

Check if it is time to report.

report_every() const noexcept

Get the minimum elapsed time between reports.

report_every(TIntType)

Set the minimum elapsed time between reports.

report_every(std::chrono::nanoseconds)

Set the minimum elapsed time between reports.

report_why_we_stopped() const

Report why run stopped.

run()

Run until finished .

run_for(TIntType)

Run for a specified amount of time.

run_for(std::chrono::nanoseconds)

Run for a specified amount of time.

run_until(T&&)

Run until a nullary predicate returns true or finished .

run_until(bool(*)())

Run until a nullary predicate returns true or finished .

running() const noexcept

Check if currently running.

running_for() const noexcept

Check if the runner is currently running for a particular length of time.

running_until() const noexcept

Check if the runner is currently running until a nullary predicate returns true.

started() const

Check if run has been called at least once before.

stopped() const

Check if the runner is stopped.

stopped_by_predicate() const

Check if the runner was, or should, stop because of the argument for run_until .

timed_out() const

Check if the amount of time passed to run_for has elapsed.