libsemigroups  v3.0.0
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
DynamicMatrix< Semiring, Scalar >
template<typename Semiring, typename Scalar>
class libsemigroups::DynamicMatrix< Semiring, Scalar >

Defined in matrix.hpp.

This is a class for matrices where both the arithmetic operations in the underlying semiring and the dimensions of the matrix can be set at run time.

Template Parameters
Semiringthe type of a semiring object which defines the semiring arithmetic (see requirements below).
Scalarthe type of the entries in the matrices (the type of elements in the underlying semiring).
Note
Certain member functions only work for square matrices and some only work for rows.

Semiring requirements

The template parameter Semiring must have the following member functions:

  • scalar_type scalar_zero() that returns the multiplicative zero scalar in the semiring
  • scalar_type scalar_one() that returns the multiplicative identity scalar in the semiring
  • scalar_type plus_no_checks(scalar_type x, scalar_type y) that returns the sum in the semiring of the scalars x and y.
  • scalar_type product_no_checks(scalar_type x, scalar_type y) that returns the product in the semiring of the scalars x and y.

See, for example, MaxPlusTruncSemiring.

Public Types

using Row = DynamicMatrix
 Alias for the type of the rows of a DynamicMatrix.
 
using RowView = DynamicRowView<Semiring, Scalar>
 Alias for the type of row views of a DynamicMatrix.
 
using scalar_const_reference = typename MatrixCommon::scalar_const_reference
 Alias for const references to the template parameter Scalar.
 
using scalar_reference = typename MatrixCommon::scalar_reference
 Alias for references to the template parameter Scalar.
 
using scalar_type = typename MatrixCommon::scalar_type
 Alias for the template parameter Scalar.
 
using semiring_type = Semiring
 Alias for the template parameter Semiring.
 

Public Member Functions

 DynamicMatrix ()=delete
 Deleted.
 
 DynamicMatrix (DynamicMatrix &&)=default
 Default move constructor.
 
 DynamicMatrix (DynamicMatrix const &)=default
 Default copy constructor.
 
 DynamicMatrix (RowView const &rv)
 Construct a row over a given semiring (RowView).
 
 DynamicMatrix (Semiring const *sr, size_t r, size_t c)
 Construct a matrix over a given semiring with given dimensions.
 
 DynamicMatrix (Semiring const *sr, std::initializer_list< scalar_type > const &rw)
 Construct a row over a given semiring (std::initializer_list).
 
 DynamicMatrix (Semiring const *sr, std::initializer_list< std::initializer_list< scalar_type > > const &rws)
 Construct a matrix over a given semiring (std::initializer_list of std::initializer_list).
 
 DynamicMatrix (Semiring const *sr, std::vector< std::vector< scalar_type > > const &rws)
 Construct a matrix over a given semiring (std::vector of std::vector).
 
scalar_reference at (size_t r, size_t c)
 Returns a reference to the specified entry of the matrix.
 
scalar_reference at (size_t r, size_t c) const
 Returns a const reference to the specified entry of the matrix.
 
iterator begin () noexcept
 Returns an iterator pointing at the first entry.
 
const_iterator cbegin () noexcept
 Returns a const iterator pointing at the first entry.
 
const_iterator cend () noexcept
 Returns a const iterator pointing one beyond the last entry in the matrix.
 
std::pair< scalar_type, scalar_typecoords (const_iterator it) const
 Get the coordinates of an iterator.
 
iterator end () noexcept
 Returns an iterator pointing one beyond the last entry in the matrix.
 
size_t hash_value () const
 Return a hash value of a matrix.
 
size_t number_of_cols () const noexcept
 Returns the number of columns of the matrix.
 
size_t number_of_rows () const noexcept
 Returns the number of rows of the matrix.
 
bool operator!= (DynamicMatrix const &that) const
 Inequality operator.
 
bool operator!= (RowView const &that) const
 Inequality operator.
 
