sim_lib_discrete_algebra/
counting.rs

1//! The counting semiring over `BigUint`. Powers count walks; closure counts
2//! paths in a nilpotent (acyclic) setting.
3
4use crate::semiring::Semiring;
5use num_bigint::BigUint;
6
7/// Natural-number counting semiring: `add` is `+`, `mul` is `*`.
8///
9/// `A^k[i][j]` over this semiring counts the walks of length `k` from `i` to
10/// `j`. The closure converges only when the matrix is nilpotent (acyclic);
11/// otherwise the closure engine raises a limit error.
12#[derive(Debug, Clone, PartialEq, Eq)]
13pub struct Counting(pub BigUint);
14
15impl Counting {
16    /// Construct from a small machine integer for convenience.
17    pub fn from_u64(value: u64) -> Self {
18        Counting(BigUint::from(value))
19    }
20}
21
22impl Semiring for Counting {
23    fn zero() -> Self {
24        Counting(BigUint::default())
25    }
26    fn one() -> Self {
27        Counting(BigUint::from(1u32))
28    }
29    fn add(&self, other: &Self) -> Self {
30        Counting(&self.0 + &other.0)
31    }
32    fn mul(&self, other: &Self) -> Self {
33        Counting(&self.0 * &other.0)
34    }
35    fn is_zero(&self) -> bool {
36        self.0 == BigUint::default()
37    }
38    /// `1 + a + a^2 + ...` is finite only when `a == 0`, giving `1`.
39    fn star(&self) -> Option<Self> {
40        if self.is_zero() {
41            Some(Self::one())
42        } else {
43            None
44        }
45    }
46}
47
48#[cfg(test)]
49mod tests {
50    use super::*;
51    use crate::semiring::laws::assert_semiring_laws;
52
53    #[test]
54    fn laws_hold() {
55        assert_semiring_laws(&[
56            Counting::from_u64(0),
57            Counting::from_u64(1),
58            Counting::from_u64(3),
59            Counting::from_u64(7),
60        ]);
61    }
62
63    #[test]
64    fn star_behaviour() {
65        assert_eq!(Counting::from_u64(0).star(), Some(Counting::from_u64(1)));
66        assert_eq!(Counting::from_u64(1).star(), None);
67        assert_eq!(Counting::from_u64(9).star(), None);
68    }
69}
sim_lib_discrete_algebra/counting.rs

sim_lib_discrete_algebra/
counting.rs
