Truncated max-plus matrices

Defined in matrix.hpp.

This page describes the functionality for \(n \times n\) matrices over the finite quotient of the max-plus semiring by the congruence \(t = t + 1\) for arbitrary \(n\) and \(t\). The value \(t\) is referred to as the threshold.

There are three types of such matrices where:

1. the dimension is known at compile-time;
2. the dimension is to be defined a run time but the arithmetic operations are known at compile-time (i.e. the value of \(t\) is known at compile time)
3. both the dimension and the arithmetic operations (i.e. \(t\)) are to be defined a run time.

All three of these types can be accessed via the alias template MaxPlusTruncMat if T has value 0, then the threshold can be set at run time, and if R or C is 0, then the dimension can be set at run time. The default value of T is 0, R is 0, and of C is R.

The alias MaxPlusTruncMat is either StaticMatrix, DynamicMatrix (compile-timearithmetic)", or \ref DynamicMatrixDynamicArith "DynamicMatrix (run-time arithmetic)", please refer to the documentation of these class templates for more details. The only substantial difference in the interface of static and dynamic matrices is that the former can be default constructed and the latter should be constructed using the dimensions.

Example

// construct an uninitialized 3 x 3 static matrix with threshold 11
MaxPlusTruncMat<11, 3> m;
// construct an uninitialized 4 x 4 dynamic matrix with threshold 11
MaxPlusTruncMat<11> m(4, 4);
// construct a truncated max-plus semiring with threshold 11
MaxPlusTruncSemiring sr(11);
// construct an uninitialized 5 x 5 dynamic matrix with threshold 11
// (defined at run time)
MaxPlusTruncMat<>  m(sr, 5, 5);

Classes
struct	MaxPlusTruncProd< T, Scalar >
	Function object for multiplication in truncated max-plus semirings. More...
class	MaxPlusTruncSemiring< Scalar >
	Class representing a truncated max-plus semiring. More...

Typedefs
template<size_t T, typename Scalar>
using	DynamicMaxPlusTruncMat
	Alias for dynamic truncated max-plus matrices.
template<size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>
using	MaxPlusTruncMat
	Alias template for truncated max-plus matrices.
template<size_t T, size_t R, size_t C, typename Scalar>
using	StaticMaxPlusTruncMat
	Alias for static truncated max-plus matrices.

Functions
template<typename Mat>
std::enable_if_t< IsMaxPlusTruncMat< Mat > >	throw_if_bad_entry (Mat const &m)
	Check that a truncated max-plus matrix is valid.
template<typename Mat>
std::enable_if_t< IsMaxPlusTruncMat< Mat > >	throw_if_bad_entry (Mat const &m, typename Mat::scalar_type val)
	Check that an entry in a truncated max-plus matrix is valid.

Variables
template<typename T>
static constexpr bool	IsMaxPlusTruncMat = detail::IsMaxPlusTruncMatHelper<T>::value
	Helper to check if a type is MaxPlusTruncMat.

Typedef Documentation

DynamicMaxPlusTruncMat

template<size_t T, typename Scalar>

using DynamicMaxPlusTruncMat

Initial value:

 DynamicMatrix<MaxPlusPlus<Scalar>,
                                               MaxPlusTruncProd<T, Scalar>,
                                               MaxPlusZero<Scalar>,
                                               IntegerZero<Scalar>,
                                               Scalar>

Defined in matrix.hpp.

Alias for the type of dynamic truncated max-plus matrices where the dimension is defined at run time, but the threshold is defined at compile-time.

Template Parameters

T	the threshold.
Scalar	the type of the entries in the matrix.

MaxPlusTruncMat

template<size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>

using MaxPlusTruncMat

Initial value:

 std::conditional_t<
      R == 0 || C == 0,
      std::conditional_t<T == 0,
                         DynamicMatrix<MaxPlusTruncSemiring<Scalar>, Scalar>,
                         DynamicMaxPlusTruncMat<T, Scalar>>,
      StaticMaxPlusTruncMat<T, R, C, Scalar>>

Defined in matrix.hpp.

Alias template for truncated max-plus matrices.

Template Parameters

T	the threshold. A value of 0 indicates that the value will be set at run time (default: 0).
R	the number of rows. A value of 0 indicates that the value will be set at run time (default: 0).
C	the number of columns. A value of 0 indicates that the value will be set at run time (default: R).
Scalar	the type of the entries in the matrix (default: int).

StaticMaxPlusTruncMat

template<size_t T, size_t R, size_t C, typename Scalar>

using StaticMaxPlusTruncMat

Initial value:

 StaticMatrix<MaxPlusPlus<Scalar>,
                                             MaxPlusTruncProd<T, Scalar>,
                                             MaxPlusZero<Scalar>,
                                             IntegerZero<Scalar>,
                                             R,
                                             C,
                                             Scalar>

Defined in matrix.hpp.

Alias for static truncated max-plus matrices where the threshold and dimensions are defined at compile-time.

Template Parameters

T	the threshold.
R	the number of rows.
C	the number of columns.
Scalar	the type of the entries in the matrix.

Function Documentation

throw_if_bad_entry() [1/2]

template<typename Mat>

std::enable_if_t< IsMaxPlusTruncMat< Mat > > throw_if_bad_entry

(

Mat const &

m

)

Defined in matrix.hpp.

This function can be used to check that a matrix contains values in the underlying semiring.

Template Parameters

Mat	the type of m, must satisfy IsMaxPlusTruncMat<Mat>.

Parameters

m	the matrix to check.

Exceptions

LibsemigroupsException

if any entry in the matrix is not in the set \(\{0, 1, \ldots, t, -\infty\}\) where \(t\) is the threshold of the matrix or if the underlying semiring is not defined (only applies to matrices with run time arithmetic).

throw_if_bad_entry() [2/2]

template<typename Mat>

std::enable_if_t< IsMaxPlusTruncMat< Mat > > throw_if_bad_entry	(	Mat const &	m,
		typename Mat::scalar_type	val )

Defined in matrix.hpp.

This function can be used to check that a matrix contains values in the underlying semiring.

Template Parameters

Mat	the type the 1st argument, must satisfy IsMaxPlusTruncMat<Mat>.

Parameters

m	the matrix.
val	the entry to check.

Exceptions

LibsemigroupsException

if the entry val is not in the set \(\{0, 1, \ldots, t, -\infty\}\) where \(t\) is the threshold of the matrix or if the underlying semiring is not defined (only applies to matrices with run time arithmetic).

Variable Documentation

IsMaxPlusTruncMat

template<typename T>

bool IsMaxPlusTruncMat = detail::IsMaxPlusTruncMatHelper<T>::value

staticconstexpr

Defined in matrix.hpp.

This variable has value true if the template parameter T is the same as MaxPlusTruncMat for some template parameters; and false if it is not.

Template Parameters

T	the type to check.