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
-
explicit 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 asvector
in the vector constructor PBR::PBR.
-
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
andright
should be vectors of $ \(n\) vectors of non-negative integer values, so that the vector in position \(i\) ofleft
is the list of points adjacent to \(i\) in the PBR, and the vector in position \(i\) ofright
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, orthis->_vector
contains a vector containing a value which is larger thanthis->_vector.size()
(i.e. twice the degree ofthis
).
-
virtual 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.
-
virtual 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\).
-
virtual void redefine(Element const&, Element const&, size_t) override¶
Multiply
x
andy
and stores the result inthis
.This member function redefines
this
to be the product of the parametersx
andy
. This member function asserts that the degrees ofx
,y
, andthis
, are all equal, and that neitherx
nory
equalsthis
.The parameter
thread_id
is required since some temporary storage is required to find the product ofx
andy
. Note that if different threads call this member function with the same value ofthread_id
then bad things will happen.
-
virtual bool operator==(Element const&) const = 0¶
Returns
true
ifthis
equalsthat
.This member function checks the mathematical equality of two Element objects in the same subclass of Element.
-
virtual bool operator<(Element const&) const = 0¶
Returns
true
ifthis
is less thanthat
.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.
-
inline bool operator>(Element const &that) const¶
Returns
true
ifthis
is greater thanthat
.This member function returns
true
ifthis
is greater thanthat
, under the ordering defined by the operator <.
-
inline bool operator!=(Element const &that) const¶
Returns
true
ifthis
is not equal tothat
.This member function returns
true
ifthis
is mathematically not equal tothat
.
-
inline bool operator<=(Element const &that) const¶
Returns
true
ifthis
is less than or equal tothat
.This member function returns
true
ifthis
is less than (under the order defined by the operator <) or mathematically equal tothat
.
-
inline bool operator>=(Element const &that) const¶
Returns
true
ifthis
is less than or equal tothat
.This member function returns
true
ifthis
is greater than (under the order defined by the operator <) or mathematically equal tothat
.
-
inline 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.
-
virtual void swap(Element&) = 0¶
Swap another Element with
this
.This member function swaps the defining data of
x
andthis
.
-
inline virtual void redefine(Element const &x, Element const &y)¶
Multiplies
x
andy
and stores the result inthis
.Redefine
this
to be the product ofx
andy
. 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.
-
inline void redefine(Element const *x, Element const *y)¶
Multiplies
x
andy
and stores the result inthis
.This version of the member function takes const pointers rather than const references, but otherwise behaves like the other Element::redefine.
-
inline void redefine(Element const *x, Element const *y, size_t)¶
Multiplies
x
andy
and stores the result inthis
.This member function differs from the the previous only in taking pointers instead of references.
-
inline virtual void increase_degree_by(size_t)¶
Increases the degree of
this
bydeg
.This does not make sense for all subclasses of Element.
-
virtual 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.
-
virtual 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
-
explicit PBR(std::initializer_list<std::vector<uint32_t>>)¶