problemreductions/rules/
minimumvertexcover_minimumsetcovering.rs

1//! Reduction from MinimumVertexCover to MinimumSetCovering.
2//!
3//! Each vertex becomes a set containing the edges it covers.
4//! The universe is the set of all edges (labeled 0 to num_edges-1).
5
6use crate::models::graph::MinimumVertexCover;
7use crate::models::set::MinimumSetCovering;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::types::WeightElement;
12
13/// Result of reducing MinimumVertexCover to MinimumSetCovering.
14#[derive(Debug, Clone)]
15pub struct ReductionVCToSC<W> {
16    target: MinimumSetCovering<W>,
17}
18
19impl<W> ReductionResult for ReductionVCToSC<W>
20where
21    W: WeightElement + crate::variant::VariantParam,
22{
23    type Source = MinimumVertexCover<SimpleGraph, W>;
24    type Target = MinimumSetCovering<W>;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    /// Solution extraction: variables correspond 1:1.
31    /// Vertex i in VC corresponds to set i in SC.
32    fn extract_solution(
33        &self,
34        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
35    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
36        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
37
38        Ok(target_solution.to_vec())
39    }
40}
41
42#[reduction(
43    transform = exact {
44        num_sets = "num_vertices",
45        universe_size = "num_edges",
46    }
47)]
48impl ReduceTo<MinimumSetCovering<i64>> for MinimumVertexCover<SimpleGraph, i64> {
49    type Result = ReductionVCToSC<i64>;
50
51    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
52        let edges = self.graph().edges();
53        let num_edges = edges.len();
54        let num_vertices = self.graph().num_vertices();
55
56        // For each vertex, create a set of edge indices that it covers.
57        // An edge (u, v) with index i is covered by vertex j if j == u or j == v.
58        let sets: Vec<Vec<usize>> = (0..num_vertices)
59            .map(|vertex| {
60                edges
61                    .iter()
62                    .enumerate()
63                    .filter(|(_, (u, v))| *u == vertex || *v == vertex)
64                    .map(|(edge_idx, _)| edge_idx)
65                    .collect()
66            })
67            .collect();
68
69        let target = MinimumSetCovering::with_weights(num_edges, sets, self.weights().to_vec());
70
71        Ok(ReductionVCToSC { target })
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
79    vec![crate::example_db::specs::RuleExampleSpec {
80        id: "minimumvertexcover_to_minimumsetcovering",
81        build: || {
82            let (n, edges) = crate::topology::small_graphs::petersen();
83            let source = MinimumVertexCover::new(SimpleGraph::new(n, edges), vec![1i64; 10]);
84            crate::example_db::specs::rule_example_with_witness::<_, MinimumSetCovering<i64>>(
85                source,
86                SolutionPair {
87                    source_config: serde_json::json!(vec![
88                        false, true, true, false, true, true, false, false, true, true
89                    ]),
90                    target_config: serde_json::json!(vec![
91                        false, true, true, false, true, true, false, false, true, true
92                    ]),
93                },
94            )
95        },
96    }]
97}
98
99#[cfg(test)]
100#[path = "../unit_tests/rules/minimumvertexcover_minimumsetcovering.rs"]
101mod tests;
problemreductions/rules/minimumvertexcover_minimumsetcovering.rs

problemreductions/rules/
minimumvertexcover_minimumsetcovering.rs
