tropical.cppm File Reference

The tropical semiring Tropical<T> = T ∪ {∞}, a dioid. More...

#include <concepts>
#include <functional>
#include <limits>
import dedekind.algebra:universal;
import dedekind.category;

Include dependency graph for tropical.cppm:

Classes
struct	dedekind::algebra::Tropical< T, Max >
	Tropical carrier T ∪ {∞}. finite==false is the ⊕-identity sentinel (−∞ for Max, +∞ for Min), absorbing under ⊗. operator+ is ⊗ (honest addition); ⊕ is TropicalPlus. More...
struct	dedekind::algebra::TropicalPlus
	⊕: the tropical addition, the order-extremum (a semilattice join for Max, meet for Min). Named, not an operator, so a+b never silently means max. More...
struct	dedekind::category::unit_trait< dedekind::algebra::Tropical< T, M >, dedekind::algebra::TropicalPlus, void >
	⊕-identity is the ∞ sentinel. More...
struct	dedekind::category::unit_trait< dedekind::algebra::Tropical< T, M >, std::plus< dedekind::algebra::Tropical< T, M > >, void >
	⊗-identity is 0. More...
struct	dedekind::category::is_saturating< dedekind::algebra::Tropical< T, M >, std::plus< dedekind::algebra::Tropical< T, M > > >
	⊗ (= T's + with the ∞ sentinel absorbing) is total exactly when T's own + is total: the ∞ boundary saturates, and the finite part inherits T's totality. Gated on IsMagma<T> so the certificate is honest — true for a periodic carrier such as unsigned (defined wraparound, no UB), false for long long (signed overflow is not a magma; cf. the !IsMagma<int,+> rejection in category/total.cppm). More...
struct	dedekind::algebra::semiring_ops< Tropical< T, M > >
	The tropical semiring's operations, (⊕ = TropicalPlus, ⊗ = +): its own, not the ring's, registered on :universal's semiring_ops. More...

Namespaces
namespace	dedekind::category

Concepts
concept	dedekind::algebra::IsTropical
	A dioid: an IsSemiring whose additive monoid Add is idempotent (a semilattice). This is the algebraic gate for the tropical carriers, refining IsSemiring exactly by ⊕-idempotence.

Typedefs
template<typename T>
using	dedekind::algebra::MaxPlus = Tropical<T, true>
template<typename T>
using	dedekind::algebra::MinPlus = Tropical<T, false>

Variables
template<typename T, bool M>
constexpr bool	dedekind::category::is_distributive_v< dedekind::algebra::Tropical< T, M >, std::plus< dedekind::algebra::Tropical< T, M > >, dedekind::algebra::TropicalPlus > = true
	⊗ distributes over ⊕.

Detailed Description

The tropical semiring Tropical<T> = T ∪ {∞}, a dioid.

@partition :tropical

Copyright

2026 The Dedekind Authors Licensed under the Apache License, Version 2.0.

tropical__Overview

Tropical<T, Max> layers over a totally-ordered monoid T: the multiplication ⊗ is T's own + (exposed as operator+), and the addition ⊕ is the order-extremum (max when Max, else min), with the sentinel ∞ as its identity (−∞ for max, +∞ for min). It is an idempotent semiring — a dioid — since ⊕ is a semilattice. MaxPlus / MinPlus alias the two directions; MaxPlus (longest path) is the critical-path carrier.

The multiplication is the naturals' addition (Maslov dequantization: ×↦+, +↦max, 1↦0, 0↦−∞); ℕ and Tropical branch on the idempotence of ⊕.