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#[reduction(
44    transform = exact {
45        num_sets = "num_edges",
46        universe_size = "num_vertices",
47    }
48)]
49impl ReduceTo<MaximumSetPacking<i64>> for MaximumMatching<SimpleGraph, i64> {
50    type Result = ReductionMatchingToSP<SimpleGraph, i64>;
51
52    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
53        let edges = self.edges();
54
55        // For each edge, create a set containing its two endpoint vertices
56        let sets: Vec<Vec<usize>> = edges.iter().map(|&(u, v, _)| vec![u, v]).collect();
57
58        // Preserve weights from edges
59        let weights = self.weights();
60
61        let target = MaximumSetPacking::with_weights(sets, weights).map_err(|cause| {
62            crate::rules::ReductionError::construction::<
63                MaximumMatching<SimpleGraph, i64>,
64                MaximumSetPacking<i64>,
65            >(cause)
66        })?;
67
68        Ok(ReductionMatchingToSP {
69            target,
70            _marker: std::marker::PhantomData,
71        })
72    }
73}
74
75#[cfg(feature = "example-db")]
76pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
77    use crate::export::SolutionPair;
78    use crate::models::set::MaximumSetPacking;
79
80    vec![crate::example_db::specs::RuleExampleSpec {
81        id: "maximummatching_to_maximumsetpacking",
82        build: || {
83            let (n, edges) = crate::topology::small_graphs::petersen();
84            let source = MaximumMatching::unit_weights(SimpleGraph::new(n, edges));
85            crate::example_db::specs::rule_example_with_witness::<_, MaximumSetPacking<i64>>(
86                source,
87                SolutionPair {
88                    source_config: serde_json::json!(vec![
89                        false, false, true, true, false, false, false, true, false, false, false,
90                        false, true, false, true
91                    ]),
92                    target_config: serde_json::json!(vec![
93                        false, false, true, true, false, false, false, true, false, false, false,
94                        false, true, false, true
95                    ]),
96                },
97            )
98        },
99    }]
100}
101
102#[cfg(test)]
103#[path = "../unit_tests/rules/maximummatching_maximumsetpacking.rs"]
104mod tests;
problemreductions/rules/maximummatching_maximumsetpacking.rs

problemreductions/rules/
maximummatching_maximumsetpacking.rs
