BMat8 helpers¶
Defined in bmat8.hpp
.
This page contains the documentation for various helper functions for
libsemigroups::BMat8
, and HPCombi::BMat8
.
-
namespace bmat8_helpers¶
Defined in
bmat8.hpp
.! ! Class for fast boolean matrices of dimension up to 8 x 8 ! ! The member functions for these small matrices over the boolean semiring ! are more optimised than the generic member functions for boolean matrices. ! Note that all BMat8 are represented internally as an 8 x 8 matrix; ! any entries not defined by the user are taken to be 0. This does ! not affect the results of any calculations. ! ! BMat8 is a trivial class. class BMat8 final { public: ! Default constructor. ! ! There is no guarantee about the contents of the matrix constructed. ! !
! Construct from uint64_t. ! ! This constructor initializes a BMat8 to have rows equal to the ! 8 chunks, of 8 bits each, of the binary representation of
mat
. ! !
! A constructor. ! ! This constructor initializes a matrix where the rows of the matrix ! are the vectors in
mat
. ! !
! Default copy constructor. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. BMat8(BMat8 const&) noexcept = default;
- Parameters
! (None) ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. BMat8() noexcept = default;
! Default move constructor. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. BMat8(BMat8&&) noexcept = default;
! Default copy assignment operator. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. BMat8& operator=(BMat8 const&) noexcept = default;
! Default move assignment operator. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. BMat8& operator=(BMat8&&) noexcept = default;
~BMat8() = default;
! Returns
true
ifthis
equalsthat
. ! ! This member function checks the mathematical equality of two BMat8 ! objects. ! !
! Returns
true
ifthis
does not equalthat
! ! This member function checks the mathematical inequality of two BMat8 ! objects. ! !
! Returns
true
ifthis
is less thanthat
. ! ! This member function checks whether a BMat8 objects is less than ! another. We order by the results of to_int() for each matrix. ! !
! Returns
true
ifthis
is greater thanthat
. ! ! This member function checks whether a BMat8 objects is greater than ! another. We order by the results of to_int() for each matrix. ! !
! Returns the entry in the (
i
,j
)th position. ! ! This member function returns the entry in the (i
,j
)th position. ! !
TODO(later) at method
! Sets the (
i
,j
)th position toval
. ! ! This member function sets the (i
,j
)th entry ofthis
toval
. ! Uses the bit twiddle for setting bits found ! here. ! !
! Returns the integer representation of
this
. ! ! Returns an unsigned integer obtained by interpreting an 8 x 8 ! BMat8 as a sequence of 64 bits (reading rows left to right, ! from top to bottom) and then realising this sequence as an unsigned ! int. ! !
! Returns the transpose of
this
. ! ! Uses the technique found in Knu09. ! !
! Returns the matrix product of
this
andthat
! ! This member function returns the standard matrix product (over the ! boolean semiring) of two BMat8 objects. ! Uses the technique given here. ! !! Insertion operator ! ! This member function allows BMat8 objects to be inserted into an ! std::ostringstream. friend std::ostringstream& operator<<(std::ostringstream& os,
BMat8 const& bm);
- Parameters
! (None) inline uint64_t to_int() const noexcept { return _data; }
- Parameters
! (None) inline BMat8 transpose() const noexcept { uint64_t x = _data; uint64_t y = (x ^ (x >> 7)) & 0xAA00AA00AA00AA; x = x ^ y ^ (y << 7); y = (x ^ (x >> 14)) & 0xCCCC0000CCCC; x = x ^ y ^ (y << 14); y = (x ^ (x >> 28)) & 0xF0F0F0F0; x = x ^ y ^ (y << 28); return BMat8(x); }
! Insertion operator ! ! This member function allows BMat8 objects to be inserted into a ! std::ostream. friend std::ostream& operator<<(std::ostream& os, BMat8 const& bm) { os << detail::to_string(bm); return os; }
! Construct a random BMat8. ! ! This static member function returns a BMat8 chosen at random. ! !
! Construct a random BMat8 of dimension at most
dim
. ! ! This static member function returns a BMat8 chosen at random, where ! only the top-leftdim
xdim
entries can be non-zero. ! !
! Swaps
this
withthat
. ! ! This member function swaps the values ofthis
andthat
. ! !
! Find a basis for the row space of
this
. ! ! This member function returns a BMat8 whose non-zero rows form a basis ! for the row space ofthis
. ! !
! Find a basis for the column space of
this
. ! ! This member function returns a BMat8 whose non-zero columns form a basis ! for the column space ofthis
. ! !
! Returns a vector containing the rows of
this
! ! This member function returns a std::vector of uint8_ts representing the ! rows ofthis
. The vector will always be of length 8, even ifthis
! was constructed with fewer rows. ! !
! Find the size of the row space of
this
. ! !
! Returns the number of non-zero rows in
this
. ! ! BMat8s do not know their “dimension” - in effect they are all of ! dimension 8. However, this member function can be used to obtain the ! number of non-zero rows ofthis
. ! !
! Check whether
this
is a regular element of the full boolean matrix ! monoid of appropriate dimension. ! !
! Returns the identity BMat8. ! ! This member function returns the BMat8 with the first
dim
entries in ! the main diagonal equal to1
and every other value equal to0
. ! !
private: void sort_rows() noexcept;
See also
bmat8_helpers::col_space_size. size_t row_space_size() const;
See also
bmat8_helpers::number_of_cols and bmat8_helpers::minimum_dim. size_t number_of_rows() const noexcept { size_t count = 0; for (size_t i = 0; i < 8; ++i) { if (_data << (8 * i) >> 56 > 0) { count++; } } return count; }
- Parameters
! (None) Not noexcept since std::uniform_int_distribution::operator() is not noexcept. static BMat8 random() { return BMat8(_dist(_gen)); }
- Parameters
! (None) Not noexcept since std::uniform_int_distribution::operator() is not noexcept. static BMat8 random(size_t dim);
- Parameters
! (None) BMat8 row_space_basis() const noexcept;
- Parameters
! (None) BMat8 col_space_basis() const noexcept { return this->transpose().row_space_basis().transpose(); }
- Parameters
! (None) TODO(later) make this return an array instead of a vector std::vector<uint8_t> rows() const;
- Parameters
! (None) ! !
- Parameters
! (None) ! !
- Parameters
! (None) bool is_regular_element() const noexcept { return *this BMat8( ~(*this * BMat8(~_data).transpose() * (*this)).to_int()) .transpose() (*this) == *this; }
uint64_t _data; static std::random_device _rd; static std::mt19937 _gen; static std::uniform_int_distribution<uint64_t> _dist; };
static_assert(std::is_trivial<BMat8>(), “BMat8 is not a trivial class!”);
! Defined in
bmat8.hpp
. This namespace contains various helper functions for the class BMat8. These functions could be member functions of BMat8 but they only use public member functions of BMat8, and so they are declared as free functions instead.Note
! Note that since all matrices are internally represented as 8 x 8, it ! is possible to access entries that you might not believe exist. ! !
Warning
! No checks on the parameters
i
andj
are performed, ifi
or!
j is greater than 7, then bad things will happen. bool get(size_t i, size_t j) const noexcept { LIBSEMIGROUPS_ASSERT(i < 8); LIBSEMIGROUPS_ASSERT(j < 8); return (_data << (8 * i + j)) >> 63; }- Param mat:
the integer representation of the matrix being constructed. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. explicit BMat8(uint64_t mat) noexcept : _data(mat) {}
- Param mat:
the vector of vectors representation of the matrix being ! constructed. ! !
- Throws LibsemigroupsException:
if
mat
has 0 rows. !- Throws LibsemigroupsException:
if
mat
has more than 8 rows. !- Throws LibsemigroupsException:
if the rows of
mat
are not all of the ! same length. ! ! \complexity ! Constant. explicit BMat8(std::vector<std::vector<bool>> const& mat);- Param that:
the BMat8 for comparison. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. bool operator==(BMat8 const& that) const noexcept { return _data == that._data; }
- Param that:
the BMat8 for comparison. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. bool operator!=(BMat8 const& that) const noexcept { return _data != that._data; }
- Param that:
the BMat8 for comparison. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. bool operator<(BMat8 const& that) const noexcept { return _data < that._data; }
- Param that:
the BMat8 for comparison. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. bool operator>(BMat8 const& that) const noexcept { return _data > that._data; }
- Param i:
the row of the entry sought. !
- Param j:
the column of the entry sought. ! !
- Return:
! A
bool
. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. ! !- Param i:
the row !
- Param j:
the column !
- Param val:
the value to set in position (
i
,j
)th ! !- Throws LibsemigroupsException:
if
i
orj
is out of bounds. ! ! \complexity ! Constant. void set(size_t i, size_t j, bool val);- Param that:
the matrix we want to multiply by
this
. ! !- Return:
! (None) ! !
- Return:
! A
uint64_t
. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. ! !- Return:
! A BMat8. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. ! !
- Return:
! A BMat8. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. BMat8 operator*(BMat8 const& that) const noexcept;
- Param that:
the BMat8 to swap
this
with. ! !- Param dim:
the dimension of the identity (default: 8) ! !
- Return:
! A BMat8. ! ! \exceptions ! \no_libsemigroups_except ! !
- Return:
! A BMat8. ! ! \exceptions ! \no_libsemigroups_except ! !
- Return:
! (None) ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. inline void swap(BMat8& that) noexcept { std::swap(this->_data, that._data); }
- Return:
! A BMat8. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. ! !
- Return:
! A BMat8. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. ! !
- Return:
! A std::vector<uint8_t>. ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! Constant. ! !
- Return:
! A
size_t
. ! ! \exceptions ! \no_libsemigroups_except ! ! \complexity ! \(O(n)\) where \(n\) is the return value of this function. ! !- Return:
! A
size_t
. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. ! !- Return:
! A
true
if there exists a boolean matrixy
such that `x * y * x = x` wherex
is*this
. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. ! !- Return:
! A BMat8. ! ! \exceptions ! \noexcept ! ! \complexity ! Constant. static BMat8 one(size_t dim = 8) noexcept { return bmat8_helpers::one<BMat8>(dim); }
Functions
-
template<typename T>
T one(size_t dim) noexcept¶ Returns the identity boolean matrix of a given dimension.
See also
BMat8::one.
- Complexity
Constant.
- Template Parameters:
T – the type of the boolean matrix being constructed, should be BMat8 or HPCombi::BMat8.
- Parameters:
dim – the dimension of the identity matrix, must be at most 7.
- Throws:
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns:
A value of type
T
with the firstdim
values on the main diagonal equal to 1 and every other entry equal to 0.
-
static inline size_t number_of_cols(BMat8 const &x) noexcept¶
Returns the number of non-zero columns in
x
.BMat8s do not know their “dimension” - in effect they are all of dimension 8. However, this member function can be used to obtain the number of non-zero rows of
this
.See also
BMat8::number_of_rows and bmat8_helpers::minimum_dim.
- Complexity
Constant.
- Parameters:
x – the BMat8 whose number of columns we want.
- Throws:
(None) – This function is
noexcept
and is guaranteed never to throw.- Returns:
A
size_t
.
-
static inline size_t col_space_size(BMat8 const &x)¶
Find the size of the column space of
x
.See also
BMat8::row_space_size.
- Complexity
\(O(n)\) where \(n\) is the return value of this function.
- Parameters:
x – a BMat8.
- Throws:
(None) – This function guarantees not to throw a
LibsemigroupsException
.- Returns:
A
size_t
.
-
size_t minimum_dim(BMat8 const &x) noexcept¶
Find the minimum dimension of
x
.This member function returns the maximal
i
such that rowi
or columni
contains a1
.- Complexity
Constant.
- Parameters:
x – a BMat8.
- Throws:
(None) – This function is
noexcept
and is guaranteed never to throw.