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::{FieldInfo, 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        module_path: module_path!(),
18        description: "Overlay binary-matrix rows into a short storage vector by shifting each row without collisions",
19        fields: &[
20            FieldInfo { name: "matrix", type_name: "Vec<Vec<bool>>", description: "m x n binary matrix A" },
21            FieldInfo { name: "bound_k", type_name: "usize", description: "Maximum shift range K" },
22        ],
23    }
24}
25
26/// Sparse Matrix Compression.
27///
28/// A configuration assigns one zero-based shift value to each row. The
29/// implementation reconstructs the implied storage vector internally instead of
30/// enumerating storage-vector entries directly, so brute-force search runs over
31/// `bound_k ^ num_rows` shift assignments.
32#[derive(Debug, Clone, Serialize, Deserialize)]
33pub struct SparseMatrixCompression {
34    matrix: Vec<Vec<bool>>,
35    bound_k: usize,
36}
37
38impl SparseMatrixCompression {
39    /// Create a new SparseMatrixCompression instance.
40    ///
41    /// # Panics
42    ///
43    /// Panics if `bound_k == 0` or if the matrix rows are ragged.
44    pub fn new(matrix: Vec<Vec<bool>>, bound_k: usize) -> Self {
45        assert!(bound_k > 0, "bound_k must be positive");
46
47        let num_cols = matrix.first().map_or(0, Vec::len);
48        for row in &matrix {
49            assert_eq!(row.len(), num_cols, "All rows must have the same length");
50        }
51
52        Self { matrix, bound_k }
53    }
54
55    /// Return the binary matrix.
56    pub fn matrix(&self) -> &[Vec<bool>] {
57        &self.matrix
58    }
59
60    /// Return the shift bound `K`.
61    pub fn bound_k(&self) -> usize {
62        self.bound_k
63    }
64
65    /// Return the number of rows `m`.
66    pub fn num_rows(&self) -> usize {
67        self.matrix.len()
68    }
69
70    /// Return the number of columns `n`.
71    pub fn num_cols(&self) -> usize {
72        self.matrix.first().map_or(0, Vec::len)
73    }
74
75    /// Return the storage-vector length `n + K`.
76    pub fn storage_len(&self) -> usize {
77        self.num_cols() + self.bound_k
78    }
79
80    /// Decode a zero-based config into the one-based shifts used in the
81    /// mathematical definition.
82    pub fn decode_shifts(&self, config: &[usize]) -> Option<Vec<usize>> {
83        if config.len() != self.num_rows() || config.iter().any(|&shift| shift >= self.bound_k) {
84            return None;
85        }
86
87        Some(config.iter().map(|&shift| shift + 1).collect())
88    }
89
90    /// Construct the implied storage vector for a shift assignment.
91    ///
92    /// Returns `None` if the shifts are malformed or if the overlay is invalid.
93    /// Row labels are stored as `1..=m`; `0` denotes an unused storage slot.
94    pub fn storage_vector(&self, config: &[usize]) -> Option<Vec<usize>> {
95        let shifts = self.decode_shifts(config)?;
96        let mut storage = vec![0; self.storage_len()];
97
98        for (row_idx, row) in self.matrix.iter().enumerate() {
99            let row_label = row_idx + 1;
100            let shift_offset = shifts[row_idx] - 1;
101
102            for (col_idx, &entry) in row.iter().enumerate() {
103                if !entry {
104                    continue;
105                }
106
107                let slot_idx = shift_offset + col_idx;
108                let slot = &mut storage[slot_idx];
109                if *slot != 0 && *slot != row_label {
110                    return None;
111                }
112                *slot = row_label;
113            }
114        }
115
116        Some(storage)
117    }
118}
119
120impl Problem for SparseMatrixCompression {
121    const NAME: &'static str = "SparseMatrixCompression";
122    type Value = crate::types::Or;
123
124    fn dims(&self) -> Vec<usize> {
125        vec![self.bound_k; self.num_rows()]
126    }
127
128    fn evaluate(&self, config: &[usize]) -> crate::types::Or {
129        crate::types::Or(self.storage_vector(config).is_some())
130    }
131
132    fn variant() -> Vec<(&'static str, &'static str)> {
133        crate::variant_params![]
134    }
135}
136
137crate::declare_variants! {
138    default SparseMatrixCompression => "(bound_k ^ num_rows) * num_rows * num_cols",
139}
140
141#[cfg(feature = "example-db")]
142pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
143    vec![crate::example_db::specs::ModelExampleSpec {
144        id: "sparse_matrix_compression",
145        instance: Box::new(SparseMatrixCompression::new(
146            vec![
147                vec![true, false, false, true],
148                vec![false, true, false, false],
149                vec![false, false, true, false],
150                vec![true, false, false, false],
151            ],
152            2,
153        )),
154        optimal_config: vec![1, 1, 1, 0],
155        optimal_value: serde_json::json!(true),
156    }]
157}
158
159#[cfg(test)]
160#[path = "../../unit_tests/models/algebraic/sparse_matrix_compression.rs"]
161mod tests;
problemreductions/models/algebraic/sparse_matrix_compression.rs

problemreductions/models/algebraic/
sparse_matrix_compression.rs
