Truncated min-plus matrices

Defined in matrix-class.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, P, 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 is either StaticMatrix, DynamicMatrix (compile-time arithmetic), or DynamicMatrix (run-time arithmetic), please refer to the documentation of these class templates for more details. The only substantial difference in the interface of static and dynamic matrices is that the former can be default constructed and the latter should be constructed using the dimensions.

Example

// construct an uninitialized 3 x 3 static matrix with threshold 11
[[maybe_unused]] MinPlusTruncMat<11, 3> m3_11;
// construct an uninitialized 4 x 4 dynamic matrix with threshold 11
MinPlusTruncMat<11> m4_11(4, 4);
// construct a truncated min-plus semiring with threshold 11
MinPlusTruncSemiring sr_11(11);
// construct an uninitialized 5 x 5 dynamic matrix with threshold 11
// (defined at run time)
MinPlusTruncMat<>  m5_11(&sr_11, 5, 5);

Classes
struct	MinPlusTruncProd< T, Scalar >
	Function object for multiplication in min-plus truncated semirings. More...
class	MinPlusTruncSemiring< Scalar >
	Class representing a truncated min-plus semiring. More...

Typedefs
template<size_t T, typename Scalar>
using	DynamicMinPlusTruncMat
	Alias for dynamic truncated min-plus matrices.
template<size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>
using	MinPlusTruncMat
	Alias template for truncated min-plus matrices.
template<size_t T, size_t R, size_t C, typename Scalar>
using	StaticMinPlusTruncMat
	Alias for static truncated min-plus matrices.

Functions
template<typename Mat>
auto	throw_if_bad_entry (Mat const &m) -> std::enable_if_t< IsMinPlusTruncMat< Mat > >
	Check that a truncated min-plus matrix is valid.
template<typename Mat>
auto	throw_if_bad_entry (Mat const &m, typename Mat::scalar_type val) -> std::enable_if_t< IsMinPlusTruncMat< Mat > >
	Check that an entry in a truncated min-plus matrix is valid.

Variables
template<typename T>
static constexpr bool	IsMinPlusTruncMat = detail::IsMinPlusTruncMatHelper<T>::value
	Helper to check if a type is MinPlusTruncMat.

Typedef Documentation

DynamicMinPlusTruncMat

template<size_t T, typename Scalar>

using DynamicMinPlusTruncMat

Initial value:

DynamicMatrix<MinPlusPlus<Scalar>,
                                              MinPlusTruncProd<T, Scalar>,
                                              MinPlusZero<Scalar>,
                                              IntegerZero<Scalar>,
                                              Scalar>

Defined in matrix-class.hpp.

Alias for the type of dynamic truncated 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.

MinPlusTruncMat

template<size_t T = 0, size_t R = 0, size_t C = R, typename Scalar = int>

using MinPlusTruncMat

Initial value:

std::conditional_t<
     R == 0 || C == 0,
     std::conditional_t<T == 0,
                        DynamicMatrix<MinPlusTruncSemiring<Scalar>, Scalar>,
                        DynamicMinPlusTruncMat<T, Scalar>>,
     StaticMinPlusTruncMat<T, R, C, Scalar>>

Defined in matrix-class.hpp.

Alias template for truncated min-plus matrices.

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).

StaticMinPlusTruncMat

template<size_t T, size_t R, size_t C, typename Scalar>

using StaticMinPlusTruncMat

Initial value:

StaticMatrix<MinPlusPlus<Scalar>,
                                            MinPlusTruncProd<T, Scalar>,
                                            MinPlusZero<Scalar>,
                                            IntegerZero<Scalar>,
                                            R,
                                            C,
                                            Scalar>

Defined in matrix-class.hpp.

Alias for static truncated min-plus 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.

Function Documentation

throw_if_bad_entry() [1/2]

template<typename Mat>

auto throw_if_bad_entry

(

Mat const &

m

)

-> std::enable_if_t< IsMinPlusTruncMat< Mat > >

Defined in matrix-exceptions.hpp.

This function can be used to check that a matrix contains values in the underlying semiring.

Template Parameters

Mat	the type of the matrix m (must satisfy IsMinPlusTruncMat<Mat>).

Parameters

m	the matrix to check.

Exceptions

LibsemigroupsException

if any entry in the matrix is not in the set \(\{0, 1, \ldots, t, \infty\}\) where \(t\) is the threshold of the matrix or if the underlying semiring is not defined (only applies to matrices with run time arithmetic).

throw_if_bad_entry() [2/2]

template<typename Mat>

auto throw_if_bad_entry	(	Mat const &	m,
		typename Mat::scalar_type	val ) -> std::enable_if_t< IsMinPlusTruncMat< Mat > >

Defined in matrix-exceptions.hpp.

This function can be used to check that a matrix contains values in the underlying semiring.

Template Parameters

Mat	the type the 1st argument, must satisfy IsMinPlusTruncMat<Mat>.

Parameters

m	the matrix.
val	the entry to check.

Exceptions

LibsemigroupsException

if the entry val is not in the set \(\{0, 1, \ldots, t, \infty\}\) where \(t\) is the threshold of the matrix or if the underlying semiring is not defined (only applies to matrices with run time arithmetic).

Deprecated

This function is deprecated and will be removed from libsemigroups in v4.

Variable Documentation

IsMinPlusTruncMat

template<typename T>

bool IsMinPlusTruncMat = detail::IsMinPlusTruncMatHelper<T>::value

staticconstexpr

Defined in is-matrix.hpp.

This variable has value true if the template parameter T is the same as MinPlusTruncMat for some template parameters; and false if it is not.

Template Parameters

T	the type to check.