problemreductions/models/set/
minimum_hitting_set.rs

1//! Minimum Hitting Set problem implementation.
2//!
3//! The Minimum Hitting Set problem asks for a minimum-size subset of universe
4//! elements that intersects every set in a collection.
5
6use crate::registry::{CreateSpec, ProblemSchemaEntry};
7use crate::traits::Problem;
8use crate::types::Min;
9use serde::{Deserialize, Serialize};
10
11inventory::submit! {
12    ProblemSchemaEntry {
13        name: "MinimumHittingSet",
14        display_name: "Minimum Hitting Set",
15        aliases: &[],
16        dimensions: &[],
17        category: crate::registry::ProblemCategory::Set,
18        module_path: module_path!(),
19        description: "Find a minimum-size subset of universe elements that hits every set",
20        fields: MinimumHittingSetCreateSpec::FIELDS,
21    }
22}
23
24/// The Minimum Hitting Set problem.
25///
26/// Given a universe `U` and a collection of subsets of `U`, find a minimum-size
27/// subset `H ⊆ U` such that `H` intersects every set in the collection.
28#[derive(Debug, Clone, Serialize, Deserialize)]
29#[serde(try_from = "MinimumHittingSetData")]
30pub struct MinimumHittingSet {
31    universe_size: usize,
32    sets: Vec<Vec<usize>>,
33}
34
35#[derive(Deserialize)]
36struct MinimumHittingSetData {
37    universe_size: usize,
38    sets: Vec<Vec<usize>>,
39}
40
41impl TryFrom<MinimumHittingSetData> for MinimumHittingSet {
42    type Error = crate::registry::ConstructionError;
43
44    fn try_from(data: MinimumHittingSetData) -> Result<Self, Self::Error> {
45        Self::try_new(data.universe_size, data.sets)
46    }
47}
48
49#[derive(Debug, Deserialize, crate::CreateSpec)]
50struct MinimumHittingSetCreateSpec {
51    /// Size of the universe U.
52    universe_size: usize,
53    /// Collection of subsets of U that must each be hit.
54    subsets: Vec<Vec<usize>>,
55}
56
57impl TryFrom<MinimumHittingSetCreateSpec> for MinimumHittingSet {
58    type Error = crate::registry::ConstructionError;
59
60    fn try_from(spec: MinimumHittingSetCreateSpec) -> Result<Self, Self::Error> {
61        Self::try_new(spec.universe_size, spec.subsets)
62    }
63}
64
65impl MinimumHittingSet {
66    /// Create a new Minimum Hitting Set instance.
67    ///
68    /// # Panics
69    ///
70    /// Panics if any set contains an element outside `0..universe_size`.
71    pub fn new(universe_size: usize, sets: Vec<Vec<usize>>) -> Self {
72        Self::try_new(universe_size, sets).unwrap_or_else(|error| panic!("{error}"))
73    }
74
75    fn try_new(
76        universe_size: usize,
77        mut sets: Vec<Vec<usize>>,
78    ) -> Result<Self, crate::registry::ConstructionError> {
79        for (index, set) in sets.iter_mut().enumerate() {
80            set.sort_unstable();
81            set.dedup();
82            if let Some(element) = set.iter().find(|&&element| element >= universe_size) {
83                return Err(format!("set {index} contains element {element} outside universe of size {universe_size}").into());
84            }
85        }
86        Ok(Self {
87            universe_size,
88            sets,
89        })
90    }
91
92    /// Get the universe size.
93    pub fn universe_size(&self) -> usize {
94        self.universe_size
95    }
96
97    /// Get the number of sets.
98    pub fn num_sets(&self) -> usize {
99        self.sets.len()
100    }
101
102    /// Get the sets.
103    pub fn sets(&self) -> &[Vec<usize>] {
104        &self.sets
105    }
106
107    /// Get a specific set.
108    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
109        self.sets.get(index)
110    }
111
112    /// Decode the selected universe elements from a binary configuration.
113    pub fn selected_elements(&self, config: &[bool]) -> Option<Vec<usize>> {
114        if config.len() != self.universe_size {
115            return None;
116        }
117
118        let mut selected = Vec::new();
119        for (element, &is_selected) in config.iter().enumerate() {
120            if is_selected {
121                selected.push(element);
122            }
123        }
124        Some(selected)
125    }
126
127    /// Check whether a configuration hits every set in the collection.
128    pub fn is_valid_solution(&self, config: &[bool]) -> bool {
129        let Some(selected) = self.selected_elements(config) else {
130            return false;
131        };
132
133        self.sets.iter().all(|set| {
134            set.iter()
135                .any(|element| selected.binary_search(element).is_ok())
136        })
137    }
138}
139
140impl Problem for MinimumHittingSet {
141    const NAME: &'static str = "MinimumHittingSet";
142    type Solution = Vec<bool>;
143    type Value = Min<i64>;
144
145    crate::problem_parameters![("num_sets", num_sets), ("universe_size", universe_size),];
146
147    fn evaluate(
148        &self,
149        config: &Self::Solution,
150    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
151        Ok({
152            let Some(selected) = self.selected_elements(config) else {
153                return Err(crate::traits::EvaluationError::InvalidConfiguration(
154                    "element-selection length does not match the universe".into(),
155                ));
156            };
157
158            if self.sets.iter().all(|set| {
159                set.iter()
160                    .any(|element| selected.binary_search(element).is_ok())
161            }) {
162                Min(Some(i64::try_from(selected.len()).map_err(|_| {
163                    crate::traits::EvaluationError::IntegerOverflow(
164                        "converting hitting-set cardinality to i64".into(),
165                    )
166                })?))
167            } else {
168                Min(None)
169            }
170        })
171    }
172
173    fn variant() -> Vec<(&'static str, &'static str)> {
174        crate::variant_params![]
175    }
176}
177
178impl crate::solvers::BruteForceProblem for MinimumHittingSet {
179    fn dimensions(&self) -> Vec<usize> {
180        vec![2; self.universe_size]
181    }
182}
183
184crate::declare_variants! {
185    default MinimumHittingSet => "2^universe_size" create MinimumHittingSetCreateSpec,
186}
187
188crate::register_brute_force! {
189    MinimumHittingSet decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
190}
191
192#[cfg(feature = "example-db")]
193pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
194    vec![crate::example_db::specs::ModelExampleSpec {
195        id: "minimum_hitting_set",
196        instance: Box::new(MinimumHittingSet::new(
197            6,
198            vec![
199                vec![0, 1, 2],
200                vec![0, 3, 4],
201                vec![1, 3, 5],
202                vec![2, 4, 5],
203                vec![0, 1, 5],
204                vec![2, 3],
205                vec![1, 4],
206            ],
207        )),
208        optimal_config: serde_json::json!(vec![false, true, false, true, true, false]),
209        optimal_value: serde_json::json!(3),
210    }]
211}
212
213#[cfg(test)]
214#[path = "../../unit_tests/models/set/minimum_hitting_set.rs"]
215mod tests;
problemreductions/models/set/minimum_hitting_set.rs

problemreductions/models/set/
minimum_hitting_set.rs
