Truncated min-plus matrices

Defined in matrix.hpp.

This page describes the functionality for \(n \times n\) matrices over the finite quotient of the min-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 MinPlusTruncMat<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 MinPlusTruncMat<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

MinPlusTruncMat<11, 3> m;       // default construct an uninitialized 3 x 3 static matrix with threshold 11
MinPlusTruncMat<11> m(4, 4);    // construct an uninitialized 4 x 4 dynamic matrix with threshold 11
MinPlusTruncSemiring sr(11);    // construct a truncated min-plus semiring with threshold 11
MinPlusTruncMat<>  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 MinPlusTruncProd

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 min-plus semiring by the congruence \(T = T + 1\).

template<typename Scalar = int>
class MinPlusTruncSemiring final

This class represents the min-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 an integral type.

MinPlusTruncSemiring() = delete

Deleted default constructor.

MinPlusTruncSemiring(MinPlusTruncSemiring const&) = default

Default copy constructor.

MinPlusTruncSemiring(MinPlusTruncSemiring&&) = default

Default move constructor.

MinPlusTruncSemiring &operator=(MinPlusTruncSemiring const&) = default

Default copy assignment operator.

MinPlusTruncSemiring &operator=(MinPlusTruncSemiring&&) = default

Default move assignment operator.

explicit MinPlusTruncSemiring(Scalar const threshold)

Construct from threshold.

Parameters

threshold – the threshold.

Throws

LibsemigroupsException if Scalar is a signed type and threshold is less than zero.

Complexity

Constant.

Scalar zero() const noexcept

Returns \(\infty\); representing the additive identity of the quotient of the min-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 min-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} \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 (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 min-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.

Scalar threshold() const noexcept

Returns the threshold value used to construct this.

Parameters

(None)

Returns

A value of type Scalar.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

template<typename Scalar>
using DynamicMinPlusTruncMatSR = DynamicMatrix<MinPlusTruncSemiring<Scalar>, Scalar>

Alias for truncated min-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 DynamicMinPlusTruncMat = DynamicMatrix<MinPlusPlus<Scalar>, MinPlusTruncProd<T, Scalar>, MinPlusZero<Scalar>, IntegerZero<Scalar>, Scalar>

Alias for the type of dynamic min-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 StaticMinPlusTruncMat = StaticMatrix<MinPlusPlus<Scalar>, MinPlusTruncProd<T, Scalar>, MinPlusZero<Scalar>, IntegerZero<Scalar>, R, C, Scalar>

Alias for static min-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 MinPlusTruncMat = std::conditional_t<R == 0 || C == 0, std::conditional_t<T == 0, DynamicMinPlusTruncMatSR<Scalar>, DynamicMinPlusTruncMat<T, Scalar>>, StaticMinPlusTruncMat<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 IsMinPlusTruncMat

This variable has value true if the template parameter T is the same as MinPlusTruncMat<T, R, C, Scalar> for some values of T, R, C, and Scalar; and false if it is not.