scalar_reference operator() (size_t r, size_t c)
 Returns a reference to the specified entry of the matrix.
 
scalar_const_reference operator() (size_t r, size_t c) const
 Returns a const reference to the specified entry of the matrix.
 
DynamicMatrix operator* (DynamicMatrix const &that)
 Returns the product of two matrices.
 
DynamicMatrix operator* (scalar_type a)
 Multiplies every entry of a matrix by a scalar in-place.
 
void operator*= (scalar_type a)
 Multiplies every entry of a matrix by a scalar in-place.
 
DynamicMatrix operator+ (DynamicMatrix const &that)
 Returns the sum of two matrices.
 
void operator+= (DynamicMatrix const &that)
 Add a matrix to another matrix in-place.
 
void operator+= (RowView const &that)
 Add a matrix to another matrix in-place.
 
void operator+= (scalar_type a)
 Adds a scalar to every entry of the matrix in-place.
 
bool operator< (DynamicMatrix const &that) const
 Less than operator.
 
bool operator< (RowView const &that) const
 Less than operator.
 
template<typename T>
bool operator<= (T const &that) const
 Less than or equal operator.
 
DynamicMatrixoperator= (DynamicMatrix &&)=default
 Default move assignment operator.
 
DynamicMatrixoperator= (DynamicMatrix const &)=default
 Default copy assignment operator.
 
bool operator== (DynamicMatrix const &that) const
 Equality operator.
 
bool operator== (RowView const &that) const
 Equality operator.
 
bool operator> (DynamicMatrix const &that) const
 Greater than operator.
 
template<typename T>
bool operator>= (T const &that) const
 Greater than or equal operator.
 
void product_inplace_no_checks (DynamicMatrix const &x, DynamicMatrix const &y)
 Multiplies x and y and stores the result in this.
 
RowView row (size_t i) const
 Returns a view into a row.
 
RowView row_no_checks (size_t i) const
 Returns a view into a row.
 
template<typename T>
void rows (T &x) const
 Add row views for every row in the matrix to a container.
 
scalar_type scalar_one () const noexcept
 Returns the multiplicative identity of the underlying semiring.
 
scalar_type scalar_zero () const noexcept
 Returns the additive identity of the underlying semiring.
 
semiring_type const * semiring () const noexcept
 Returns the underlying semiring.
 
void swap (DynamicMatrix &that) noexcept
 Swaps the contents of *this with the contents of that.
 
void transpose ()
 Transpose a matrix in-place.
 
void transpose_no_checks ()
 Transpose a matrix in-place.
 

Static Public Member Functions

static DynamicMatrix one (Semiring const *semiring, size_t n)
 Construct the \(n \times n\) identity matrix.
 

Constructor & Destructor Documentation

◆ DynamicMatrix() [1/8]

template<typename Semiring, typename Scalar>
DynamicMatrix ( )
delete

The default constructor for this variant of DynamicMatrix is deleted because a valid semiring object is required to define the arithmetic at run-time.

◆ DynamicMatrix() [2/8]

template<typename Semiring, typename Scalar>
DynamicMatrix ( DynamicMatrix< Semiring, Scalar > const & )
default

Default copy constructor.

◆ DynamicMatrix() [3/8]

template<typename Semiring, typename Scalar>
DynamicMatrix ( DynamicMatrix< Semiring, Scalar > && )
default

Default move constructor.

◆ DynamicMatrix() [4/8]

template<typename Semiring, typename Scalar>
DynamicMatrix ( Semiring const * sr,
size_t r,
size_t c )
inline

Construct a matrix over the semiring semiring with the given dimensions.

Parameters
sra pointer to const semiring object.
rthe number of rows in the matrix being constructed.
cthe number of columns in the matrix being constructed.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
Constant

◆ DynamicMatrix() [5/8]

template<typename Semiring, typename Scalar>
DynamicMatrix ( Semiring const * sr,
std::initializer_list< std::initializer_list< scalar_type > > const & rws )
inlineexplicit

