problemreductions/models/set/
three_dimensional_matching.rs

1//! Three-Dimensional Matching (3DM) problem implementation.
2//!
3//! Given disjoint sets W, X, Y each with q elements and a set M of triples
4//! (w, x, y) with w in W, x in X, y in Y, determine if there exists a
5//! matching M' of size q where no two triples agree in any coordinate.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use serde::{Deserialize, Serialize};
10use std::collections::HashSet;
11
12inventory::submit! {
13    ProblemSchemaEntry {
14        name: "ThreeDimensionalMatching",
15        display_name: "Three-Dimensional Matching",
16        aliases: &["3DM"],
17        dimensions: &[],
18        category: crate::registry::ProblemCategory::Set,
19        module_path: module_path!(),
20        description: "Find a perfect matching in a tripartite hypergraph",
21        fields: &[
22            FieldInfo { name: "universe_size", type_name: "usize", description: "Size of each set W, X, Y (q)" },
23            FieldInfo { name: "triples", type_name: "Vec<(usize, usize, usize)>", description: "Set M of triples (w, x, y)" },
24        ],
25    }
26}
27
28/// Three-Dimensional Matching (3DM) problem.
29///
30/// Given disjoint sets W = {0, ..., q-1}, X = {0, ..., q-1}, Y = {0, ..., q-1}
31/// and a set M of triples (w, x, y) where w is in W, x is in X, y is in Y,
32/// determine if there exists a subset M' of M with |M'| = q such that no two
33/// triples in M' agree in any coordinate.
34///
35/// This is a classical NP-complete problem (Karp, 1972), closely related to
36/// Exact Cover by 3-Sets.
37///
38/// # Example
39///
40/// ```
41/// use problemreductions::models::set::ThreeDimensionalMatching;
42/// use problemreductions::{Problem, BruteForce};
43///
44/// // W = X = Y = {0, 1, 2} (q = 3)
45/// // Triples: (0,1,2), (1,0,1), (2,2,0), (0,0,0), (1,2,2)
46/// let problem = ThreeDimensionalMatching::new(
47///     3,
48///     vec![(0, 1, 2), (1, 0, 1), (2, 2, 0), (0, 0, 0), (1, 2, 2)],
49/// );
50///
51/// let solver = BruteForce::new();
52/// let solutions = solver.find_all_witnesses(&problem).unwrap();
53///
54/// // First three triples form a valid matching
55/// assert!(!solutions.is_empty());
56/// assert!(problem.evaluate(&solutions[0]).unwrap());
57/// ```
58#[derive(Debug, Clone, Serialize, Deserialize)]
59#[serde(try_from = "ThreeDimensionalMatchingData")]
60pub struct ThreeDimensionalMatching {
61    /// Size of each set W, X, Y (elements are 0..universe_size).
62    universe_size: usize,
63    /// Set M of triples (w, x, y) where w, x, y are in 0..universe_size.
64    triples: Vec<(usize, usize, usize)>,
65}
66
67#[derive(Deserialize)]
68struct ThreeDimensionalMatchingData {
69    universe_size: usize,
70    triples: Vec<(usize, usize, usize)>,
71}
72
73impl TryFrom<ThreeDimensionalMatchingData> for ThreeDimensionalMatching {
74    type Error = crate::registry::ConstructionError;
75
76    fn try_from(data: ThreeDimensionalMatchingData) -> Result<Self, Self::Error> {
77        Self::try_new(data.universe_size, data.triples)
78    }
79}
80
81impl ThreeDimensionalMatching {
82    /// Create a new 3DM problem.
83    ///
84    /// # Panics
85    ///
86    /// Panics if any triple contains an element outside 0..universe_size.
87    pub fn new(universe_size: usize, triples: Vec<(usize, usize, usize)>) -> Self {
88        Self::try_new(universe_size, triples).unwrap_or_else(|error| panic!("{error}"))
89    }
90
91    fn try_new(
92        universe_size: usize,
93        triples: Vec<(usize, usize, usize)>,
94    ) -> Result<Self, crate::registry::ConstructionError> {
95        for (index, &(w, x, y)) in triples.iter().enumerate() {
96            if w >= universe_size || x >= universe_size || y >= universe_size {
97                return Err(format!(
98                    "triple {index} contains a coordinate outside 0..{universe_size}"
99                )
100                .into());
101            }
102        }
103        Ok(Self {
104            universe_size,
105            triples,
106        })
107    }
108
109    /// Get the universe size (q).
110    pub fn universe_size(&self) -> usize {
111        self.universe_size
112    }
113
114    /// Get the number of triples in M.
115    pub fn num_triples(&self) -> usize {
116        self.triples.len()
117    }
118
119    /// Get the triples.
120    pub fn triples(&self) -> &[(usize, usize, usize)] {
121        &self.triples
122    }
123
124    /// Get a specific triple.
125    pub fn get_triple(&self, index: usize) -> Option<&(usize, usize, usize)> {
126        self.triples.get(index)
127    }
128}
129
130impl Problem for ThreeDimensionalMatching {
131    const NAME: &'static str = "ThreeDimensionalMatching";
132    type Solution = Vec<bool>;
133    type Value = crate::types::Or;
134
135    crate::problem_parameters![
136        ("num_triples", num_triples),
137        ("universe_size", universe_size),
138    ];
139
140    fn evaluate(
141        &self,
142        config: &Self::Solution,
143    ) -> Result<crate::types::Or, crate::traits::EvaluationError> {
144        Ok({
145            crate::types::Or({
146                if config.len() != self.triples.len() {
147                    return Err(crate::traits::EvaluationError::InvalidConfiguration(
148                        "triple-selection length does not match the instance".into(),
149                    ));
150                }
151
152                // Count selected triples
153                let selected_count = config.iter().filter(|&&v| v).count();
154                if selected_count != self.universe_size {
155                    return Ok(crate::types::Or(false));
156                }
157
158                // Check that selected triples have all distinct coordinates
159                let mut used_w = HashSet::with_capacity(self.universe_size);
160                let mut used_x = HashSet::with_capacity(self.universe_size);
161                let mut used_y = HashSet::with_capacity(self.universe_size);
162
163                for (i, &selected) in config.iter().enumerate() {
164                    if selected {
165                        let (w, x, y) = self.triples[i];
166                        if !used_w.insert(w) {
167                            return Ok(crate::types::Or(false));
168                        }
169                        if !used_x.insert(x) {
170                            return Ok(crate::types::Or(false));
171                        }
172                        if !used_y.insert(y) {
173                            return Ok(crate::types::Or(false));
174                        }
175                    }
176                }
177
178                true
179            })
180        })
181    }
182
183    fn variant() -> Vec<(&'static str, &'static str)> {
184        crate::variant_params![]
185    }
186}
187
188impl crate::solvers::BruteForceProblem for ThreeDimensionalMatching {
189    fn dimensions(&self) -> Vec<usize> {
190        vec![2; self.triples.len()]
191    }
192}
193
194crate::declare_variants! {
195    default ThreeDimensionalMatching => "2^num_triples",
196}
197
198crate::register_brute_force! {
199    ThreeDimensionalMatching decode |_, indices: Vec<usize>| crate::config::config_to_bits(&indices),
200}
201
202#[cfg(feature = "example-db")]
203pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
204    vec![crate::example_db::specs::ModelExampleSpec {
205        id: "three_dimensional_matching",
206        instance: Box::new(ThreeDimensionalMatching::new(
207            3,
208            vec![(0, 1, 2), (1, 0, 1), (2, 2, 0), (0, 0, 0), (1, 2, 2)],
209        )),
210        optimal_config: serde_json::json!(vec![true, true, true, false, false]),
211        optimal_value: serde_json::json!(true),
212    }]
213}
214
215#[cfg(test)]
216#[path = "../../unit_tests/models/set/three_dimensional_matching.rs"]
217mod tests;
problemreductions/models/set/three_dimensional_matching.rs

problemreductions/models/set/
three_dimensional_matching.rs
