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

problemreductions/models/set/
set_basis.rs
