Max-plus matrices

Defined in matrix.hpp.

This page describes the functionality for \(n \times n\) matrices over the max-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 MaxPlusMat<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 MaxPlusMat<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

MaxPlusMat<3> m;       // default construct an uninitialized 3 x 3 static matrix
MaxPlusMat<>  m(4, 4); // construct an uninitialized 4 x 4 dynamic matrix
template<typename Scalar>
struct MaxPlusPlus

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} \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.

template<typename Scalar>
struct MaxPlusProd

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 max-plus semiring.

template<typename Scalar>
struct MaxPlusZero

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 max-plus semiring.

template<typename Scalar>
using DynamicMaxPlusMat = DynamicMatrix<MaxPlusPlus<Scalar>, MaxPlusProd<Scalar>, MaxPlusZero<Scalar>, IntegerZero<Scalar>, Scalar>

Alias for the type of dynamic max-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 StaticMaxPlusMat = StaticMatrix<MaxPlusPlus<Scalar>, MaxPlusProd<Scalar>, MaxPlusZero<Scalar>, IntegerZero<Scalar>, R, C, Scalar>

Alias for static max-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 MaxPlusMat = std::conditional_t<R == 0 || C == 0, DynamicMaxPlusMat<Scalar>, StaticMaxPlusMat<R, C, Scalar>>

Alias template for max-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 IsMaxPlusMat

This variable has value true if the template parameter T is the same as MaxPlusMat<R, C, Scalar> for some value of N and Scalar.