Skip to main content

clm_rust_core/cpn/
sparse.rs

1//! Compressed Sparse Incidence Matrix for High-Performance CPN Transition Evaluation (INV-419).
2//!
3//! Replaces dense 2D matrix traversals with compressed sparse adjacency lists.
4//! Provides zero-allocation in-place transition firing.
5
6use serde::{Deserialize, Serialize};
7
8#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
9pub struct SparseIncidenceMatrix {
10    pub place_count: usize,
11    pub trans_count: usize,
12    /// For each transition, list of (place_idx, tokens_consumed)
13    pub consumed: Vec<Vec<(usize, i64)>>,
14    /// For each transition, list of (place_idx, tokens_produced)
15    pub produced: Vec<Vec<(usize, i64)>>,
16    /// Net delta per transition: list of (place_idx, delta)
17    pub deltas: Vec<Vec<(usize, i64)>>,
18}
19
20impl SparseIncidenceMatrix {
21    /// Create a SparseIncidenceMatrix from a dense incidence matrix D (rows=places, cols=transitions).
22    pub fn from_dense(d: &[Vec<i64>], place_count: usize, trans_count: usize) -> Self {
23        let mut consumed = vec![Vec::new(); trans_count];
24        let mut produced = vec![Vec::new(); trans_count];
25        let mut deltas = vec![Vec::new(); trans_count];
26
27        for t in 0..trans_count {
28            for p in 0..place_count {
29                let val = if p < d.len() && t < d[p].len() {
30                    d[p][t]
31                } else {
32                    0
33                };
34                if val < 0 {
35                    consumed[t].push((p, -val));
36                    deltas[t].push((p, val));
37                } else if val > 0 {
38                    produced[t].push((p, val));
39                    deltas[t].push((p, val));
40                }
41            }
42        }
43
44        Self {
45            place_count,
46            trans_count,
47            consumed,
48            produced,
49            deltas,
50        }
51    }
52
53    /// Check if transition `t` is enabled under the given marking slice.
54    #[inline]
55    pub fn is_enabled(&self, t: usize, marking: &[i64]) -> bool {
56        if t >= self.trans_count {
57            return false;
58        }
59        for &(p, required) in &self.consumed[t] {
60            if p >= marking.len() || marking[p] < required {
61                return false;
62            }
63        }
64        true
65    }
66
67    /// Fire transition `t` in-place on `marking` with zero heap allocations.
68    /// Returns Ok(true) on success, or Err if transition was not enabled.
69    #[inline]
70    pub fn fire(&self, t: usize, marking: &mut [i64]) -> Result<(), &'static str> {
71        if !self.is_enabled(t, marking) {
72            return Err("Transition not enabled by current marking");
73        }
74
75        // Apply deltas directly
76        for &(p, delta) in &self.deltas[t] {
77            if p < marking.len() {
78                marking[p] += delta;
79            }
80        }
81        Ok(())
82    }
83
84    /// Compute the net delta vector for transition `t` into `out_delta`.
85    #[inline]
86    pub fn get_delta(&self, t: usize, out_delta: &mut [i64]) {
87        for v in out_delta.iter_mut() {
88            *v = 0;
89        }
90        if t < self.trans_count {
91            for &(p, delta) in &self.deltas[t] {
92                if p < out_delta.len() {
93                    out_delta[p] = delta;
94                }
95            }
96        }
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn test_sparse_from_dense_and_fire() {
106        // D: p0 -> t0 -> p1
107        // D = [ [-1], [1] ]
108        let d = vec![vec![-1], vec![1]];
109        let sparse = SparseIncidenceMatrix::from_dense(&d, 2, 1);
110
111        assert_eq!(sparse.consumed[0], vec![(0, 1)]);
112        assert_eq!(sparse.produced[0], vec![(1, 1)]);
113
114        let mut marking = vec![3, 0];
115        assert!(sparse.is_enabled(0, &marking));
116
117        sparse.fire(0, &mut marking).expect("Fire should succeed");
118        assert_eq!(marking, vec![2, 1]);
119
120        sparse.fire(0, &mut marking).expect("Fire should succeed");
121        assert_eq!(marking, vec![1, 2]);
122
123        sparse.fire(0, &mut marking).expect("Fire should succeed");
124        assert_eq!(marking, vec![0, 3]);
125
126        assert!(!sparse.is_enabled(0, &marking));
127        assert!(sparse.fire(0, &mut marking).is_err());
128    }
129}