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

ruvector_math/tropical/
semiring.rs
