sim_lib_discrete_algebra/
semiring.rs

1//! The [`Semiring`] trait: the algebraic core of the discrete-math family.
2//!
3//! A semiring is a set with two operations, `add` (combine alternatives) and
4//! `mul` (chain in sequence), each with an identity (`zero` and `one`). One
5//! generic matrix-closure engine over a semiring derives many graph algorithms:
6//! boolean closure gives reachability, min-plus closure gives shortest paths,
7//! counting powers count walks. See the instance modules for the standard
8//! semirings.
9
10/// A semiring: `(add, zero)` is a commutative monoid, `(mul, one)` is a monoid,
11/// `mul` distributes over `add`, and `zero` annihilates under `mul`.
12///
13/// Implementations must uphold, for all `a`, `b`, `c`:
14/// - `zero + a == a` and `a + zero == a`
15/// - `a + b == b + a` and `(a + b) + c == a + (b + c)`
16/// - `one * a == a` and `a * one == a`
17/// - `(a * b) * c == a * (b * c)`
18/// - `a * (b + c) == a*b + a*c` and `(a + b) * c == a*c + b*c`
19/// - `zero * a == zero` and `a * zero == zero`
20///
21/// # Examples
22///
23/// The standard instances differ only in what `add` and `mul` mean. Over
24/// [`MinPlus`](crate::MinPlus), `add` is `min` and `mul` is `+`, so chaining a
25/// path costs the sum of its edges while combining alternatives keeps the
26/// cheaper one:
27///
28/// ```
29/// use sim_lib_discrete_algebra::{MinPlus, Semiring};
30///
31/// let zero = MinPlus::zero(); // Inf: "no path"
32/// let one = MinPlus::one(); //  Fin(0): the empty path
33/// assert_eq!(one, MinPlus::Fin(0));
34///
35/// // mul chains in sequence (sum of weights); add picks the cheaper route.
36/// assert_eq!(MinPlus::Fin(2).mul(&MinPlus::Fin(3)), MinPlus::Fin(5));
37/// assert_eq!(MinPlus::Fin(2).add(&MinPlus::Fin(3)), MinPlus::Fin(2));
38///
39/// // zero annihilates under mul and is the additive identity.
40/// assert_eq!(zero.mul(&MinPlus::Fin(7)), zero);
41/// assert_eq!(zero.add(&MinPlus::Fin(7)), MinPlus::Fin(7));
42/// ```
43pub trait Semiring: Clone + PartialEq + core::fmt::Debug {
44    /// The additive identity, also meaning "no value" / "no path".
45    fn zero() -> Self;
46    /// The multiplicative identity.
47    fn one() -> Self;
48    /// Combine two alternatives.
49    fn add(&self, other: &Self) -> Self;
50    /// Chain two values in sequence.
51    fn mul(&self, other: &Self) -> Self;
52    /// Whether this value is the additive identity.
53    fn is_zero(&self) -> bool {
54        *self == Self::zero()
55    }
56    /// The Kleene star `1 + a + a^2 + ...` when it converges, else `None`.
57    ///
58    /// Present only for closed semirings. The default is `None`.
59    fn star(&self) -> Option<Self> {
60        None
61    }
62}
63
64#[cfg(test)]
65pub(crate) mod laws {
66    use super::Semiring;
67
68    /// Assert the semiring laws on a small sample set (all triples).
69    ///
70    /// `samples` should include `zero` and `one` plus a few ordinary values.
71    /// For floating-point semirings, pick values that are exact in the format.
72    pub(crate) fn assert_semiring_laws<S: Semiring>(samples: &[S]) {
73        let zero = S::zero();
74        let one = S::one();
75        for a in samples {
76            assert_eq!(zero.add(a), *a, "zero + a == a");
77            assert_eq!(a.add(&zero), *a, "a + zero == a");
78            assert_eq!(one.mul(a), *a, "one * a == a");
79            assert_eq!(a.mul(&one), *a, "a * one == a");
80            assert_eq!(zero.mul(a), zero, "zero * a == zero");
81            assert_eq!(a.mul(&zero), zero, "a * zero == zero");
82            assert_eq!(a.is_zero(), *a == zero, "is_zero agrees with == zero");
83        }
84        for a in samples {
85            for b in samples {
86                assert_eq!(a.add(b), b.add(a), "add is commutative");
87                for c in samples {
88                    assert_eq!(a.add(b).add(c), a.add(&b.add(c)), "add is associative");
89                    assert_eq!(a.mul(b).mul(c), a.mul(&b.mul(c)), "mul is associative");
90                    assert_eq!(
91                        a.mul(&b.add(c)),
92                        a.mul(b).add(&a.mul(c)),
93                        "left distributive"
94                    );
95                    assert_eq!(
96                        a.add(b).mul(c),
97                        a.mul(c).add(&b.mul(c)),
98                        "right distributive"
99                    );
100                }
101            }
102        }
103    }
104}
sim_lib_discrete_algebra/semiring.rs

sim_lib_discrete_algebra/
semiring.rs
