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::{FieldInfo, ProblemSchemaEntry, ProblemSizeFieldEntry};
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        module_path: module_path!(),
18        description: "Find a minimum-size subset of universe elements that hits every set",
19        fields: &[
20            FieldInfo { name: "universe_size", type_name: "usize", description: "Size of the universe U" },
21            FieldInfo { name: "sets", type_name: "Vec<Vec<usize>>", description: "Collection of subsets of U that must each be hit" },
22        ],
23    }
24}
25
26inventory::submit! {
27    ProblemSizeFieldEntry {
28        name: "MinimumHittingSet",
29        fields: &["num_sets", "universe_size"],
30    }
31}
32
33/// The Minimum Hitting Set problem.
34///
35/// Given a universe `U` and a collection of subsets of `U`, find a minimum-size
36/// subset `H ⊆ U` such that `H` intersects every set in the collection.
37#[derive(Debug, Clone, Serialize, Deserialize)]
38pub struct MinimumHittingSet {
39    universe_size: usize,
40    sets: Vec<Vec<usize>>,
41}
42
43impl MinimumHittingSet {
44    /// Create a new Minimum Hitting Set instance.
45    ///
46    /// # Panics
47    ///
48    /// Panics if any set contains an element outside `0..universe_size`.
49    pub fn new(universe_size: usize, sets: Vec<Vec<usize>>) -> Self {
50        let mut sets = sets;
51        for (set_index, set) in sets.iter_mut().enumerate() {
52            set.sort_unstable();
53            set.dedup();
54            for &element in set.iter() {
55                assert!(
56                    element < universe_size,
57                    "Set {set_index} contains element {element} which is outside universe of size {universe_size}"
58                );
59            }
60        }
61
62        Self {
63            universe_size,
64            sets,
65        }
66    }
67
68    /// Get the universe size.
69    pub fn universe_size(&self) -> usize {
70        self.universe_size
71    }
72
73    /// Get the number of sets.
74    pub fn num_sets(&self) -> usize {
75        self.sets.len()
76    }
77
78    /// Get the sets.
79    pub fn sets(&self) -> &[Vec<usize>] {
80        &self.sets
81    }
82
83    /// Get a specific set.
84    pub fn get_set(&self, index: usize) -> Option<&Vec<usize>> {
85        self.sets.get(index)
86    }
87
88    /// Decode the selected universe elements from a binary configuration.
89    pub fn selected_elements(&self, config: &[usize]) -> Option<Vec<usize>> {
90        if config.len() != self.universe_size {
91            return None;
92        }
93
94        let mut selected = Vec::new();
95        for (element, &value) in config.iter().enumerate() {
96            match value {
97                0 => {}
98                1 => selected.push(element),
99                _ => return None,
100            }
101        }
102        Some(selected)
103    }
104
105    /// Check whether a configuration hits every set in the collection.
106    pub fn is_valid_solution(&self, config: &[usize]) -> bool {
107        let Some(selected) = self.selected_elements(config) else {
108            return false;
109        };
110
111        self.sets.iter().all(|set| {
112            set.iter()
113                .any(|element| selected.binary_search(element).is_ok())
114        })
115    }
116}
117
118impl Problem for MinimumHittingSet {
119    const NAME: &'static str = "MinimumHittingSet";
120    type Value = Min<usize>;
121
122    fn dims(&self) -> Vec<usize> {
123        vec![2; self.universe_size]
124    }
125
126    fn evaluate(&self, config: &[usize]) -> Min<usize> {
127        let Some(selected) = self.selected_elements(config) else {
128            return Min(None);
129        };
130
131        if self.sets.iter().all(|set| {
132            set.iter()
133                .any(|element| selected.binary_search(element).is_ok())
134        }) {
135            Min(Some(selected.len()))
136        } else {
137            Min(None)
138        }
139    }
140
141    fn variant() -> Vec<(&'static str, &'static str)> {
142        crate::variant_params![]
143    }
144}
145
146crate::declare_variants! {
147    default MinimumHittingSet => "2^universe_size",
148}
149
150#[cfg(feature = "example-db")]
151pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
152    vec![crate::example_db::specs::ModelExampleSpec {
153        id: "minimum_hitting_set",
154        instance: Box::new(MinimumHittingSet::new(
155            6,
156            vec![
157                vec![0, 1, 2],
158                vec![0, 3, 4],
159                vec![1, 3, 5],
160                vec![2, 4, 5],
161                vec![0, 1, 5],
162                vec![2, 3],
163                vec![1, 4],
164            ],
165        )),
166        optimal_config: vec![0, 1, 0, 1, 1, 0],
167        optimal_value: serde_json::json!(3),
168    }]
169}
170
171#[cfg(test)]
172#[path = "../../unit_tests/models/set/minimum_hitting_set.rs"]
173mod tests;
problemreductions/models/set/minimum_hitting_set.rs

problemreductions/models/set/
minimum_hitting_set.rs
