problemreductions/models/set/
set_basis.rs

1//! Set Basis problem implementation.
2//!
3//! Given a collection of sets over a finite universe and an integer `k`,
4//! determine whether there exist `k` basis sets such that every target set
5//! can be reconstructed as a union of some subcollection of the basis.
6
7use crate::registry::{CreateSpec, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "SetBasis",
14        display_name: "Set Basis",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Set,
18        module_path: module_path!(),
19        description: "Determine whether a collection of sets admits a basis of size k under union",
20        fields: SetBasisCreateSpec::FIELDS,
21    }
22}
23
24/// The Set Basis decision problem.
25///
26/// Given a collection `C` of subsets of a finite set `S` and an integer `k`,
27/// determine whether there exists a collection `B` of exactly `k` subsets of
28/// `S` such that every set in `C` can be expressed as the union of some
29/// subcollection of `B`.
30#[derive(Debug, Clone, Serialize, Deserialize)]
31#[serde(try_from = "SetBasisData")]
32pub struct SetBasis {
33    /// Size of the universe (elements are `0..universe_size`).
34    universe_size: usize,
35    /// Collection of target sets.
36    collection: Vec<Vec<usize>>,
37    /// Number of basis sets to encode in a configuration.
38    k: usize,
39}
40
41#[derive(Deserialize)]
42struct SetBasisData {
43    universe_size: usize,
44    collection: Vec<Vec<usize>>,
45    k: usize,
46}
47
48impl TryFrom<SetBasisData> for SetBasis {
49    type Error = crate::registry::ConstructionError;
50
51    fn try_from(data: SetBasisData) -> Result<Self, Self::Error> {
52        Self::try_new(data.universe_size, data.collection, data.k)
53    }
54}
55
56#[derive(Debug, Deserialize, crate::CreateSpec)]
57struct SetBasisCreateSpec {
58    /// Size of the ground set S.
59    universe_size: usize,
60    /// Collection C of target subsets of S.
61    subsets: Vec<Vec<usize>>,
62    /// Required number of basis sets.
63    k: usize,
64}
65
66impl TryFrom<SetBasisCreateSpec> for SetBasis {
67    type Error = crate::registry::ConstructionError;
68
69    fn try_from(spec: SetBasisCreateSpec) -> Result<Self, Self::Error> {
70        Self::try_new(spec.universe_size, spec.subsets, spec.k)
71    }
72}
73
74impl SetBasis {
75    /// Create a new Set Basis instance.
76    ///
77    /// # Panics
78    ///
79    /// Panics if any element in `collection` lies outside the universe.
80    pub fn new(universe_size: usize, collection: Vec<Vec<usize>>, k: usize) -> Self {
81        Self::try_new(universe_size, collection, k).unwrap_or_else(|error| panic!("{error}"))
82    }
83
84    fn try_new(
85        universe_size: usize,
86        mut collection: Vec<Vec<usize>>,
87        k: usize,
88    ) -> Result<Self, crate::registry::ConstructionError> {
89        for (index, set) in collection.iter_mut().enumerate() {
90            set.sort_unstable();
91            set.dedup();
92            if let Some(element) = set.iter().find(|&&element| element >= universe_size) {
93                return Err(format!("set {index} contains element {element} outside universe of size {universe_size}").into());
94            }
95        }
96        Ok(Self {
97            universe_size,
98            collection,
99            k,
100        })
101    }
102
103    /// Return the universe size.
104    pub fn universe_size(&self) -> usize {
105        self.universe_size
106    }
107
108    /// Return the number of target sets.
109    pub fn num_sets(&self) -> usize {
110        self.collection.len()
111    }
112
113    /// Return the required basis size.
114    pub fn basis_size(&self) -> usize {
115        self.k
116    }
117
118    /// Return the target collection.
119    pub fn collection(&self) -> &[Vec<usize>] {
120        &self.collection
121    }
122
123    /// Return a single target set.
124    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
125        self.collection.get(index)
126    }
127
128    /// Check whether the configuration is a satisfying Set Basis solution.
129    pub fn is_valid_solution(
130        &self,
131        solution: &[Vec<bool>],
132    ) -> Result<bool, crate::traits::EvaluationError> {
133        if solution.len() != self.k
134            || solution
135                .iter()
136                .any(|subset| subset.len() != self.universe_size)
137        {
138            return Err(crate::traits::EvaluationError::InvalidConfiguration(
139                "set-basis dimensions do not match the instance".into(),
140            ));
141        }
142        let basis = Self::decode_basis(solution);
143        Ok(self
144            .collection
145            .iter()
146            .all(|target| Self::can_represent_target(&basis, target, self.universe_size)))
147    }
148
149    fn decode_basis(solution: &[Vec<bool>]) -> Vec<Vec<usize>> {
150        solution
151            .iter()
152            .map(|row| {
153                row.iter()
154                    .enumerate()
155                    .filter_map(|(element, &selected)| selected.then_some(element))
156                    .collect()
157            })
158            .collect()
159    }
160
161    fn is_subset(candidate: &[usize], target_membership: &[bool]) -> bool {
162        candidate.iter().all(|&element| target_membership[element])
163    }
164
165    fn can_represent_target(basis: &[Vec<usize>], target: &[usize], universe_size: usize) -> bool {
166        let mut target_membership = vec![false; universe_size];
167        for &element in target {
168            target_membership[element] = true;
169        }
170
171        let mut covered = vec![false; universe_size];
172        for subset in basis {
173            if Self::is_subset(subset, &target_membership) {
174                for &element in subset {
175                    covered[element] = true;
176                }
177            }
178        }
179
180        target.iter().all(|&element| covered[element])
181    }
182}
183
184impl Problem for SetBasis {
185    const NAME: &'static str = "SetBasis";
186    type Solution = Vec<Vec<bool>>;
187    type Value = crate::types::Or;
188
189    crate::problem_parameters![
190        ("universe_size", universe_size),
191        ("num_sets", num_sets),
192        ("basis_size", basis_size),
193    ];
194
195    fn evaluate(
196        &self,
197        solution: &Self::Solution,
198    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
199        Ok(crate::types::Or(self.is_valid_solution(solution)?))
200    }
201
202    fn variant() -> Vec<(&'static str, &'static str)> {
203        crate::variant_params![]
204    }
205}
206
207impl crate::solvers::BruteForceProblem for SetBasis {
208    fn dimensions(&self) -> Vec<usize> {
209        vec![2; self.k * self.universe_size]
210    }
211}
212
213crate::declare_variants! {
214    default SetBasis => "2^(basis_size * universe_size)" create SetBasisCreateSpec,
215}
216
217crate::register_brute_force! {
218    SetBasis decode |problem: &SetBasis, indices: Vec<usize>| if problem.universe_size() == 0 { vec![Vec::new(); problem.basis_size()] } else { indices.chunks(problem.universe_size()).map(crate::config::config_to_bits).collect() },
219}
220
221#[cfg(feature = "example-db")]
222pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
223    vec![crate::example_db::specs::ModelExampleSpec {
224        id: "set_basis",
225        instance: Box::new(SetBasis::new(
226            4,
227            vec![vec![0, 1], vec![1, 2], vec![0, 2], vec![0, 1, 2]],
228            3,
229        )),
230        optimal_config: serde_json::json!(vec![
231            vec![false, false, true, false],
232            vec![false, true, false, false],
233            vec![true, false, false, false]
234        ]),
235        optimal_value: serde_json::json!(true),
236    }]
237}
238
239#[cfg(test)]
240#[path = "../../unit_tests/models/set/set_basis.rs"]
241mod tests;
problemreductions/models/set/set_basis.rs

problemreductions/models/set/
set_basis.rs
