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:
the dimension is known at compile-time;
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)
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<T, R, C, Scalar>
: 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<T, R, C, Scalar>
is either
StaticMatrix
or DynamicMatrix
, please refer to the
documentation of these class templates for more details. The only substantial
difference in the interface of StaticMatrix
and
DynamicMatrix
is that the former can be default constructed and the
latter should be constructed using the dimensions.
Example
MaxPlusTruncMat<11, 3> m; // default construct an uninitialized 3 x 3 static matrix with threshold 11
MaxPlusTruncMat<11> m(4, 4); // construct an uninitialized 4 x 4 dynamic matrix with threshold 11
MaxPlusTruncSemiring sr(11); // construct a truncated max-plus semiring with threshold 11
MaxPlusTruncMat<> m(sr, 5, 5); // construct an uninitialized 5 x 5 dynamic matrix with threshold 11 (defined at run time)
-
template<size_t T, typename Scalar>
struct MaxPlusTruncProd¶ This is a stateless struct with a single call operator of signature:
Scalar operator()(Scalar const x, Scalar const y) const noexcept
that returns \(x \otimes y\) which is defined by\[\begin{split}x\otimes y = \begin{cases} \min\{x + y, T\} & \text{if } x \neq -\infty\text{ and }y \neq -\infty \\ -\infty & \text{if } x = -\infty \text{ or }y = -\infty; \\ \end{cases}\end{split}\]representing multiplication in the quotient of the max-plus semiring by the congruence \(T = T + 1\).
-
template<typename Scalar = int>
class MaxPlusTruncSemiring final¶ This class represents the max-plus truncated semiring consists of the integers \(\{0, \ldots , t\}\) for some value \(t\) (called the threshold of the semiring) and \(-\infty\). Instances of this class can be used to define the value of the threshold \(t\) at run time.
- Template Parameters
Scalar – the type of the elements of the semiring. This must be a signed integer type.
-
MaxPlusTruncSemiring() = delete¶
Deleted default constructor.
-
MaxPlusTruncSemiring(MaxPlusTruncSemiring const&) = default¶
Default copy constructor.
-
MaxPlusTruncSemiring(MaxPlusTruncSemiring&&) = default¶
Default move constructor.
-
MaxPlusTruncSemiring &operator=(MaxPlusTruncSemiring const&) = default¶
Default copy assignment operator.
-
MaxPlusTruncSemiring &operator=(MaxPlusTruncSemiring&&) = default¶
Default move assignment operator.
-
explicit MaxPlusTruncSemiring(Scalar const threshold)¶
Construct from threshold.
- Parameters
threshold – the threshold.
- Throws
LibsemigroupsException
ifthreshold
is less than zero.- Complexity
Constant.
-
Scalar zero() const noexcept¶
Returns \(-\infty\); representing the additive identity of the quotient of the max-plus semiring.
- Parameters
(None)
- Returns
A value of type
Scalar
.- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Constant.
-
Scalar one() const noexcept¶
Returns \(0\); representing the multiplicative identity of the quotient of the max-plus semiring.
- Parameters
(None)
- Returns
A value of type
Scalar
.- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Constant.
-
Scalar plus(Scalar const x, Scalar const y) const noexcept¶
Returns \(x \oplus y\) which is defined by
\[\begin{split}x\oplus y = \begin{cases} \max\{x, y\} & \text{if } x \neq -\infty\text{ and }y \neq -\infty \\ -\infty & \text{if } x = -\infty \text{ or }y = -\infty; \\ \end{cases}\end{split}\]representing addition in the max-plus semiring (and its quotient).
- Parameters
x – scalar
y – scalar
- Returns
A value of type
Scalar
.- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Constant.
-
Scalar prod(Scalar const x, Scalar const y) const noexcept¶
Returns \(x \otimes y\) which is defined by
\[\begin{split}x\otimes y = \begin{cases} \min\{x + y, t\} & \text{if } x \neq -\infty\text{ and }y \neq -\infty \\ -\infty & \text{if } x = -\infty \text{ or }y = -\infty; \\ \end{cases}\end{split}\]where \(t\) is the threshold; representing multiplication in the quotient of the max-plus semiring.
- Parameters
x – scalar
y – scalar
- Returns
A value of type
Scalar
.- Exceptions
This function is
noexcept
and is guaranteed never to throw.- Complexity
Constant.
-
template<typename Scalar>
using DynamicMaxPlusTruncMatSR = DynamicMatrix<MaxPlusTruncSemiring<Scalar>, Scalar>¶ Alias for truncated max-plus matrices with dimensions and threshold defined at runtime.
- Template Parameters
Scalar – The type of the entries in the matrix.
-
template<typename T, typename Scalar>
using DynamicMaxPlusTruncMat = DynamicMatrix<MaxPlusPlus<Scalar>, MaxPlusTruncProd<T, Scalar>, MaxPlusZero<Scalar>, IntegerZero<Scalar>, Scalar>¶ Alias for the type of dynamic 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.
-
template<size_t T, size_t R, size_t C, typename Scalar>
using StaticMaxPlusTruncMat = StaticMatrix<MaxPlusPlus<Scalar>, MaxPlusTruncProd<T, Scalar>, MaxPlusZero<Scalar>, IntegerZero<Scalar>, R, C, Scalar>¶ Alias for static max-plus truncated 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.
-
template<size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>
using MaxPlusTruncMat = std::conditional_t<R == 0 || C == 0, std::conditional_t<T == 0, DynamicMaxPlusTruncMatSR<Scalar>, DynamicMaxPlusTruncMat<T, Scalar>>, StaticMaxPlusTruncMat<T, R, C, Scalar>>¶ - 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
).
-
template<typename T>
static constexpr bool IsMaxPlusTruncMat¶ This variable has value
true
if the template parameterT
is the same asMaxPlusTruncMat<T, R, C, Scalar>
for some values ofT
,R
,C
, andScalar
; andfalse
if it is not.