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

problemreductions/models/algebraic/
sparse_matrix_compression.rs