This function constructs a matrix over a given semiring from an std::initializer_list of the rows (std::initializer_list).

Parameters
sra pointer to const semiring object.
rwsthe values to be copied into the matrix.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(n\) is number_of_cols.

◆ DynamicMatrix() [6/8]

template<typename Semiring, typename Scalar>
DynamicMatrix ( Semiring const * sr,
std::vector< std::vector< scalar_type > > const & rws )
inlineexplicit

This function constructs a matrix over a given semiring from an std::vector of the rows (std::vector).

Parameters
sra pointer to const semiring object.
rwsthe values to be copied into the matrix.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(n\) is number_of_cols.

◆ DynamicMatrix() [7/8]

template<typename Semiring, typename Scalar>
DynamicMatrix ( Semiring const * sr,
std::initializer_list< scalar_type > const & rw )
inlineexplicit

Construct a row over a given semiring from a std::initializer_list of the entries.

Parameters
sra pointer to const Semiring object.
rwthe values to be copied into the row.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
\(O(mn)\) where \(m\) is number_of_cols.

◆ DynamicMatrix() [8/8]

template<typename Semiring, typename Scalar>
DynamicMatrix ( RowView const & rv)
inlineexplicit

Construct a row over a given semiring from a RowView.

Parameters
rvthe row view.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
\(O(n)\) where \(n\) is the size of the row being constructed.

Member Function Documentation

◆ at() [1/2]

template<typename Semiring, typename Scalar>
scalar_reference at ( size_t r,
size_t c )

Returns a reference to the specified entry of the matrix.

Parameters
rthe index of the row of the entry.
cthe index of the column of the entry.
Returns
A value of type scalar_reference.
Exceptions
LibsemigroupsExceptionif r or c is out of bounds.
Complexity
Constant

◆ at() [2/2]

template<typename Semiring, typename Scalar>
scalar_reference at ( size_t r,
size_t c ) const

Returns a const reference to the specified entry of the matrix.

Parameters
rthe index of the row of the entry.
cthe index of the column of the entry.
Returns
A value of type scalar_const_reference.
Exceptions
LibsemigroupsExceptionif r or c is out of bounds.
Complexity
Constant

◆ begin()

template<typename Semiring, typename Scalar>
iterator begin ( )
noexcept

This function returns a random access iterator point at the first entry of the matrix.

Returns
A value of type iterator.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
Constant
Warning
The order in which entries in the matrix are iterated over is not specified.

◆ cbegin()

template<typename Semiring, typename Scalar>
const_iterator cbegin ( )
noexcept

This function returns a const (random access) iterator pointing at the first entry in the matrix.

Returns
A value of type const_iterator.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
Constant
Warning
The order in which entries in the matrix are iterated over is not specified.

◆ cend()

template<typename Semiring, typename Scalar>
const_iterator cend ( )
noexcept

This function returns a const (random access) iterator pointing one passed the last entry of the matrix.

Returns
A value of type const_iterator.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
Constant
Warning
The order in which entries in the matrix are iterated over is not specified.

◆ coords()

template<typename Semiring, typename Scalar>
std::pair< scalar_type, scalar_type > coords ( const_iterator it) const

This function returns a pair containing the row and columns corresponding to a const_iterator pointing into a matrix.

Parameters
itthe const_iterator.
Returns
A value of type std::pair<scalar_type, scalar_type>.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
Constant

◆ end()

template<typename Semiring, typename Scalar>
iterator end ( )
noexcept
Returns
A value of type iterator.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
Constant
Warning
The order in which entries in the matrix are iterated over is not specified.

◆ hash_value()

template<typename Semiring, typename Scalar>
size_t hash_value ( ) const

This function returns a hash value for a matrix. The return value is recomputed every time this function is called.

Returns
A hash value for a this.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
\(O(mn)\) where \(m\) is the number_of_rows and \(n\) is number_of_cols.

