problemreductions/rules/
minimumvertexcover_minimumweightandorgraph.rs

1//! Reduction from MinimumVertexCover to MinimumWeightAndOrGraph.
2
3use crate::models::graph::MinimumVertexCover;
4use crate::models::misc::MinimumWeightAndOrGraph;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7use crate::topology::Graph;
8use crate::topology::SimpleGraph;
9
10/// Result of reducing MinimumVertexCover to MinimumWeightAndOrGraph.
11#[derive(Debug, Clone)]
12pub struct ReductionVCToAndOrGraph {
13    target: MinimumWeightAndOrGraph,
14    sink_arc_start: usize,
15    num_source_vertices: usize,
16}
17
18impl ReductionResult for ReductionVCToAndOrGraph {
19    type Source = MinimumVertexCover<SimpleGraph, i64>;
20    type Target = MinimumWeightAndOrGraph;
21
22    fn target_problem(&self) -> &Self::Target {
23        &self.target
24    }
25
26    fn extract_solution(
27        &self,
28        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
29    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
30        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
31
32        Ok({
33            (0..self.num_source_vertices)
34                .map(|j| target_solution[self.sink_arc_start + j])
35                .collect()
36        })
37    }
38}
39
40#[reduction(
41    transform = exact {
42        num_vertices = "1 + num_edges + 2 * num_vertices",
43        num_arcs = "3 * num_edges + num_vertices",
44    }
45)]
46impl ReduceTo<MinimumWeightAndOrGraph> for MinimumVertexCover<SimpleGraph, i64> {
47    type Result = ReductionVCToAndOrGraph;
48
49    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
50        let n = self.graph().num_vertices();
51        let edges = self.graph().edges();
52        let m = edges.len();
53
54        let num_target_vertices = 1 + m + (2 * n);
55        let mut gate_types = vec![None; num_target_vertices];
56        gate_types[0] = Some(true);
57        for gate in gate_types.iter_mut().skip(1).take(m + n) {
58            *gate = Some(false);
59        }
60
61        let edge_vertex = |i: usize| 1 + i;
62        let cover_vertex = |j: usize| 1 + m + j;
63        let sink_vertex = |j: usize| 1 + m + n + j;
64
65        let mut arcs = Vec::with_capacity((3 * m) + n);
66        let mut arc_weights = Vec::with_capacity((3 * m) + n);
67
68        for i in 0..m {
69            arcs.push((0, edge_vertex(i)));
70            arc_weights.push(1);
71        }
72
73        for (i, &(u, v)) in edges.iter().enumerate() {
74            arcs.push((edge_vertex(i), cover_vertex(u)));
75            arc_weights.push(1);
76            arcs.push((edge_vertex(i), cover_vertex(v)));
77            arc_weights.push(1);
78        }
79
80        let sink_arc_start = arcs.len();
81        for (j, &weight) in self.weights().iter().enumerate() {
82            arcs.push((cover_vertex(j), sink_vertex(j)));
83            arc_weights.push(weight);
84        }
85
86        let target =
87            MinimumWeightAndOrGraph::new(num_target_vertices, arcs, 0, gate_types, arc_weights);
88
89        Ok(ReductionVCToAndOrGraph {
90            target,
91            sink_arc_start,
92            num_source_vertices: n,
93        })
94    }
95}
96
97#[cfg(any(test, feature = "example-db"))]
98fn issue_example_source() -> MinimumVertexCover<SimpleGraph, i64> {
99    MinimumVertexCover::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![1i64; 3])
100}
101
102#[cfg(feature = "example-db")]
103pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
104    use crate::export::SolutionPair;
105
106    vec![crate::example_db::specs::RuleExampleSpec {
107        id: "minimumvertexcover_to_minimumweightandorgraph",
108        build: || {
109            crate::example_db::specs::rule_example_with_witness::<_, MinimumWeightAndOrGraph>(
110                issue_example_source(),
111                SolutionPair {
112                    source_config: serde_json::json!(vec![false, true, false]),
113                    target_config: serde_json::json!(vec![
114                        true, true, false, true, true, false, false, true, false
115                    ]),
116                },
117            )
118        },
119    }]
120}
121
122#[cfg(test)]
123#[path = "../unit_tests/rules/minimumvertexcover_minimumweightandorgraph.rs"]
124mod tests;
problemreductions/rules/minimumvertexcover_minimumweightandorgraph.rs

problemreductions/rules/
minimumvertexcover_minimumweightandorgraph.rs
