problemreductions/rules/
threedimensionalmatching_threematroidintersection.rs

1//! Reduction from ThreeDimensionalMatching to ThreeMatroidIntersection.
2
3use crate::models::set::{ThreeDimensionalMatching, ThreeMatroidIntersection};
4use crate::reduction;
5use crate::rules::traits::{ReduceTo, ReductionResult};
6
7/// Result of reducing ThreeDimensionalMatching to ThreeMatroidIntersection.
8#[derive(Debug, Clone)]
9pub struct ReductionThreeDimensionalMatchingToThreeMatroidIntersection {
10    target: ThreeMatroidIntersection,
11}
12
13impl ReductionResult for ReductionThreeDimensionalMatchingToThreeMatroidIntersection {
14    type Source = ThreeDimensionalMatching;
15    type Target = ThreeMatroidIntersection;
16
17    fn target_problem(&self) -> &ThreeMatroidIntersection {
18        &self.target
19    }
20
21    /// Each target ground-set element is exactly one source triple, so the
22    /// witness vector is preserved unchanged.
23    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
24        target_solution.to_vec()
25    }
26}
27
28#[reduction(overhead = {
29    ground_set_size = "num_triples",
30    num_groups = "3 * universe_size",
31    bound = "universe_size",
32})]
33impl ReduceTo<ThreeMatroidIntersection> for ThreeDimensionalMatching {
34    type Result = ReductionThreeDimensionalMatchingToThreeMatroidIntersection;
35
36    fn reduce_to(&self) -> Self::Result {
37        let mut w_groups = vec![Vec::new(); self.universe_size()];
38        let mut x_groups = vec![Vec::new(); self.universe_size()];
39        let mut y_groups = vec![Vec::new(); self.universe_size()];
40
41        for (triple_index, &(w, x, y)) in self.triples().iter().enumerate() {
42            w_groups[w].push(triple_index);
43            x_groups[x].push(triple_index);
44            y_groups[y].push(triple_index);
45        }
46
47        ReductionThreeDimensionalMatchingToThreeMatroidIntersection {
48            target: ThreeMatroidIntersection::new(
49                self.num_triples(),
50                vec![w_groups, x_groups, y_groups],
51                self.universe_size(),
52            ),
53        }
54    }
55}
56
57#[cfg(feature = "example-db")]
58pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
59    use crate::export::SolutionPair;
60
61    vec![crate::example_db::specs::RuleExampleSpec {
62        id: "threedimensionalmatching_to_threematroidintersection",
63        build: || {
64            crate::example_db::specs::rule_example_with_witness::<_, ThreeMatroidIntersection>(
65                ThreeDimensionalMatching::new(
66                    3,
67                    vec![(0, 0, 0), (1, 1, 1), (2, 2, 2), (0, 1, 2), (1, 2, 0)],
68                ),
69                SolutionPair {
70                    source_config: vec![1, 1, 1, 0, 0],
71                    target_config: vec![1, 1, 1, 0, 0],
72                },
73            )
74        },
75    }]
76}
77
78#[cfg(test)]
79#[path = "../unit_tests/rules/threedimensionalmatching_threematroidintersection.rs"]
80mod tests;
problemreductions/rules/threedimensionalmatching_threematroidintersection.rs

problemreductions/rules/
threedimensionalmatching_threematroidintersection.rs