◆ number_of_cols()

template<typename Semiring, typename Scalar>
size_t number_of_cols ( ) const
noexcept

This function returns the number of columns of the matrix.

Returns
A value of type size_t.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
Constant

◆ number_of_rows()

template<typename Semiring, typename Scalar>
size_t number_of_rows ( ) const
noexcept

This function returns the number of rows of the matrix.

Returns
A value of type size_t.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
Constant

◆ one()

template<typename Semiring, typename Scalar>
static DynamicMatrix one ( Semiring const * semiring,
size_t n )
inlinestatic

Construct the \(n \times n\) identity matrix.

Parameters
semiringthe semiring.
nthe dimension.
Returns
The \(n \times n\) identity matrix over semiring.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
\(O(n ^ 2)\).

◆ operator!=() [1/2]

template<typename Semiring, typename Scalar>
bool operator!= ( DynamicMatrix< Semiring, Scalar > const & that) const

This function returns true if *this is not equal to that; and false otherwise.

Parameters
thatthe matrix or row view for comparison.
Returns
The negation of operator==(that).
Complexity
see operator==

◆ operator!=() [2/2]

template<typename Semiring, typename Scalar>
bool operator!= ( RowView const & that) const

This function returns true if *this is not equal to that; and false otherwise.

Parameters
thatthe matrix or row view for comparison.
Returns
The negation of operator==(that).
Complexity
see operator==

◆ operator()() [1/2]

template<typename Semiring, typename Scalar>
scalar_reference operator() ( size_t r,
size_t c )

Returns a reference to the specified entry of the matrix.

Parameters
rthe index of the row of the entry.
cthe index of the column of the entry.
Returns
A value of type scalar_reference.
Exceptions
this function guarantees not to throw a LibsemigroupsException.
Complexity
Constant
Warning
No checks on the validity of the parameters r and c are performed.

◆ operator()() [2/2]

template<typename Semiring, typename Scalar>
scalar_const_reference operator() ( size_t r,
size_t c ) const

Returns a const reference to the specified entry of the matrix.

Parameters
rthe index of the row of the entry.
cthe index of the column of the entry.
Returns
A value of type scalar_const_reference.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
Constant
Warning
No checks on the validity of the parameters r and c are performed.

◆ operator*() [1/2]

template<typename Semiring, typename Scalar>
DynamicMatrix operator* ( DynamicMatrix< Semiring, Scalar > const & that)

This function returns the product of two matrices.

Parameters
thatthe matrix to multiply by this.
Returns
The product of the two matrices.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(m\) is number_of_cols.
Warning
The matrices must be of the same dimensions, although this is not verified.
This function does not detect overflows of scalar_type.

◆ operator*() [2/2]

template<typename Semiring, typename Scalar>
DynamicMatrix operator* ( scalar_type a)

This function multiplies every entry of a matrix by a scalar in-place.

Parameters
athe scalar to multiply every entry by.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(m\) is number_of_cols.
Warning
This function does not detect overflows of scalar_type.

◆ operator*=()

template<typename Semiring, typename Scalar>
void operator*= ( scalar_type a)

This function multiplies every entry of a matrix by a scalar in-place.

Parameters
athe scalar to multiply every entry by.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(m\) is number_of_cols.
Warning
This function does not detect overflows of scalar_type.

◆ operator+()

template<typename Semiring, typename Scalar>
DynamicMatrix operator+ ( DynamicMatrix< Semiring, Scalar > const & that)

This function returns the sum of two matrices.

Parameters
thatthe matrix to add to this.
Returns
The sum of the two matrices.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(m\) number_of_cols
Warning
The matrices must be of the same dimensions, although this is not verified.
This function does not detect overflows of scalar_type.

◆ operator+=() [1/3]

template<typename Semiring, typename Scalar>
void operator+= ( DynamicMatrix< Semiring, Scalar > const & that)

