problemreductions/rules/
decisionminimumdominatingset_minimumsummulticenter.rs

1//! Reduction from Decision Minimum Dominating Set to Minimum Sum Multicenter.
2//!
3//! On unit-weight, unit-length graphs, choosing `K` centers with total distance
4//! `n - K` is exactly choosing a dominating set of size at most `K`.
5
6use crate::models::decision::Decision;
7use crate::models::graph::{MinimumDominatingSet, MinimumSumMulticenter};
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::topology::{Graph, SimpleGraph};
11use crate::types::One;
12
13/// Result of reducing DecisionMinimumDominatingSet to MinimumSumMulticenter.
14#[derive(Debug, Clone)]
15pub struct ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter {
16    target: MinimumSumMulticenter<SimpleGraph, i32>,
17}
18
19impl ReductionResult for ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter {
20    type Source = Decision<MinimumDominatingSet<SimpleGraph, One>>;
21    type Target = MinimumSumMulticenter<SimpleGraph, i32>;
22
23    fn target_problem(&self) -> &Self::Target {
24        &self.target
25    }
26
27    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
28        target_solution.to_vec()
29    }
30}
31
32#[reduction(overhead = { num_vertices = "num_vertices", num_edges = "num_edges" })]
33impl ReduceTo<MinimumSumMulticenter<SimpleGraph, i32>>
34    for Decision<MinimumDominatingSet<SimpleGraph, One>>
35{
36    type Result = ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter;
37
38    fn reduce_to(&self) -> Self::Result {
39        let source_graph = self.inner().graph();
40        let target = MinimumSumMulticenter::new(
41            SimpleGraph::new(source_graph.num_vertices(), source_graph.edges()),
42            vec![1i32; source_graph.num_vertices()],
43            vec![1i32; source_graph.num_edges()],
44            self.k(),
45        );
46        ReductionDecisionMinimumDominatingSetToMinimumSumMulticenter { target }
47    }
48}
49
50#[cfg(feature = "example-db")]
51pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
52    use crate::export::SolutionPair;
53
54    vec![crate::example_db::specs::RuleExampleSpec {
55        id: "decisionminimumdominatingset_to_minimumsummulticenter",
56        build: || {
57            crate::example_db::specs::rule_example_with_witness::<
58                _,
59                MinimumSumMulticenter<SimpleGraph, i32>,
60            >(
61                Decision::new(
62                    MinimumDominatingSet::new(
63                        SimpleGraph::new(
64                            6,
65                            vec![(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (3, 5), (4, 5)],
66                        ),
67                        vec![One; 6],
68                    ),
69                    2,
70                ),
71                SolutionPair {
72                    source_config: vec![1, 0, 0, 1, 0, 0],
73                    target_config: vec![1, 0, 0, 1, 0, 0],
74                },
75            )
76        },
77    }]
78}
79
80#[cfg(test)]
81#[path = "../unit_tests/rules/decisionminimumdominatingset_minimumsummulticenter.rs"]
82mod tests;
problemreductions/rules/decisionminimumdominatingset_minimumsummulticenter.rs

problemreductions/rules/
decisionminimumdominatingset_minimumsummulticenter.rs
