Partitioned binary relations

Overview

Defined in element.hpp.

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

Full API

class libsemigroups::PBR : public libsemigroups::detail::ElementWithVectorData<std::vector<uint32_t>, PBR>

Class for partitioned binary relations (PBR).

Partitioned binary relations (PBRs) are a generalisation of bipartitions, which were introduced by Martin and Mazorchuk.

Public Functions

PBR(std::initializer_list<std::vector<uint32_t>>)

A constructor.

Constructs a PBR defined by the initializer list vec. This list should be interpreted in the same way as vector in the vector constructor PBR::PBR.

PBR(size_t)

A constructor.

Constructs an empty (no relation) PBR of the given degree.

PBR(std::initializer_list<std::vector<int32_t>> const&, std::initializer_list<std::vector<int32_t>> const&)

Constructs a PBR from two vectors.

The parameters left and right should be vectors of $ \(n\) vectors of non-negative integer values, so that the vector in position \(i\) of left is the list of points adjacent to \(i\) in the PBR, and the vector in position \(i\) of right is the list of points adjacent to \(n + i\) in the PBR.

void validate() const

Validates the data defining this.

This member function throws a libsemigroups::LibsemigroupsException if the data defining this is invalid, which could occur if:

  • this->_vector has odd length, or

  • this->_vector contains a vector containing a value which is larger than this->_vector.size() (i.e. twice the degree of this).

size_t complexity() const override

Returns the approximate time complexity of multiplying PBRs.

The approximate time complexity of multiplying PBRs is \(2n ^ 3\) where \(n\) is the degree.

size_t degree() const override

Returns the degree of a PBR.

The degree of a PBR is half the number of points in the PBR.

PBR identity() const override

Returns the identity PBR with degree equal to that of this.

This member function returns a new PBR with degree equal to the degree of this where every value is adjacent to its negative. Equivalently, \(i\) is adjacent \(i + n\) and vice versa for every \(i\) less than the degree \(n\).

void redefine(Element const&, Element const&, size_t) override

Multiply x and y and stores the result in this.

This member function redefines this to be the product of the parameters x and y. This member function asserts that the degrees of x, y, and this, are all equal, and that neither x nor y equals this.

The parameter thread_id is required since some temporary storage is required to find the product of x and y. Note that if different threads call this member function with the same value of thread_id then bad things will happen.

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.

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

void increase_degree_by(size_t)

Increases the degree of this by deg.

This does not make sense for all subclasses of Element.

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

PBR identity(size_t n)

Returns the identity PBR with degree equal to n.

This function returns a new PBR with degree equal to n where every value is adjacent to its negative. Equivalently, \(i\) is adjacent \(i + n\) and vice versa for every \(i\) less than the degree \(n\).

Friends

std::ostringstream &operator<<(std::ostringstream&, PBR const&)

Insertion operator.

This member function allows PBR objects to be inserted into an ostringstream

std::ostream &operator<<(std::ostream&, PBR const&)

Insertion operator.

This member function allows PBR objects to be inserted into an ostream.