This function adds a matrix (or the row represented by a RowView) to another matrix of the same shape in-place.

Parameters
thatthe matrix or row view to add.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(m\) is number_of_cols
Warning
The matrices must be of the same dimensions, although this is not checked.
This function does not detect overflows of scalar_type.

◆ operator+=() [2/3]

template<typename Semiring, typename Scalar>
void operator+= ( RowView const & that)

This function adds a matrix (or the row represented by a RowView) to another matrix of the same shape in-place.

Parameters
thatthe matrix or row view to add.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(m\) is number_of_cols
Warning
The matrices must be of the same dimensions, although this is not checked.
This function does not detect overflows of scalar_type.

◆ operator+=() [3/3]

template<typename Semiring, typename Scalar>
void operator+= ( scalar_type a)

This function adds a scalar to every entry of the matrix in-place.

Parameters
athe scalar_type to add to a DynamicMatrix.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(m\) is number_of_cols
Warning
This function does not detect overflows of scalar_type.

◆ operator<() [1/2]

template<typename Semiring, typename Scalar>
bool operator< ( DynamicMatrix< Semiring, Scalar > const & that) const

This operator defines a total order on the set of matrices of the same type.

Parameters
thatthe matrix or row view for comparison.
Returns
true if *this is less than that and false if it is not.
Complexity
At worst \(O(mn)\) where \(m\) is number_of_rows and \(n\) is number_of_cols.

◆ operator<() [2/2]

template<typename Semiring, typename Scalar>
bool operator< ( RowView const & that) const

This operator defines a total order on the set of matrices of the same type.

Parameters
thatthe matrix or row view for comparison.
Returns
true if *this is less than that and false if it is not.
Complexity
At worst \(O(mn)\) where \(m\) is number_of_rows and \(n\) is number_of_cols.

◆ operator<=()

template<typename Semiring, typename Scalar>
template<typename T>
bool operator<= ( T const & that) const

This operator defines a total order on the set of matrices of the same type.

Template Parameters
Uthe type of the argument that.
Parameters
thatthe matrix or row view for comparison.
Returns
true if *this is less than or equal to that and false if it is not.
Complexity
At worst \(O(mn)\) where \(m\) is number_of_rows and \(n\) is number_of_cols.

◆ operator=() [1/2]

template<typename Semiring, typename Scalar>
DynamicMatrix & operator= ( DynamicMatrix< Semiring, Scalar > && )
default

Default move assignment operator.

◆ operator=() [2/2]

template<typename Semiring, typename Scalar>
DynamicMatrix & operator= ( DynamicMatrix< Semiring, Scalar > const & )
default

Default copy assignment operator.

◆ operator==() [1/2]

template<typename Semiring, typename Scalar>
bool operator== ( DynamicMatrix< Semiring, Scalar > const & that) const

This function returns true if *this is equal to that; and false otherwise.

Parameters
thatmatrix or row view for comparison.
Returns
true if *this and that are equal and false if they are not.
Complexity
At worst \(O(mn)\) where \(m\) is the number of rows and \(n\) is the number of columns of the matrix.

◆ operator==() [2/2]

template<typename Semiring, typename Scalar>
bool operator== ( RowView const & that) const

This function returns true if *this is equal to that; and false otherwise.

Parameters
thatmatrix or row view for comparison.
Returns
true if *this and that are equal and false if they are not.
Complexity
At worst \(O(mn)\) where \(m\) is the number of rows and \(n\) is the number of columns of the matrix.

◆ operator>()

template<typename Semiring, typename Scalar>
bool operator> ( DynamicMatrix< Semiring, Scalar > const & that) const

This operator defines a total order on the set of matrices of the same type.

Parameters
thatthe matrix for comparison.
Returns
true if *this is less than that and false if it is not.
Complexity
At worst \(O(mn)\) where \(m\) is number_of_rows and \(m\) is number_of_cols

