problemreductions/rules/
vertexcovering_setcovering.rs

1//! Reduction from VertexCovering to SetCovering.
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::VertexCovering;
7use crate::models::set::SetCovering;
8use crate::rules::traits::{ReduceTo, ReductionResult};
9use crate::traits::Problem;
10use crate::types::ProblemSize;
11use num_traits::{Num, Zero};
12use std::ops::AddAssign;
13
14/// Result of reducing VertexCovering to SetCovering.
15#[derive(Debug, Clone)]
16pub struct ReductionVCToSC<W> {
17    target: SetCovering<W>,
18    source_size: ProblemSize,
19}
20
21impl<W> ReductionResult for ReductionVCToSC<W>
22where
23    W: Clone + Default + PartialOrd + Num + Zero + AddAssign + 'static,
24{
25    type Source = VertexCovering<W>;
26    type Target = SetCovering<W>;
27
28    fn target_problem(&self) -> &Self::Target {
29        &self.target
30    }
31
32    /// Solution extraction: variables correspond 1:1.
33    /// Vertex i in VC corresponds to set i in SC.
34    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
35        target_solution.to_vec()
36    }
37
38    fn source_size(&self) -> ProblemSize {
39        self.source_size.clone()
40    }
41
42    fn target_size(&self) -> ProblemSize {
43        self.target.problem_size()
44    }
45}
46
47impl<W> ReduceTo<SetCovering<W>> for VertexCovering<W>
48where
49    W: Clone + Default + PartialOrd + Num + Zero + AddAssign + From<i32> + 'static,
50{
51    type Result = ReductionVCToSC<W>;
52
53    fn reduce_to(&self) -> Self::Result {
54        let edges = self.edges();
55        let num_edges = edges.len();
56        let num_vertices = self.num_vertices();
57
58        // For each vertex, create a set of edge indices that it covers.
59        // An edge (u, v) with index i is covered by vertex j if j == u or j == v.
60        let sets: Vec<Vec<usize>> = (0..num_vertices)
61            .map(|vertex| {
62                edges
63                    .iter()
64                    .enumerate()
65                    .filter(|(_, (u, v))| *u == vertex || *v == vertex)
66                    .map(|(edge_idx, _)| edge_idx)
67                    .collect()
68            })
69            .collect();
70
71        let target = SetCovering::with_weights(num_edges, sets, self.weights_ref().clone());
72
73        ReductionVCToSC {
74            target,
75            source_size: self.problem_size(),
76        }
77    }
78}
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use crate::solvers::{BruteForce, Solver};
84    use crate::traits::ConstraintSatisfactionProblem;
85
86    #[test]
87    fn test_vc_to_sc_basic() {
88        // Path graph 0-1-2 with edges (0,1) and (1,2)
89        // Vertex 0 covers edge 0
90        // Vertex 1 covers edges 0 and 1
91        // Vertex 2 covers edge 1
92        let vc_problem = VertexCovering::<i32>::new(3, vec![(0, 1), (1, 2)]);
93        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
94        let sc_problem = reduction.target_problem();
95
96        // Check the sets are constructed correctly
97        assert_eq!(sc_problem.universe_size(), 2); // 2 edges
98        assert_eq!(sc_problem.num_sets(), 3); // 3 vertices
99
100        // Set 0 (vertex 0): should contain edge 0
101        assert_eq!(sc_problem.get_set(0), Some(&vec![0]));
102        // Set 1 (vertex 1): should contain edges 0 and 1
103        assert_eq!(sc_problem.get_set(1), Some(&vec![0, 1]));
104        // Set 2 (vertex 2): should contain edge 1
105        assert_eq!(sc_problem.get_set(2), Some(&vec![1]));
106    }
107
108    #[test]
109    fn test_vc_to_sc_triangle() {
110        // Triangle graph: 3 vertices, 3 edges
111        // Edge indices: (0,1)->0, (1,2)->1, (0,2)->2
112        let vc_problem = VertexCovering::<i32>::new(3, vec![(0, 1), (1, 2), (0, 2)]);
113        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
114        let sc_problem = reduction.target_problem();
115
116        assert_eq!(sc_problem.universe_size(), 3);
117        assert_eq!(sc_problem.num_sets(), 3);
118
119        // Verify each vertex covers exactly 2 edges
120        for i in 0..3 {
121            let set = sc_problem.get_set(i).unwrap();
122            assert_eq!(set.len(), 2);
123        }
124    }
125
126    #[test]
127    fn test_vc_to_sc_solution_extraction() {
128        let vc_problem = VertexCovering::<i32>::new(3, vec![(0, 1), (1, 2)]);
129        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
130        let sc_problem = reduction.target_problem();
131
132        // Solve the SetCovering problem
133        let solver = BruteForce::new();
134        let sc_solutions = solver.find_best(sc_problem);
135
136        // Extract solutions back to VertexCovering
137        let vc_solutions: Vec<_> = sc_solutions
138            .iter()
139            .map(|s| reduction.extract_solution(s))
140            .collect();
141
142        // Verify extracted solutions are valid vertex covers
143        for sol in &vc_solutions {
144            assert!(vc_problem.solution_size(sol).is_valid);
145        }
146
147        // The minimum should be selecting just vertex 1 (covers both edges)
148        let min_size: usize = vc_solutions[0].iter().sum();
149        assert_eq!(min_size, 1);
150    }
151
152    #[test]
153    fn test_vc_to_sc_optimality_preservation() {
154        // Test that optimal solutions are preserved through reduction
155        let vc_problem = VertexCovering::<i32>::new(4, vec![(0, 1), (1, 2), (2, 3)]);
156        let solver = BruteForce::new();
157
158        // Solve VC directly
159        let direct_solutions = solver.find_best(&vc_problem);
160        let direct_size = direct_solutions[0].iter().sum::<usize>();
161
162        // Solve via reduction
163        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
164        let sc_solutions = solver.find_best(reduction.target_problem());
165        let reduced_solutions: Vec<_> = sc_solutions
166            .iter()
167            .map(|s| reduction.extract_solution(s))
168            .collect();
169        let reduced_size = reduced_solutions[0].iter().sum::<usize>();
170
171        // Optimal sizes should match
172        assert_eq!(direct_size, reduced_size);
173    }
174
175    #[test]
176    fn test_vc_to_sc_weighted() {
177        // Weighted problem: weights should be preserved
178        let vc_problem = VertexCovering::with_weights(3, vec![(0, 1), (1, 2)], vec![10, 1, 10]);
179        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
180        let sc_problem = reduction.target_problem();
181
182        // Weights should be preserved
183        assert_eq!(sc_problem.weights(), vec![10, 1, 10]);
184
185        // Solve both ways
186        let solver = BruteForce::new();
187        let vc_solutions = solver.find_best(&vc_problem);
188        let sc_solutions = solver.find_best(sc_problem);
189
190        // Both should select vertex 1 (weight 1)
191        assert_eq!(vc_solutions[0], vec![0, 1, 0]);
192        assert_eq!(sc_solutions[0], vec![0, 1, 0]);
193    }
194
195    #[test]
196    fn test_vc_to_sc_empty_graph() {
197        // Graph with no edges
198        let vc_problem = VertexCovering::<i32>::new(3, vec![]);
199        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
200        let sc_problem = reduction.target_problem();
201
202        assert_eq!(sc_problem.universe_size(), 0);
203        assert_eq!(sc_problem.num_sets(), 3);
204
205        // All sets should be empty
206        for i in 0..3 {
207            assert!(sc_problem.get_set(i).unwrap().is_empty());
208        }
209    }
210
211    #[test]
212    fn test_vc_to_sc_source_target_size() {
213        let vc_problem = VertexCovering::<i32>::new(5, vec![(0, 1), (1, 2), (2, 3), (3, 4)]);
214        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
215
216        let source_size = reduction.source_size();
217        let target_size = reduction.target_size();
218
219        assert_eq!(source_size.get("num_vertices"), Some(5));
220        assert_eq!(source_size.get("num_edges"), Some(4));
221        assert_eq!(target_size.get("universe_size"), Some(4)); // edges become universe
222        assert_eq!(target_size.get("num_sets"), Some(5)); // vertices become sets
223    }
224
225    #[test]
226    fn test_vc_to_sc_star_graph() {
227        // Star graph: center vertex 0 connected to all others
228        // Edges: (0,1), (0,2), (0,3)
229        let vc_problem = VertexCovering::<i32>::new(4, vec![(0, 1), (0, 2), (0, 3)]);
230        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
231        let sc_problem = reduction.target_problem();
232
233        // Vertex 0 should cover all 3 edges
234        assert_eq!(sc_problem.get_set(0), Some(&vec![0, 1, 2]));
235        // Other vertices cover only 1 edge each
236        assert_eq!(sc_problem.get_set(1), Some(&vec![0]));
237        assert_eq!(sc_problem.get_set(2), Some(&vec![1]));
238        assert_eq!(sc_problem.get_set(3), Some(&vec![2]));
239
240        // Minimum cover should be just vertex 0
241        let solver = BruteForce::new();
242        let solutions = solver.find_best(&vc_problem);
243        assert_eq!(solutions[0], vec![1, 0, 0, 0]);
244    }
245
246    #[test]
247    fn test_vc_to_sc_all_solutions_valid() {
248        // Ensure all solutions extracted from SC are valid VC solutions
249        let vc_problem = VertexCovering::<i32>::new(4, vec![(0, 1), (1, 2), (0, 2), (2, 3)]);
250        let reduction = ReduceTo::<SetCovering<i32>>::reduce_to(&vc_problem);
251        let sc_problem = reduction.target_problem();
252
253        let solver = BruteForce::new();
254        let sc_solutions = solver.find_best(sc_problem);
255
256        for sc_sol in &sc_solutions {
257            let vc_sol = reduction.extract_solution(sc_sol);
258            let sol_size = vc_problem.solution_size(&vc_sol);
259            assert!(
260                sol_size.is_valid,
261                "Extracted solution {:?} should be valid",
262                vc_sol
263            );
264        }
265    }
266}
267
268// Register reduction with inventory for auto-discovery
269use crate::poly;
270use crate::rules::registry::{ReductionEntry, ReductionOverhead};
271
272inventory::submit! {
273    ReductionEntry {
274        source_name: "VertexCovering",
275        target_name: "SetCovering",
276        source_graph: "SimpleGraph",
277        target_graph: "SetSystem",
278        overhead_fn: || ReductionOverhead::new(vec![
279            ("num_sets", poly!(num_vertices)),
280            ("num_elements", poly!(num_edges)),
281        ]),
282    }
283}
problemreductions/rules/vertexcovering_setcovering.rs

problemreductions/rules/
vertexcovering_setcovering.rs
