bitset_row_basis

This page contains details of the function templates for finding the row basis of a boolean matrix represented as bitsets that belong to the namespace matrix_helper.

template<typename Mat, typename Container>
void bitset_row_basis(Container &&rows, std::decay_t<Container> &result)

Appends a basis for the space spanned by the bitsets in rows to the container result.

Template Parameters

• Mat – a type such that IsBMat<Mat> is true.

• Container – a container type (such as detail::StaticVector1, for example). The Container::value_type must be BitSet<M> or std::bitset<M> for some M.

Parameters

• rows – container of spanning rows represented by bitsets.

• result – container for the resulting rowbasis

Returns

(None)

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

\(O(r ^ 2 c)\) where \(r\) is the size of rows and \(c\) is the size of each bitset in rows.

Helper functions

template<typename Mat, typename Container>
std::decay_t<Container> bitset_row_basis(Container &&rows)

Returns a basis for the space spanned by the bitsets in rows.

Template Parameters

• Mat – a type such that IsBMat<Mat> is true.

• Container – a container type (such as detail::StaticVector1, for example). The Container::value_type must be BitSet<M> or std::bitset<M> for some M.

Parameters

rows – container of spanning rows represented by bitsets.

Returns

A container of type std::decay_t<Container> containing the row basis consisting of bitsets.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

\(O(r ^ 2 c)\) where \(r\) is the size of rows and \(c\) is the size of each bitset in rows.

template<typename Mat, size_t M = detail::BitSetCapacity<Mat>::value>
detail::StaticVector1<BitSet<M>, M> bitset_row_basis(Mat const &x)

Returns a basis for the space spanned by the rows of the boolean matrix x.

Template Parameters

• Mat – a type such that IsBMat<Mat> is true.

• M – an upper bound for the dimensions of the returned container. If IsStaticMatrix<Mat> is true, then M is the number of rows (or columns) in the square matrix x. Otherwise, if IsDynamicMatrix<Mat> is true, then M is BitSet<1>::max_size.

Parameters

x – the boolean matrix.

Returns

A container of type detail::StaticVector1<BitSet<M>, M>> containing the row basis of x consisting of bitsets.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

\(O(r ^ 2 c)\) where \(r\) is the number of rows in x and \(c\) is the number of columns in x.

template<typename Mat, typename Container>
void bitset_row_basis(Mat const &x, Container &result)

Appends a basis for the rowspace of the boolean matrix x to the container result.

Template Parameters

• Mat – a type such that IsBMat<Mat> is true.

• Container – a container type (such as detail::StaticVector1, for example). The Container::value_type must be BitSet<M> or std::bitset<M> for some M.

Parameters

• x – the boolean matrix.

• result – container for the resulting rowbasis

Returns

(None)

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

\(O(r ^ 2 c)\) where \(r\) is the number of rows in x and \(c\) is the number of columns in x.