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(test)]
66#[path = "../unit_tests/rules/maximummatching_maximumsetpacking.rs"]
67mod tests;
problemreductions/rules/maximummatching_maximumsetpacking.rs

problemreductions/rules/
maximummatching_maximumsetpacking.rs
