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, i32>;
20    type Target = MinimumWeightAndOrGraph;
21
22    fn target_problem(&self) -> &Self::Target {
23        &self.target
24    }
25
26    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
27        (0..self.num_source_vertices)
28            .map(|j| usize::from(target_solution.get(self.sink_arc_start + j) == Some(&1)))
29            .collect()
30    }
31}
32
33#[reduction(
34    overhead = {
35        num_vertices = "1 + num_edges + 2 * num_vertices",
36        num_arcs = "3 * num_edges + num_vertices",
37    }
38)]
39impl ReduceTo<MinimumWeightAndOrGraph> for MinimumVertexCover<SimpleGraph, i32> {
40    type Result = ReductionVCToAndOrGraph;
41
42    fn reduce_to(&self) -> Self::Result {
43        let n = self.graph().num_vertices();
44        let edges = self.graph().edges();
45        let m = edges.len();
46
47        let num_target_vertices = 1 + m + (2 * n);
48        let mut gate_types = vec![None; num_target_vertices];
49        gate_types[0] = Some(true);
50        for gate in gate_types.iter_mut().skip(1).take(m + n) {
51            *gate = Some(false);
52        }
53
54        let edge_vertex = |i: usize| 1 + i;
55        let cover_vertex = |j: usize| 1 + m + j;
56        let sink_vertex = |j: usize| 1 + m + n + j;
57
58        let mut arcs = Vec::with_capacity((3 * m) + n);
59        let mut arc_weights = Vec::with_capacity((3 * m) + n);
60
61        for i in 0..m {
62            arcs.push((0, edge_vertex(i)));
63            arc_weights.push(1);
64        }
65
66        for (i, &(u, v)) in edges.iter().enumerate() {
67            arcs.push((edge_vertex(i), cover_vertex(u)));
68            arc_weights.push(1);
69            arcs.push((edge_vertex(i), cover_vertex(v)));
70            arc_weights.push(1);
71        }
72
73        let sink_arc_start = arcs.len();
74        for (j, &weight) in self.weights().iter().enumerate() {
75            arcs.push((cover_vertex(j), sink_vertex(j)));
76            arc_weights.push(weight);
77        }
78
79        let target =
80            MinimumWeightAndOrGraph::new(num_target_vertices, arcs, 0, gate_types, arc_weights);
81
82        ReductionVCToAndOrGraph {
83            target,
84            sink_arc_start,
85            num_source_vertices: n,
86        }
87    }
88}
89
90#[cfg(any(test, feature = "example-db"))]
91fn issue_example_source() -> MinimumVertexCover<SimpleGraph, i32> {
92    MinimumVertexCover::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![1i32; 3])
93}
94
95#[cfg(feature = "example-db")]
96pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
97    use crate::export::SolutionPair;
98
99    vec![crate::example_db::specs::RuleExampleSpec {
100        id: "minimumvertexcover_to_minimumweightandorgraph",
101        build: || {
102            crate::example_db::specs::rule_example_with_witness::<_, MinimumWeightAndOrGraph>(
103                issue_example_source(),
104                SolutionPair {
105                    source_config: vec![0, 1, 0],
106                    target_config: vec![1, 1, 0, 1, 1, 0, 0, 1, 0],
107                },
108            )
109        },
110    }]
111}
112
113#[cfg(test)]
114#[path = "../unit_tests/rules/minimumvertexcover_minimumweightandorgraph.rs"]
115mod tests;
problemreductions/rules/minimumvertexcover_minimumweightandorgraph.rs

problemreductions/rules/
minimumvertexcover_minimumweightandorgraph.rs
