libsemigroups
Public Member Functions | Protected Member Functions | Friends | List of all members
libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass > Class Template Reference

Matrices over a semiring. More...

#include <elements.h>

Inheritance diagram for libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >:
Inheritance graph
Collaboration diagram for libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >:
Collaboration graph

Public Member Functions

 MatrixOverSemiringBase (std::vector< TValueType > *matrix, Semiring< TValueType > const *semiring)
 A constructor. More...
 
 MatrixOverSemiringBase (std::vector< std::vector< TValueType >> const &matrix, Semiring< TValueType > const *semiring)
 A constructor. More...
 
size_t complexity () const override
 Returns the approximate time complexity of multiplying two matrices. More...
 
size_t degree () const override
 Returns the dimension of the matrix. More...
 
Elementidentity () const override
 Returns the identity matrix with dimension of this. More...
 
Elementreally_copy (size_t increase_deg_by=0) const override
 Returns a pointer to a copy of this. More...
 
void redefine (Element const *x, Element const *y) override
 Multiply x and y and stores the result in this. More...
 
Semiring< TValueType > const * semiring () const
 Returns a pointer to the Semiring over which the matrix is defined. More...
 
- Public Member Functions inherited from libsemigroups::ElementWithVectorData< TValueType, TSubclass >
 ElementWithVectorData ()
 A constructor. More...
 
 ElementWithVectorData (std::vector< TValueType > *vector)
 A constructor. More...
 
 ElementWithVectorData (std::vector< TValueType > const &vector)
 A constructor. More...
 
TValueType at (size_t pos) const
 Returns the pos entry in the vector containing the defining data. More...
 
std::vector< TValueType >::iterator begin () const
 Returns an iterator. More...
 
std::vector< TValueType >::iterator cbegin () const
 Returns a const iterator. More...
 
std::vector< TValueType >::iterator cend () const
 Returns a const iterator. More...
 
void copy (Element const *x) override
 Copy another Element into this. More...
 
std::vector< TValueType >::iterator end () const
 Returns an iterator. More...
 
bool operator< (Element const &that) const override
 Returns true if this is less than that. More...
 
bool operator== (Element const &that) const override
 Returns true if this equals that. More...
 
TValueType operator[] (size_t pos) const
 Returns the pos entry in the vector containing the defining data. More...
 
void really_delete () override
 Deletes the defining data of an ElementWithVectorData. More...
 
void swap (Element *x) override
 Swap another Element with this. More...
 
- Public Member Functions inherited from libsemigroups::Element
 Element (elm_t type=Element::elm_t::NOT_RWSE)
 A constructor. More...
 
virtual ~Element ()
 A default destructor. More...
 
elm_t get_type () const
 Returns the type libsemigroups::Element::elm_t of an Element object. More...
 
size_t hash_value () const
 Return the hash value of an Element. More...
 
virtual void redefine (Element const *x, Element const *y, size_t const &thread_id)
 Multiplies x and y and stores the result in this. More...
 

Protected Member Functions

 MatrixOverSemiringBase (std::vector< TValueType > *matrix)
 Constructs a MatrixOverSemiringBase with whose underlying semiring is not defined. The underlying semiring must be set by any class deriving from this one. More...
 
- Protected Member Functions inherited from libsemigroups::ElementWithVectorDataDefaultHash< TValueType, TSubclass >
void cache_hash_value () const override
 This method implements the default hash function for an ElementWithVectorData, which uses ElementWithVectorData::vector_hash. Derive from this class if you are defining a class derived from ElementWithVectorData and there is a specialization of std::hash for the template parameter TValueType, and you do not want to define a hash function explicitly in your derived class. More...
 
- Protected Member Functions inherited from libsemigroups::Element
void reset_hash_value () const
 Reset the cached value used by Element::hash_value. More...
 

Friends

class ElementWithVectorData< TValueType, TSubclass >
 

Additional Inherited Members

- Public Types inherited from libsemigroups::Element
enum  elm_t { RWSE = 0, NOT_RWSE = 1 }
 This enum contains some different types of Element. More...
 
- Static Protected Member Functions inherited from libsemigroups::ElementWithVectorData< TValueType, TSubclass >
template<typename T >
static size_t vector_hash (std::vector< T > const *vec)
 Returns a hash value for a vector provided there is a specialization of std::hash for the template type T. More...
 
- Protected Attributes inherited from libsemigroups::ElementWithVectorData< TValueType, TSubclass >
std::vector< TValueType > * _vector
 The vector containing the defining data of this. More...
 
- Static Protected Attributes inherited from libsemigroups::Element
static size_t const UNDEFINED = std::numeric_limits<size_t>::max()
 UNDEFINED value. More...
 

