problemreductions/models/algebraic/
sparse_matrix_compression.rs

1//! Sparse Matrix Compression problem implementation.
2//!
3//! Given an `m x n` binary matrix `A` and a positive integer `K`, determine
4//! whether the rows can be overlaid into a storage vector of length `n + K`
5//! by assigning each row a shift in `{1, ..., K}` without collisions.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "SparseMatrixCompression",
14        display_name: "Sparse Matrix Compression",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Algebraic,
18        module_path: module_path!(),
19        description: "Overlay binary-matrix rows into a short storage vector by shifting each row without collisions",
20        fields: SparseMatrixCompressionCreateSpec::FIELDS,
21    }
22}
23
24/// Sparse Matrix Compression.
25///
26/// A configuration assigns one zero-based shift value to each row. The
27/// implementation reconstructs the implied storage vector internally instead of
28/// enumerating storage-vector entries directly, so brute-force search runs over
29/// `bound_k ^ num_rows` shift assignments.
30#[derive(Debug, Clone, Serialize, Deserialize)]
31pub struct SparseMatrixCompression {
32    matrix: Vec<Vec<bool>>,
33    bound_k: usize,
34}
35
36#[derive(Debug, Deserialize, crate::CreateSpec)]
37struct SparseMatrixCompressionCreateSpec {
38    /// m x n binary matrix A.
39    matrix: Vec<Vec<bool>>,
40    /// Maximum shift range K.
41    bound_k: usize,
42}
43
44impl TryFrom<SparseMatrixCompressionCreateSpec> for SparseMatrixCompression {
45    type Error = crate::registry::ConstructionError;
46    fn try_from(spec: SparseMatrixCompressionCreateSpec) -> Result<Self, Self::Error> {
47        if spec.bound_k == 0 {
48            return Err("bound_k must be positive".to_string().into());
49        }
50        let columns = spec.matrix.first().map_or(0, Vec::len);
51        if spec.matrix.iter().any(|row| row.len() != columns) {
52            return Err("all matrix rows must have the same length"
53                .to_string()
54                .into());
55        }
56        Ok(Self::new(spec.matrix, spec.bound_k))
57    }
58}
59
60impl SparseMatrixCompression {
61    /// Create a new SparseMatrixCompression instance.
62    ///
63    /// # Panics
64    ///
65    /// Panics if `bound_k == 0` or if the matrix rows are ragged.
66    pub fn new(matrix: Vec<Vec<bool>>, bound_k: usize) -> Self {
67        assert!(bound_k > 0, "bound_k must be positive");
68
69        let num_cols = matrix.first().map_or(0, Vec::len);
70        for row in &matrix {
71            assert_eq!(row.len(), num_cols, "All rows must have the same length");
72        }
73
74        Self { matrix, bound_k }
75    }
76
77    /// Return the binary matrix.
78    pub fn matrix(&self) -> &[Vec<bool>] {
79        &self.matrix
80    }
81
82    /// Return the shift bound `K`.
83    pub fn bound_k(&self) -> usize {
84        self.bound_k
85    }
86
87    /// Return the number of rows `m`.
88    pub fn num_rows(&self) -> usize {
89        self.matrix.len()
90    }
91
92    /// Return the number of columns `n`.
93    pub fn num_cols(&self) -> usize {
94        self.matrix.first().map_or(0, Vec::len)
95    }
96
97    /// Return the storage-vector length `n + K`.
98    pub fn storage_len(&self) -> usize {
99        self.num_cols() + self.bound_k
100    }
101
102    /// Decode a zero-based config into the one-based shifts used in the
103    /// mathematical definition.
104    pub fn decode_shifts(&self, config: &[usize]) -> Option<Vec<usize>> {
105        if config.len() != self.num_rows() || config.iter().any(|&shift| shift >= self.bound_k) {
106            return None;
107        }
108
109        Some(config.iter().map(|&shift| shift + 1).collect())
110    }
111
112    /// Construct the implied storage vector for a shift assignment.
113    ///
114    /// Returns `None` if the shifts are malformed or if the overlay is invalid.
115    /// Row labels are stored as `1..=m`; `0` denotes an unused storage slot.
116    pub fn storage_vector(&self, config: &[usize]) -> Option<Vec<usize>> {
117        let shifts = self.decode_shifts(config)?;
118        let mut storage = vec![0; self.storage_len()];
119
120        for (row_idx, row) in self.matrix.iter().enumerate() {
121            let row_label = row_idx + 1;
122            let shift_offset = shifts[row_idx] - 1;
123
124            for (col_idx, &entry) in row.iter().enumerate() {
125                if !entry {
126                    continue;
127                }
128
129                let slot_idx = shift_offset + col_idx;
130                let slot = &mut storage[slot_idx];
131                if *slot != 0 && *slot != row_label {
132                    return None;
133                }
134                *slot = row_label;
135            }
136        }
137
138        Some(storage)
139    }
140}
141
142impl Problem for SparseMatrixCompression {
143    const NAME: &'static str = "SparseMatrixCompression";
144    type Solution = Vec<usize>;
145    type Value = crate::types::Or;
146
147    crate::problem_parameters![
148        ("bound_k", bound_k),
149        ("num_cols", num_cols),
150        ("num_rows", num_rows),
151    ];
152
153    fn evaluate(
154        &self,
155        config: &Self::Solution,
156    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
157        if config.len() != self.num_rows() {
158            return Err(crate::traits::EvaluationError::InvalidConfiguration(
159                "shift-vector length does not match the matrix rows".into(),
160            ));
161        }
162        if config.iter().any(|&shift| shift >= self.bound_k) {
163            return Err(crate::traits::EvaluationError::InvalidConfiguration(
164                "shift vector contains an out-of-range shift".into(),
165            ));
166        }
167        Ok(crate::types::Or(self.storage_vector(config).is_some()))
168    }
169
170    fn variant() -> Vec<(&'static str, &'static str)> {
171        crate::variant_params![]
172    }
173}
174
175impl crate::solvers::BruteForceProblem for SparseMatrixCompression {
176    fn dimensions(&self) -> Vec<usize> {
177        vec![self.bound_k; self.num_rows()]
178    }
179}
180
181crate::declare_variants! {
182    default SparseMatrixCompression => "(bound_k ^ num_rows) * num_rows * num_cols" create SparseMatrixCompressionCreateSpec,
183}
184
185crate::register_brute_force! {
186    SparseMatrixCompression,
187}
188
189#[cfg(feature = "example-db")]
190pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
191    vec![crate::example_db::specs::ModelExampleSpec {
192        id: "sparse_matrix_compression",
193        instance: Box::new(SparseMatrixCompression::new(
194            vec![
195                vec![true, false, false, true],
196                vec![false, true, false, false],
197                vec![false, false, true, false],
198                vec![true, false, false, false],
199            ],
200            2,
201        )),
202        optimal_config: serde_json::json!(vec![1, 1, 1, 0]),
203        optimal_value: serde_json::json!(true),
204    }]
205}
206
207#[cfg(test)]
208#[path = "../../unit_tests/models/algebraic/sparse_matrix_compression.rs"]
209mod tests;
problemreductions/models/algebraic/sparse_matrix_compression.rs

problemreductions/models/algebraic/
sparse_matrix_compression.rs