◆ operator>=()

template<typename Semiring, typename Scalar>
template<typename T>
bool operator>= ( T const & that) const

This operator defines a total order on the set of matrices of the same type.

Template Parameters
Uthe type of the argument that.
Parameters
thatthe matrix or row view for comparison.
Returns
true if *this is greater than or equal to that and false if it is not.
Complexity
At worst \(O(mn)\) where \(m\) is number_of_rows and \(n\) is number_of_cols.

◆ product_inplace_no_checks()

template<typename Semiring, typename Scalar>
void product_inplace_no_checks ( DynamicMatrix< Semiring, Scalar > const & x,
DynamicMatrix< Semiring, Scalar > const & y )

This function redefines this to be the product of x and y. This is in-place multiplication to avoid allocation of memory for products which do not need to be stored for future use.

Parameters
xthe first matrix to multiply.
ythe second matrix to multiply.
Complexity
\(O(n ^ 3)\) where \(n\) is number_of_rows or number_of_cols.
Warning
This function only applies to matrices with the same number of rows and columns but this isn't verified.

◆ row()

template<typename Semiring, typename Scalar>
RowView row ( size_t i) const

This function returns a RowView into the row with index i.

Parameters
ithe index of the row.
Returns
A value of type RowView.
Exceptions
LibsemigroupsExceptionif i is greater than or equal to number_of_rows.

◆ row_no_checks()

template<typename Semiring, typename Scalar>
RowView row_no_checks ( size_t i) const

This function returns a RowView into the row with index i.

Parameters
ithe index of the row.
Returns
A value of type RowView.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
Constant
Warning
No checks are made on the argument i.

◆ rows()

template<typename Semiring, typename Scalar>
template<typename T>
void rows ( T & x) const

This function adds a RowView for each row in the matrix to the container x.

Template Parameters
Tthe type of the container.
Parameters
xa container.
Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
\(O(m)\) where \(m\) is the template parameter R.

◆ scalar_one()

template<typename Semiring, typename Scalar>
scalar_type scalar_one ( ) const
noexcept

This function returns the multiplicative identity of the underlying semiring of a matrix.

Returns
The multiplicative identity of the semiring, a scalar_type.
Exceptions
This function is noexcept and is guaranteed never to throw.

◆ scalar_zero()

template<typename Semiring, typename Scalar>
scalar_type scalar_zero ( ) const
noexcept

This function returns the additive identity of the underlying semiring of a matrix.

Returns
The additive identity of the semiring, a scalar_type.
Exceptions
This function is noexcept and is guaranteed never to throw.

◆ semiring()

template<typename Semiring, typename Scalar>
semiring_type const * semiring ( ) const
noexcept

Returns a const pointer to the underlying semiring (if any).

Returns
A value of type Semiring const*.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
Constant

◆ swap()

template<typename Semiring, typename Scalar>
void swap ( DynamicMatrix< Semiring, Scalar > & that)
inlinenoexcept

This function swaps the contents of *this with the contents of that.

Parameters
thatthe matrix to swap contents with.
Exceptions
This function is noexcept and is guaranteed never to throw.
Complexity
Constant

◆ transpose()

template<typename Semiring, typename Scalar>
void transpose ( )

This function transpose a matrix object in-place.

Exceptions
This function guarantees not to throw a LibsemigroupsException.
Exceptions
LibsemigroupsExceptionif the matrix isn't square.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(n\) is number_of_cols.

◆ transpose_no_checks()

template<typename Semiring, typename Scalar>
void transpose_no_checks ( )

This function transpose a matrix object in-place.

Exceptions
This function guarantees not to throw a LibsemigroupsException.
Complexity
\(O(mn)\) where \(m\) is number_of_rows and \(n\) is number_of_cols.
Warning
This only works when number_of_rows and number_of_cols are equal (i.e. for square matrices), but this is not verified.

The documentation for this class was generated from the following file: