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 if this equals that

. ! ! This member function checks the mathematical equality of two BMat8 ! objects. ! !

! Returns

true if this does not equal that

! ! This member function checks the mathematical inequality of two BMat8 ! objects. ! !

! Returns

true if this is less than that

. ! ! 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 if this is greater than that

. ! ! 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 to val. ! ! This member function sets the (i, j)th entry of this to val. ! 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 and that ! ! 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-left dim x dim

entries can be non-zero. ! !

! Swaps

this with that. ! ! This member function swaps the values of this and that

. ! !

! 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 of this

. ! !

! 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 of this

. ! !

! Returns a vector containing the rows of

this ! ! This member function returns a std::vector of uint8_ts representing the ! rows of this. The vector will always be of length 8, even if this

! 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 of this

. ! !

! 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 to 1 and every other value equal to 0

. ! !

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 and j are performed, if i 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 or j 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 matrix y such that `x * y * x = x` where x 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 first dim 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 row i or column i contains a 1.

Complexity

Constant.

Parameters:

x – a BMat8.

Throws:

(None) – This function is noexcept and is guaranteed never to throw.