Boolean matrices of arbitrary dimension¶
Overview¶
Defined in element.hpp
.
This page contains the documentation for the class template
libsemigroups::BooleanMat
.
Full API¶
-
class
BooleanMat
: public libsemigroups::detail::MatrixOverSemiringBase<bool, BooleanMat>¶ Matrices over the boolean semiring.
A boolean matrix is a square matrix over the boolean semiring, under the usual multiplication of matrices.
Every boolean matrix is defined over a single static copy of the boolean semiring.
Public Functions
-
BooleanMat
(std::vector<bool> const&)¶ A constructor.
Constructs a boolean matrix defined by
matrix
.The parameter
matrix
should be a vector of boolean values of length \(n ^ 2\) for some integer \(n\), so that the value in position \(ni + j\) is the entry in row \(i\) and column \(j\) of the constructed matrix.
-
BooleanMat
(std::vector<std::vector<bool>> const&)¶ A constructor.
Constructs a boolean matrix defined by matrix, which is copied into the constructed boolean matrix; see BooleanMat::BooleanMat for more details.
-
BooleanMat
(size_t)¶ A constructor.
Constructs a boolean matrix of the specified degree
-
BooleanMat
(BooleanMat const&)¶ A copy constructor.
-
void
redefine
(Element const&, Element const&)¶ Multiplies
x
andy
and stores the result inthis
.This member function asserts that the dimensions of
x
,y
, andthis
, are all equal, and that neitherx
nory
equalsthis
.
-
virtual void
redefine
()¶ 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
() 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.
-
virtual void
redefine
() 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 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 ofx
andy
.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
() Multiplies
x
andy
and stores the result inthis
.This member function differs from the the previous only in taking pointers instead of references.
-
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.
-
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
.
-
virtual 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.
-
virtual 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
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
.
-
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.
-
virtual void
redefine
(Element const &x, Element const &y, size_t)¶ 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 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 ofx
andy
.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
andy
and stores the result inthis
.This member function differs from the the previous only in taking pointers instead of references.
-
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.
-