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 parameter T is the same as MinPlusMat<N, Scalar> for some value of N and Scalar.