problemreductions/rules/
maximummatching_maximumsetpacking.rs

1//! Reductions between MaximumMatching and MaximumSetPacking problems.
2//!
3//! MaximumMatching -> MaximumSetPacking: Each edge becomes a set containing its two endpoint vertices.
4//! For edge (u, v), create set = {u, v}. Weights are preserved from edges.
5
6use crate::models::graph::MaximumMatching;
7use crate::models::set::MaximumSetPacking;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::types::WeightElement;
12
13/// Result of reducing MaximumMatching to MaximumSetPacking.
14#[derive(Debug, Clone)]
15pub struct ReductionMatchingToSP<G, W> {
16    target: MaximumSetPacking<W>,
17    _marker: std::marker::PhantomData<G>,
18}
19
20impl<G, W> ReductionResult for ReductionMatchingToSP<G, W>
21where
22    G: Graph + crate::variant::VariantParam,
23    W: WeightElement + crate::variant::VariantParam,
24{
25    type Source = MaximumMatching<G, W>;
26    type Target = MaximumSetPacking<W>;
27
28    fn target_problem(&self) -> &Self::Target {
29        &self.target
30    }
31
32    /// Solutions map directly: edge i in MaximumMatching = set i in MaximumSetPacking.
33    fn extract_solution(
34        &self,
35        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
36    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
37        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
38
39        Ok(target_solution.to_vec())
40    }
41}
42
43// Each edge contributes exactly one set. The target universe ends at the largest
44// endpoint label (or is empty), so trailing isolated vertices make its size < n.
45#[reduction(
46    transform = {
47        exact { num_sets = "num_edges" },
48        upper_bound { universe_size = "num_vertices" },
49    }
50)]
51impl ReduceTo<MaximumSetPacking<i64>> for MaximumMatching<SimpleGraph, i64> {
52    type Result = ReductionMatchingToSP<SimpleGraph, i64>;
53
54    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
55        let edges = self.edges();
56
57        // For each edge, create a set containing its two endpoint vertices
58        let sets: Vec<Vec<usize>> = edges.iter().map(|&(u, v, _)| vec![u, v]).collect();
59
60        // Preserve weights from edges
61        let weights = self.weights();
62
63        let target = MaximumSetPacking::with_weights(sets, weights).map_err(|cause| {
64            crate::rules::ReductionError::construction::<
65                MaximumMatching<SimpleGraph, i64>,
66                MaximumSetPacking<i64>,
67            >(cause)
68        })?;
69
70        Ok(ReductionMatchingToSP {
71            target,
72            _marker: std::marker::PhantomData,
73        })
74    }
75}
76
77#[cfg(feature = "example-db")]
78pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
79    use crate::export::SolutionPair;
80    use crate::models::set::MaximumSetPacking;
81
82    vec![crate::example_db::specs::RuleExampleSpec {
83        id: "maximummatching_to_maximumsetpacking",
84        build: || {
85            let (n, edges) = crate::topology::small_graphs::petersen();
86            let source = MaximumMatching::unit_weights(SimpleGraph::new(n, edges));
87            crate::example_db::specs::rule_example_with_witness::<_, MaximumSetPacking<i64>>(
88                source,
89                SolutionPair {
90                    source_config: serde_json::json!(vec![
91                        false, false, true, true, false, false, false, true, false, false, false,
92                        false, true, false, true
93                    ]),
94                    target_config: serde_json::json!(vec![
95                        false, false, true, true, false, false, false, true, false, false, false,
96                        false, true, false, true
97                    ]),
98                },
99            )
100        },
101    }]
102}
103
104#[cfg(test)]
105#[path = "../unit_tests/rules/maximummatching_maximumsetpacking.rs"]
106mod tests;
problemreductions/rules/maximummatching_maximumsetpacking.rs

problemreductions/rules/
maximummatching_maximumsetpacking.rs
