Rank¶
This page contains details of the specialisations of the adapters
Rank and RankState for boolean matrices.
-
template<typename Mat>
class RankState<Mat>¶ This class is a specialization of the adapter
RankState()for instances ofBMat. TheRankState()is used as part of the computation of the rank of a boolean matrix inRankwhich is used byKonieczny.- Template Parameters
Mat – a type such that
IsBMatistrue.
-
using MaxBitSet = BitSet<BitSet<1>::max_size()>¶
Type of the maximum possible size of
BitSet.
-
using type = RightAction<Mat, MaxBitSet, ImageRightAction<Mat, MaxBitSet>>¶
The type of additional data used by
Rank: the right action consisting of all possible rows of matrices belonging to the underlying semigroup.
-
RankState() = default¶
Default constructor. The other standard constructors (copy constructor, move constructor, etc) are deleted.
-
template<typename T>
RankState(T first, T last)¶ Construct from const iterators to the generators of the semigroup.
- Template Parameters
T – type of const iterators to the generators of the semigroup
- Parameters
first – const iterator to the first generator
last – const iterator pointing one passed the last generator
- Throws
LibsemigroupsExceptionif the distance betweenfirstandlastis0.
-
type const &get() const¶
Returns the fully enumerated row orbit.
- Parameters
(None)
- Returns
A const reference to the fully enumerated row orbit, a value of type
type.- Complexity
\(O(mn)\) where \(m\) is the number of generators added at the time of construction (i.e.
std::distance(first, last)) and \(n\) is the size of the fully enumerated row orbit.
-
template<typename Mat>
struct Rank<Mat, RankState<Mat>>¶ Specialization of the adapter
Rankfor instances ofBMat.- Template Parameters
Mat – a type such that
IsBMatistrue.
-
size_t operator()(RankState<Mat> const &state, Mat const &x) const¶
Returns the rank of
x.- Parameters
state – a const reference to the RankState<Mat>
x – the matrix
- Returns
the rank of the parameter
x, which is a value of typesize_t.- Complexity
The first call has complexity at worst \(O(mn)\) where \(m\) is the number of generators added at the time of construction (i.e.
std::distance(first, last)) and \(n\) is the size of the fully enumerated row orbit, subsequent calls have constant complexity.