Transformations

Overview

Defined in element.hpp.

This page contains the documentation for the class template libsemigroups::Transformation.

Full API

template<typename TValueType>
class libsemigroups::Transformation : public libsemigroups::detail::TransfBase<TValueType, Transformation<TValueType>>

Template class for transformations.

The value of the template parameter T can be used to reduce the amount of memory required by instances of this class; see PartialTransformation for more details.

A transformation \(f\) is just a function defined on the whole of \(\{0, 1, \ldots, n - 1\}\) for some integer \(n\) called the degree of \(f\). A transformation is stored as a vector of the images of \(\{0, 1, \ldots, n - 1\}\), i.e. \(\{(0)f, (1)f, \ldots, (n - 1)f\}\).

Public Functions

Transformation(std::vector<TValueType> const &vec)

A constructor.

Constructs a Transformation f of degree vec.size() from vec, where the image of a point i is given by vec[i].

Transformation(std::vector<TValueType> &&vec)

A constructor.

The parameter vector should be a rvalue reference to defining data of the transformation.

Returns an transformation whose defining data is vec. This constructor moves the data from vec, meaning that vec is changed by this constructor.

Transformation(std::initializer_list<TValueType> imgs)

A constructor.

Constructs a Transformation f of degree imgs.size() from imgs, where the image of a point i is given by imgs[i].

Transformation(Transformation<TValueType> const &copy)

A copy constructor.

Constructs a Transformation which is mathematically equal to copy.

void validate() const

Validates the data defining this.

This member function throws a libsemigroups::LibsemigroupsException if any value of this is out of bounds (i.e. greater than or equal to this->degree()).

void increase_degree_by(size_t m) override

Increases the degree of this by deg.

This does not make sense for all subclasses of Element.

void validate() const

Validates the data defining this.

This member function throws a libsemigroups::LibsemigroupsException if any value of this is out of bounds (i.e. less than 0, greater than or equal to degree(), and not libsemigroups::UNDEFINED).

size_t complexity() const override

Returns the approximate time complexity of multiplying two partial transformations.

The approximate time complexity of multiplying partial transformations is just their degree.

size_t complexity() const = 0

Returns the approximate time complexity of multiplying two Element objects in a given subclass.

This member function returns an integer which represents the approximate time complexity of multiplying two objects in the same subclass of Element which have the same Element::degree. For example, the approximate time complexity of multiplying two \(3\times 3\) matrices over a common semiring is \(O(3 ^ 3)\), and 27 is returned by MatrixOverSemiring::complexity.

The returned value is used in, for example, FroidurePin::fast_product and FroidurePin::nr_idempotents to decide if it is better to multiply elements or follow a path in the Cayley graph.

size_t degree() const final

Returns the degree of a partial transformation.

The degree of a partial transformation is the number of points used in its definition.

size_t degree() const = 0

Returns the degree of an Element.

This member function returns an integer which represents the size of the element, and is used to determine whether or not two elements are compatible for multiplication. For example, two Transformation objects of different degrees cannot be multiplied, and a Bipartition of degree 10 cannot be an element of a monoid of bipartitions of degree 3.

See the relevant subclass for the particular meaning of the return value of this member function for each subclass.

size_t crank() const

Returns the rank of a partial transformation.

The rank of a partial transformation is the number of its distinct image values, not including libsemigroups::UNDEFINED. This function recomputes the return value every time it is called.

Transformation<TValueType> identity() const override

Returns the identity transformation with same degree as this.

This member function returns a new partial transformation with degree equal to the degree of this that fixes every value from 0 to the degree of this.

bool operator==(Element const&) const = 0

Returns true if this equals that.

This member function checks the mathematical equality of two Element objects in the same subclass of Element.

bool operator<(Element const&) const = 0

Returns true if this is less than that.

This member function defines a total order on the set of objects in a given subclass of Element with a given Element::degree. The definition of this total order depends on the member function for the operator < in the subclass.

bool operator>(Element const &that) const

Returns true if this is greater than that.

This member function returns true if this is greater than that, under the ordering defined by the operator <.

bool operator!=(Element const &that) const

Returns true if this is not equal to that.

This member function returns true if this is mathematically not equal to that.

bool operator<=(Element const &that) const

Returns true if this is less than or equal to that.

This member function returns true if this is less than (under the order defined by the operator <) or mathematically equal to that.

bool operator>=(Element const &that) const

Returns true if this is less than or equal to that.

This member function returns true if this is greater than (under the order defined by the operator <) or mathematically equal to that.

size_t hash_value() const

Return the hash value of an Element.

This member function returns a hash value for an object in a subclass of Element. This value is only computed the first time this member function is called.

void swap(Element&) = 0

Swap another Element with this.

This member function swaps the defining data of x and this.

void redefine(Element const &x, Element const &y)

Multiplies x and y and stores the result in this.

Redefine this to be the product of x and y. This is in-place multiplication to avoid allocation of memory for products which do not need to be stored for future use.

The implementation of this member function in the Element base class simply calls the 3 parameter version with third parameter 0. Any subclass of Element can implement either a two or three parameter version of this member function and the base class member function implements the other member function.

void redefine(Element const *x, Element const *y)

Multiplies x and y and stores the result in this.

This version of the member function takes const pointers rather than const references, but otherwise behaves like the other Element::redefine.

void redefine(Element const &x, Element const &y, size_t)

Multiplies x and y and stores the result in this.

Redefine this to be the product of x and y. This is in-place multiplication to avoid allocation of memory for products which do not need to be stored for future use.

The implementation of this member function in the Element base class simply calls the 2 parameter version and ignores the third parameter thread_id. Any subclass of Element can implement either a two or three parameter version of this member function and the base class member function implements the other member function.

The parameter thread_id is required in some derived classes of Element because some temporary storage is required to find the product of x and y.

Note that if different threads call this member function on a derived class of Element where static temporary storage is used in the redefine member function with the same value of thread_id, then bad things may happen.

void redefine(Element const *x, Element const *y, size_t)

Multiplies x and y and stores the result in this.

This member function differs from the the previous only in taking pointers instead of references.

Element *heap_copy() const = 0

Returns a new element completely independent of this.

This member function really copies an Element. To minimise the amount of copying when Element objects are inserted in a std::unordered_map and other containers, an Element behaves somewhat like a pointer, in that the actual data in an Element is only copied when this member function is called. Otherwise, if an Element is copied, then its defining data is only stored once.

Element *heap_identity() const = 0

Returns an independent copy of the identity.

This member function returns a copy of the identity element (in the appropriate semigroup) which is independent from previous copies.

Public Static Functions

Transformation<TValueType> identity(size_t n)

Returns the identity transformation with n.

This member function returns a new partial transformation with degree equal to n and that fixes every value from 0 to n.