Min-plus matrices¶
Defined in matrix.hpp
.
This page describes the functionality for \(n \times n\) matrices over the
min-plus semiring for arbitrary dimension \(n\). There are two types of
such matrices those whose dimension is known at compile-time, and those where
it is not. Both types can be accessed via the alias template
MinPlusMat<N, Scalar>
: if N
has value 0
, then the dimensions
can be set at run time, otherwise N
is the dimension. The default value of
N
is 0
.
The alias MinPlusMat<N, 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
MinPlusMat<3> m; // default construct an uninitialized 3 x 3 static matrix
MinPlusMat<> m(4, 4); // construct an uninitialized 4 x 4 dynamic matrix
-
template<typename Scalar>
struct MinPlusPlus¶ 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 \oplus y\) which is defined by\[\begin{split}x\oplus y = \begin{cases} \min\{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 min-plus semiring.
-
template<typename Scalar>
struct MinPlusProd¶ 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} 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 multiplication in the min-plus semiring.
-
template<typename Scalar>
struct MinPlusZero¶ This is a stateless struct with a single call operator of signature:
Scalar operator()() const noexcept
which returns \(\infty\); representing the additive identity of the min-plus semiring.
-
template<typename Scalar>
using DynamicMinPlusMat = DynamicMatrix<MinPlusPlus<Scalar>, MinPlusProd<Scalar>, MinPlusZero<Scalar>, IntegerZero<Scalar>, Scalar>¶ Alias for the type of dynamic min-plus matrices where the dimensions of the matrices can be defined at run time.
- Template Parameters
Scalar – The type of the entries in the matrix.
-
template<size_t R, size_t C, typename Scalar>
using StaticMinPlusMat = StaticMatrix<MinPlusPlus<Scalar>, MinPlusProd<Scalar>, MinPlusZero<Scalar>, IntegerZero<Scalar>, R, C, Scalar>¶ Alias for static min-plus matrices whose arithmetic and dimensions are defined at compile-time.
- Template Parameters
R – the number of rows.
C – the number of columns.
Scalar – The type of the entries in the matrix.
-
template<size_t R = 0, size_t C = R, Scalar = int>
using MinPlusMat = std::conditional_t<R == 0 || C == 0, DynamicMinPlusMat<Scalar>, StaticMinPlusMat<R, C, Scalar>>¶ Alias template for min-plus matrices.
- Template Parameters
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 IsMinPlusMat¶ This variable has value
true
if the template parameterT
is the same asMinPlusMat<N, Scalar>
for some value ofN
andScalar
.