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(&self, target_solution: &[usize]) -> Vec<usize> {
34        target_solution.to_vec()
35    }
36}
37
38#[reduction(
39    overhead = {
40        num_sets = "num_edges",
41        universe_size = "num_vertices",
42    }
43)]
44impl ReduceTo<MaximumSetPacking<i32>> for MaximumMatching<SimpleGraph, i32> {
45    type Result = ReductionMatchingToSP<SimpleGraph, i32>;
46
47    fn reduce_to(&self) -> Self::Result {
48        let edges = self.edges();
49
50        // For each edge, create a set containing its two endpoint vertices
51        let sets: Vec<Vec<usize>> = edges.iter().map(|&(u, v, _)| vec![u, v]).collect();
52
53        // Preserve weights from edges
54        let weights = self.weights();
55
56        let target = MaximumSetPacking::with_weights(sets, weights);
57
58        ReductionMatchingToSP {
59            target,
60            _marker: std::marker::PhantomData,
61        }
62    }
63}
64
65#[cfg(feature = "example-db")]
66pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
67    use crate::export::SolutionPair;
68    use crate::models::set::MaximumSetPacking;
69
70    vec![crate::example_db::specs::RuleExampleSpec {
71        id: "maximummatching_to_maximumsetpacking",
72        build: || {
73            let (n, edges) = crate::topology::small_graphs::petersen();
74            let source = MaximumMatching::unit_weights(SimpleGraph::new(n, edges));
75            crate::example_db::specs::rule_example_with_witness::<_, MaximumSetPacking<i32>>(
76                source,
77                SolutionPair {
78                    source_config: vec![0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1],
79                    target_config: vec![0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1],
80                },
81            )
82        },
83    }]
84}
85
86#[cfg(test)]
87#[path = "../unit_tests/rules/maximummatching_maximumsetpacking.rs"]
88mod tests;
problemreductions/rules/maximummatching_maximumsetpacking.rs

problemreductions/rules/
maximummatching_maximumsetpacking.rs
