Bipartitions¶
Overview¶
Defined in element.hpp
.
This page contains the documentation for the class template
libsemigroups::Bipartition
.
Full API¶
-
class
libsemigroups
::
Bipartition
: public libsemigroups::detail::ElementWithVectorDataDefaultHash<uint32_t, Bipartition>¶ Class for bipartitions.
A bipartition is a partition of the set \(\{0, ..., 2n - 1\}\) for some integer \(n\); see the Semigroups package for GAP documentation for more details. The Bipartition class is more complex (i.e. has more member functions) than strictly required by the algorithms for a FroidurePin object because the extra member functions are used in the GAP package Semigroups package for GAP.
Public Functions
-
Bipartition
()¶ A constructor.
Constructs a uninitialised bipartition.
-
Bipartition
(size_t)¶ A constructor.
Constructs a uninitialised bipartition of degree
degree
.
-
Bipartition
(std::vector<uint32_t> const&)¶ A constructor.
The parameter
blocks
must have length 2n for some positive integer n, consist of non-negative integers, and have the property that if i, i > 0, occurs inblocks
, then i - 1 occurs earlier in blocks.The parameter
blocks
is copied.
-
Bipartition
(std::vector<uint32_t>&&)¶ A constructor.
The parameter
vector
should be a rvalue reference to defining data of the Bipartition.Returns a Bipartition whose defining data is
vec
. This constructor moves the data fromvec
, meaning thatvec
is changed by this constructor.
-
Bipartition
(std::initializer_list<uint32_t> blocks)¶ A constructor.
Converts
blocks
to a vector and uses corresponding constructor.
-
Bipartition
(Bipartition const&)¶ A copy constructor.
Constructs a Bipartition that is mathematically equal to
copy
.
-
Bipartition
(std::initializer_list<std::vector<int32_t>> const&)¶ A constructor.
The argument
blocks
should be a list of vectors which partition the ranges [-n .. -1] U [1 .. n] for some positive integer n, called the degree of the bipartition. The bipartition constructed has equivalence classes given by the vectors inblocks
.
-
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, ora positive integer i occurs in
this->_vector
before the integer i - 1
-
size_t
complexity
() const override¶ Returns the approximate time complexity of multiplication.
In the case of a Bipartition of degree n the value 2n ^ 2 is returned.
-
size_t
degree
() const override¶ Returns the degree of the bipartition.
A bipartition is of degree n if it is a partition of \(\{0, \ldots, 2n - 1\}\).
-
Bipartition
identity
() const override¶ Returns an identity bipartition.
The identity bipartition of degree \(n\) has blocks \(\{i, -i\}\) for all \(i\in \{0, \ldots, n - 1\}\). This member function returns a new identity bipartition of degree equal to the degree of
this
.
-
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 (as defined at the top of this page) 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.
-
size_t
rank
()¶ Returns the number of transverse blocks.
The rank of a bipartition is the number of blocks containing both positive and negative values. This value is cached after it is first computed.
-
uint32_t
const_nr_blocks
() const¶ Returns the number of blocks in a bipartition.
This member function differs for Bipartition::nr_blocks in that the number of blocks is not cached if it has not been previously computed.
-
uint32_t
nr_blocks
()¶ Returns the number of blocks in a bipartition.
This value is cached the first time it is computed.
-
uint32_t
nr_left_blocks
()¶ Returns the number of blocks containing a positive integer.
The left blocks of a bipartition is the partition of \(\{0, \ldots, n - 1\}\) induced by the bipartition. This member function returns the number of blocks in this partition.
-
uint32_t
nr_right_blocks
()¶ Returns the number of blocks containing a negative integer.
The right blocks of a bipartition is the partition of \(\{n, \ldots, 2n - 1\}\) induced by the bipartition. This member function returns the number of blocks in this partition.
-
bool
is_transverse_block
(size_t)¶ Returns
true
if the block with indexindex
is transverse.A block of a biparition is transverse if it contains integers less than and greater than \(n\), which is the degree of the bipartition. This member function asserts that the parameter
index
is less than the number of blocks in the bipartition.
-
Blocks *
left_blocks
()¶ Return the left blocks of a bipartition.
The left blocks of a bipartition is the partition of \(\{0, \ldots, n - 1\}\) induced by the bipartition. This member function returns a Blocks object representing this partition.
-
Blocks *
right_blocks
()¶ Return the left blocks of a bipartition.
The right blocks of a bipartition is the partition of \(\{n, \ldots, 2n - 1\}\) induced by the bipartition. This member function returns a Blocks object representing this partition.
-
void
set_nr_blocks
(size_t)¶ Set the cached number of blocks.
This member function sets the cached value of the number of blocks of
this
tonr_blocks
. It asserts that either there is no existing cached value ornr_blocks
equals the existing cached value.
-
void
set_nr_left_blocks
(size_t)¶ Set the cached number of left blocks.
This member function sets the cached value of the number of left blocks of
this
tonr_left_blocks
. It asserts that either there is no existing cached value ornr_left_blocks
equals the existing cached value.
-
void
set_rank
(size_t)¶ Set the cached rank.
This member function sets the cached value of the rank of
this
torank
. It asserts that either there is no existing cached value orrank
equals the existing cached value.
-
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.
-
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.
-
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 <.
-
bool
operator!=
(Element const &that) const¶ Returns
true
ifthis
is not equal tothat
.This member function returns
true
ifthis
is mathematically not equal tothat
.
-
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
.
-
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
.
-
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
andthis
.
-
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.
-
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.
-
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.
-
void
increase_degree_by
(size_t)¶ Increases the degree of
this
bydeg
.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
-
Bipartition
identity
(size_t n)¶ Returns an identity bipartition.
The identity bipartition of degree \(n\) has blocks \(\{i, -i\}\) for all \(i\in \{0, \ldots, n - 1\}\). This member function returns a new identity bipartition of degree equal to
n
.
-