Detailed Description

template<typename TValueType, class TSubclass>
class libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >

Matrices over a semiring.

This class is abstract since it does not implement all methods required by the Element class, it exists to provide common methods for its subclasses.

The template parameter TValueType is the type of the entries in the matrix, which must also be the type of the corresponding template parameter for the Semiring object used to define an instance of a MatrixOverSemiringBase.

The template parameter TSubclass is the type of a subclass of MatrixOverSemiringBase, and it is used so that it can be passed to ElementWithVectorData, whose method ElementWithVectorData::identity returns an instance of TSubclass.

Constructor & Destructor Documentation

§ MatrixOverSemiringBase() [1/3]

template<typename TValueType, class TSubclass>
libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::MatrixOverSemiringBase ( std::vector< TValueType > *  matrix,
Semiring< TValueType > const *  semiring 
)
inline

A constructor.

Constructs a matrix defined by matrix, matrix is not copied, and should be deleted using ElementWithVectorData::really_delete.

The parameter matrix should be a vector of integer values of length \(n ^ 2\) for some integer \(n\), so that the value in position \(in + j\) is the entry in the \(i\)th row and \(j\)th column of the constructed matrix.

The parameter semiring should be a pointer to a Semiring, which is the semiring over which the matrix is defined.

This method asserts that the paramater semiring is not a nullptr, that the vector matrix has size a non-zero perfect square.

§ MatrixOverSemiringBase() [2/3]

template<typename TValueType, class TSubclass>
libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::MatrixOverSemiringBase ( std::vector< std::vector< TValueType >> const &  matrix,
Semiring< TValueType > const *  semiring 
)
inline

A constructor.

Constructs a matrix defined by matrix, which is copied into the constructed object.

The parameter matrix should be a vector of integer values of length \(n ^ 2\) for some integer \(n\), so that the value in position \(in + j\) is the entry in the \(i\)th row and \(j\)th column of the constructed matrix.

The parameter semiring should be a pointer to a Semiring, which is the semiring over which the matrix is defined.

This method asserts that the paramater semiring is not a nullptr, that the vector matrix is not empty, and that every vector contained in matrix has the same length as matrix.

Note that it is the responsibility of the caller to delete the parameter semiring, and that this should only be done after every MatrixOverSemiringBase object that was constructed using semiring has been deleted.

§ MatrixOverSemiringBase() [3/3]

template<typename TValueType, class TSubclass>
libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::MatrixOverSemiringBase ( std::vector< TValueType > *  matrix)
inlineexplicitprotected

Constructs a MatrixOverSemiringBase with whose underlying semiring is not defined. The underlying semiring must be set by any class deriving from this one.

Member Function Documentation

§ complexity()

template<typename TValueType, class TSubclass>
size_t libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::complexity ( ) const
inlineoverridevirtual

Returns the approximate time complexity of multiplying two matrices.

The approximate time complexity of multiplying matrices is \(n ^ 3\) where \(n\) is the dimension of the matrix.

Implements libsemigroups::Element.

§ degree()

template<typename TValueType, class TSubclass>
size_t libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::degree ( ) const
inlineoverridevirtual

Returns the dimension of the matrix.

The dimension of a matrix is just the number of rows (or, equivalently columns).

Implements libsemigroups::Element.

§ identity()

template<typename TValueType, class TSubclass>
Element* libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::identity ( ) const
inlineoverridevirtual

Returns the identity matrix with dimension of this.

This method returns a new matrix with dimension equal to that of this, where the main diagonal consists of the value Semiring::one and every other entry Semiring::zero.

Implements libsemigroups::Element.

§ really_copy()

template<typename TValueType, class TSubclass>
Element* libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::really_copy ( size_t  increase_deg_by = 0) const
inlineoverridevirtual

Returns a pointer to a copy of this.

The parameter increase_deg_by must be 0, since it does not make sense to increase the degree of a matrix.

Reimplemented from libsemigroups::ElementWithVectorData< TValueType, TSubclass >.

§ redefine()

template<typename TValueType, class TSubclass>
void libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::redefine ( Element const *  x,
Element const *  y 
)
inlineoverridevirtual

Multiply x and y and stores the result in this.

This method asserts that the degrees of x, y, and this, are all equal, and that neither x nor y equals this. It does not currently verify that x, y, and this are defined over the same semiring.

Reimplemented from libsemigroups::Element.

§ semiring()

template<typename TValueType, class TSubclass>
Semiring<TValueType> const* libsemigroups::MatrixOverSemiringBase< TValueType, TSubclass >::semiring ( ) const
inline

Returns a pointer to the Semiring over which the matrix is defined.


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