tropical_gemm/types/
min_plus.rs

1use super::scalar::TropicalScalar;
2use super::traits::{SimdTropical, TropicalSemiring, TropicalWithArgmax};
3use std::fmt;
4use std::ops::{Add, Mul};
5
6/// TropicalMinPlus semiring: (ℝ ∪ {+∞}, min, +)
7///
8/// - Addition (⊕) = min
9/// - Multiplication (⊗) = +
10/// - Zero = +∞
11/// - One = 0
12///
13/// This is used for:
14/// - Shortest path algorithms (Dijkstra, Floyd-Warshall)
15/// - Dynamic programming with minimum cost
16#[derive(Copy, Clone, PartialEq)]
17#[repr(transparent)]
18pub struct TropicalMinPlus<T: TropicalScalar>(pub T);
19
20impl<T: TropicalScalar> TropicalMinPlus<T> {
21    /// Create a new TropicalMinPlus value.
22    #[inline(always)]
23    pub fn new(value: T) -> Self {
24        Self(value)
25    }
26}
27
28impl<T: TropicalScalar> TropicalSemiring for TropicalMinPlus<T> {
29    type Scalar = T;
30
31    fn scalar_slice(values: &[Self]) -> Option<&[Self::Scalar]> {
32        // SAFETY: this type is repr(transparent) over its scalar field.
33        Some(unsafe { std::slice::from_raw_parts(values.as_ptr().cast(), values.len()) })
34    }
35
36    #[inline(always)]
37    fn tropical_zero() -> Self {
38        Self(T::pos_infinity())
39    }
40
41    #[inline(always)]
42    fn tropical_one() -> Self {
43        Self(T::scalar_zero())
44    }
45
46    #[inline(always)]
47    fn tropical_add(self, rhs: Self) -> Self {
48        Self(self.0.scalar_min(rhs.0))
49    }
50
51    #[inline(always)]
52    fn tropical_mul(self, rhs: Self) -> Self {
53        Self(self.0.scalar_add(rhs.0))
54    }
55
56    #[inline(always)]
57    fn value(&self) -> T {
58        self.0
59    }
60
61    #[inline(always)]
62    fn from_scalar(s: T) -> Self {
63        Self(s)
64    }
65}
66
67impl<T: TropicalScalar> TropicalWithArgmax for TropicalMinPlus<T> {
68    type Index = u32;
69
70    #[inline(always)]
71    fn tropical_add_argmax(self, self_idx: u32, rhs: Self, rhs_idx: u32) -> (Self, u32) {
72        // For min, we track argmin
73        if self.0 <= rhs.0 {
74            (self, self_idx)
75        } else {
76            (rhs, rhs_idx)
77        }
78    }
79
80    #[inline(always)]
81    fn is_no_contribution(&self) -> bool {
82        self.0.is_drifted_pos_zero()
83    }
84}
85
86impl<T: TropicalScalar> SimdTropical for TropicalMinPlus<T> {
87    const SIMD_AVAILABLE: bool = true;
88    const SIMD_WIDTH: usize = 8;
89}
90
91impl<T: TropicalScalar> Add for TropicalMinPlus<T> {
92    type Output = Self;
93
94    #[inline(always)]
95    fn add(self, rhs: Self) -> Self::Output {
96        self.tropical_add(rhs)
97    }
98}
99
100impl<T: TropicalScalar> Mul for TropicalMinPlus<T> {
101    type Output = Self;
102
103    #[inline(always)]
104    fn mul(self, rhs: Self) -> Self::Output {
105        self.tropical_mul(rhs)
106    }
107}
108
109impl<T: TropicalScalar> Default for TropicalMinPlus<T> {
110    #[inline(always)]
111    fn default() -> Self {
112        Self::tropical_zero()
113    }
114}
115
116impl<T: TropicalScalar> fmt::Debug for TropicalMinPlus<T> {
117    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
118        write!(f, "TropicalMinPlus({})", self.0)
119    }
120}
121
122impl<T: TropicalScalar> fmt::Display for TropicalMinPlus<T> {
123    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
124        write!(f, "{}", self.0)
125    }
126}
127
128impl<T: TropicalScalar> From<T> for TropicalMinPlus<T> {
129    #[inline(always)]
130    fn from(value: T) -> Self {
131        Self(value)
132    }
133}
134
135#[cfg(test)]
136mod tests {
137    use super::*;
138
139    #[test]
140    fn test_semiring_identity() {
141        let a = TropicalMinPlus::new(5.0f64);
142        let zero = TropicalMinPlus::tropical_zero();
143        let one = TropicalMinPlus::tropical_one();
144
145        // a ⊕ 0 = a
146        assert_eq!(a.tropical_add(zero), a);
147        // a ⊗ 1 = a
148        assert_eq!(a.tropical_mul(one), a);
149    }
150
151    #[test]
152    fn test_operations() {
153        let a = TropicalMinPlus::new(3.0f64);
154        let b = TropicalMinPlus::new(5.0f64);
155
156        // min(3, 5) = 3
157        assert_eq!(a.tropical_add(b).0, 3.0);
158        // 3 + 5 = 8
159        assert_eq!(a.tropical_mul(b).0, 8.0);
160    }
161
162    #[test]
163    fn test_shortest_path_scenario() {
164        // Simulating: path cost a=10, path cost b=5, combine = min(10,5) = 5
165        let a = TropicalMinPlus::new(10.0f64);
166        let b = TropicalMinPlus::new(5.0f64);
167        assert_eq!(a.tropical_add(b).0, 5.0);
168
169        // Extending a path: cost=5, edge=3, total = 5+3 = 8
170        let path = TropicalMinPlus::new(5.0f64);
171        let edge = TropicalMinPlus::new(3.0f64);
172        assert_eq!(path.tropical_mul(edge).0, 8.0);
173    }
174
175    #[test]
176    fn test_argmin_right_wins() {
177        // For MinPlus, argmax actually tracks argmin
178        let a = TropicalMinPlus::new(5.0f64);
179        let b = TropicalMinPlus::new(3.0f64);
180
181        let (result, idx) = a.tropical_add_argmax(0, b, 1);
182        assert_eq!(result.0, 3.0);
183        assert_eq!(idx, 1); // Right has smaller value
184    }
185
186    #[test]
187    fn test_argmin_left_wins() {
188        let a = TropicalMinPlus::new(2.0f64);
189        let b = TropicalMinPlus::new(7.0f64);
190
191        let (result, idx) = a.tropical_add_argmax(10, b, 20);
192        assert_eq!(result.0, 2.0);
193        assert_eq!(idx, 10); // Left has smaller value
194    }
195
196    #[test]
197    fn test_argmin_equal_values() {
198        // When values are equal, left (self) wins (<= comparison)
199        let a = TropicalMinPlus::new(5.0f64);
200        let b = TropicalMinPlus::new(5.0f64);
201
202        let (result, idx) = a.tropical_add_argmax(1, b, 2);
203        assert_eq!(result.0, 5.0);
204        assert_eq!(idx, 1); // Equal, so left (self) wins
205    }
206
207    #[test]
208    fn test_argmin_chain() {
209        // Simulate accumulating through k iterations - find minimum
210        let mut acc = TropicalMinPlus::tropical_zero(); // +inf
211        let mut idx = 0u32;
212
213        let values = [8.0, 3.0, 9.0, 5.0]; // Min is at index 1
214        for (k, &val) in values.iter().enumerate() {
215            let candidate = TropicalMinPlus::new(val);
216            (acc, idx) = acc.tropical_add_argmax(idx, candidate, k as u32);
217        }
218
219        assert_eq!(acc.0, 3.0);
220        assert_eq!(idx, 1); // Index where min occurred
221    }
222
223    #[test]
224    fn test_argmin_pos_infinity() {
225        let a = TropicalMinPlus::tropical_zero(); // +inf
226        let b = TropicalMinPlus::new(100.0f64);
227
228        let (result, idx) = a.tropical_add_argmax(0, b, 1);
229        assert_eq!(result.0, 100.0);
230        assert_eq!(idx, 1); // 100 < +inf
231    }
232
233    #[test]
234    fn test_absorbing_zero() {
235        let a = TropicalMinPlus::new(5.0f64);
236        let zero = TropicalMinPlus::tropical_zero();
237
238        // a ⊗ 0 = a + (+inf) = +inf
239        let result = a.tropical_mul(zero);
240        assert!(result.0.is_infinite() && result.0 > 0.0);
241    }
242
243    #[test]
244    fn test_operator_overloads() {
245        let a = TropicalMinPlus::new(3.0f64);
246        let b = TropicalMinPlus::new(5.0f64);
247
248        // Add operator (min)
249        assert_eq!((a + b).0, 3.0);
250        assert_eq!((b + a).0, 3.0);
251
252        // Mul operator (add)
253        assert_eq!((a * b).0, 8.0);
254        assert_eq!((b * a).0, 8.0);
255    }
256
257    #[test]
258    fn test_default() {
259        let d = TropicalMinPlus::<f64>::default();
260        assert!(d.0.is_infinite() && d.0 > 0.0); // +inf
261        assert_eq!(d, TropicalMinPlus::tropical_zero());
262    }
263
264    #[test]
265    fn test_display_debug() {
266        let a = TropicalMinPlus::new(5.0f64);
267
268        assert_eq!(format!("{}", a), "5");
269        assert_eq!(format!("{:?}", a), "TropicalMinPlus(5)");
270    }
271
272    #[test]
273    fn test_from() {
274        let a: TropicalMinPlus<f64> = 5.0.into();
275        assert_eq!(a.0, 5.0);
276
277        let b = TropicalMinPlus::<f64>::from(3.0);
278        assert_eq!(b.0, 3.0);
279    }
280
281    #[test]
282    fn test_value_and_from_scalar() {
283        let a = TropicalMinPlus::new(5.0f64);
284        assert_eq!(a.value(), 5.0);
285
286        let b = TropicalMinPlus::<f64>::from_scalar(3.0);
287        assert_eq!(b.value(), 3.0);
288    }
289
290    #[test]
291    fn test_simd_tropical() {
292        assert!(TropicalMinPlus::<f64>::SIMD_AVAILABLE);
293        assert_eq!(TropicalMinPlus::<f64>::SIMD_WIDTH, 8);
294    }
295
296    #[test]
297    fn test_clone_copy() {
298        let a = TropicalMinPlus::new(5.0f64);
299        let a_copy = a;
300        let a_clone = a.clone();
301
302        assert_eq!(a, a_copy);
303        assert_eq!(a, a_clone);
304    }
305
306    #[test]
307    fn test_eq() {
308        let a1 = TropicalMinPlus::new(5.0f64);
309        let a2 = TropicalMinPlus::new(5.0f64);
310        let b = TropicalMinPlus::new(3.0f64);
311
312        assert_eq!(a1, a2);
313        assert_ne!(a1, b);
314    }
315
316    #[test]
317    fn test_f32() {
318        let a = TropicalMinPlus::new(3.0f32);
319        let b = TropicalMinPlus::new(5.0f32);
320
321        assert!((a.tropical_add(b).0 - 3.0).abs() < 1e-6);
322        assert!((a.tropical_mul(b).0 - 8.0).abs() < 1e-6);
323    }
324}
tropical_gemm/types/min_plus.rs

tropical_gemm/types/
min_plus.rs
