ruvector_math/tropical/
semiring.rs

1//! Tropical Semiring Core Operations
2//!
3//! Implements the max-plus and min-plus semirings.
4
5use std::cmp::Ordering;
6use std::ops::{Add, Mul};
7
8/// Tropical number in the max-plus semiring
9#[derive(Debug, Clone, Copy)]
10pub struct Tropical {
11    value: f64,
12}
13
14impl Tropical {
15    /// Tropical zero (-∞ in max-plus)
16    pub const ZERO: Tropical = Tropical {
17        value: f64::NEG_INFINITY,
18    };
19
20    /// Tropical one (0 in max-plus)
21    pub const ONE: Tropical = Tropical { value: 0.0 };
22
23    /// Create new tropical number
24    #[inline]
25    pub fn new(value: f64) -> Self {
26        Self { value }
27    }
28
29    /// Get underlying value
30    #[inline]
31    pub fn value(&self) -> f64 {
32        self.value
33    }
34
35    /// Check if this is tropical zero (-∞)
36    #[inline]
37    pub fn is_zero(&self) -> bool {
38        self.value == f64::NEG_INFINITY
39    }
40
41    /// Tropical addition: max(a, b)
42    #[inline]
43    pub fn add(&self, other: &Self) -> Self {
44        Self {
45            value: self.value.max(other.value),
46        }
47    }
48
49    /// Tropical multiplication: a + b
50    #[inline]
51    pub fn mul(&self, other: &Self) -> Self {
52        if self.is_zero() || other.is_zero() {
53            Self::ZERO
54        } else {
55            Self {
56                value: self.value + other.value,
57            }
58        }
59    }
60
61    /// Tropical power: n * a
62    #[inline]
63    pub fn pow(&self, n: i32) -> Self {
64        if self.is_zero() {
65            Self::ZERO
66        } else {
67            Self {
68                value: self.value * n as f64,
69            }
70        }
71    }
72}
73
74impl Add for Tropical {
75    type Output = Self;
76
77    fn add(self, other: Self) -> Self {
78        Tropical::add(&self, &other)
79    }
80}
81
82impl Mul for Tropical {
83    type Output = Self;
84
85    fn mul(self, other: Self) -> Self {
86        Tropical::mul(&self, &other)
87    }
88}
89
90impl PartialEq for Tropical {
91    fn eq(&self, other: &Self) -> bool {
92        (self.value - other.value).abs() < 1e-10
93    }
94}
95
96impl PartialOrd for Tropical {
97    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
98        self.value.partial_cmp(&other.value)
99    }
100}
101
102/// Trait for tropical semiring operations
103pub trait TropicalSemiring {
104    /// Tropical zero element
105    fn tropical_zero() -> Self;
106
107    /// Tropical one element
108    fn tropical_one() -> Self;
109
110    /// Tropical addition (max for max-plus, min for min-plus)
111    fn tropical_add(&self, other: &Self) -> Self;
112
113    /// Tropical multiplication (ordinary addition)
114    fn tropical_mul(&self, other: &Self) -> Self;
115}
116
117impl TropicalSemiring for f64 {
118    fn tropical_zero() -> Self {
119        f64::NEG_INFINITY
120    }
121
122    fn tropical_one() -> Self {
123        0.0
124    }
125
126    fn tropical_add(&self, other: &Self) -> Self {
127        self.max(*other)
128    }
129
130    fn tropical_mul(&self, other: &Self) -> Self {
131        if *self == f64::NEG_INFINITY || *other == f64::NEG_INFINITY {
132            f64::NEG_INFINITY
133        } else {
134            *self + *other
135        }
136    }
137}
138
139/// Min-plus tropical number (for shortest paths)
140#[derive(Debug, Clone, Copy)]
141pub struct TropicalMin {
142    value: f64,
143}
144
145impl TropicalMin {
146    /// Tropical zero (+∞ in min-plus)
147    pub const ZERO: TropicalMin = TropicalMin {
148        value: f64::INFINITY,
149    };
150
151    /// Tropical one (0 in min-plus)
152    pub const ONE: TropicalMin = TropicalMin { value: 0.0 };
153
154    /// Create new min-plus tropical number
155    #[inline]
156    pub fn new(value: f64) -> Self {
157        Self { value }
158    }
159
160    /// Get underlying value
161    #[inline]
162    pub fn value(&self) -> f64 {
163        self.value
164    }
165
166    /// Tropical addition: min(a, b)
167    #[inline]
168    pub fn add(&self, other: &Self) -> Self {
169        Self {
170            value: self.value.min(other.value),
171        }
172    }
173
174    /// Tropical multiplication: a + b
175    #[inline]
176    pub fn mul(&self, other: &Self) -> Self {
177        if self.value == f64::INFINITY || other.value == f64::INFINITY {
178            Self::ZERO
179        } else {
180            Self {
181                value: self.value + other.value,
182            }
183        }
184    }
185}
186
187impl Add for TropicalMin {
188    type Output = Self;
189
190    fn add(self, other: Self) -> Self {
191        TropicalMin::add(&self, &other)
192    }
193}
194
195impl Mul for TropicalMin {
196    type Output = Self;
197
198    fn mul(self, other: Self) -> Self {
199        TropicalMin::mul(&self, &other)
200    }
201}
202
203#[cfg(test)]
204mod tests {
205    use super::*;
206
207    #[test]
208    fn test_tropical_zero_one() {
209        let zero = Tropical::ZERO;
210        let one = Tropical::ONE;
211        let a = Tropical::new(5.0);
212
213        // Zero is identity for max (use + operator which uses Add trait)
214        assert_eq!(zero + a, a);
215
216        // One is identity for + (use * operator which uses Mul trait)
217        assert_eq!(one * a, a);
218    }
219
220    #[test]
221    fn test_tropical_associativity() {
222        let a = Tropical::new(1.0);
223        let b = Tropical::new(2.0);
224        let c = Tropical::new(3.0);
225
226        // (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)
227        assert_eq!((a + b) + c, a + (b + c));
228
229        // (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c)
230        assert_eq!((a * b) * c, a * (b * c));
231    }
232
233    #[test]
234    fn test_tropical_min_plus() {
235        let a = TropicalMin::new(3.0);
236        let b = TropicalMin::new(5.0);
237
238        assert_eq!((a + b).value(), 3.0); // min(3, 5) = 3
239        assert_eq!((a * b).value(), 8.0); // 3 + 5 = 8
240    }
241}
ruvector_math/tropical/semiring.rs

ruvector_math/tropical/
semiring.rs
