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    forced_cover: Vec<bool>,
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            self.forced_cover
34                .iter()
35                .enumerate()
36                .map(|(j, &forced)| forced || target_solution[self.sink_arc_start + j])
37                .collect()
38        })
39    }
40}
41
42#[reduction(
43    transform = upper_bound {
44        num_vertices = "1 + num_edges + 2 * num_vertices",
45        num_arcs = "3 * num_edges + num_vertices",
46    }
47)]
48impl ReduceTo<MinimumWeightAndOrGraph> for MinimumVertexCover<SimpleGraph, i64> {
49    type Result = ReductionVCToAndOrGraph;
50
51    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
52        let n = self.graph().num_vertices();
53        // Every optimum includes negative-weight vertices, even isolated ones.
54        let forced_cover: Vec<_> = self.weights().iter().map(|&w| w < 0).collect();
55        let edges: Vec<_> = self
56            .graph()
57            .edges()
58            .into_iter()
59            .filter(|&(u, v)| !forced_cover[u] && !forced_cover[v])
60            .collect();
61        let m = edges.len();
62
63        let num_target_vertices = 1 + m + (2 * n);
64        let mut gate_types = vec![None; num_target_vertices];
65        gate_types[0] = Some(true);
66        for gate in gate_types.iter_mut().skip(1).take(m + n) {
67            *gate = Some(false);
68        }
69
70        let edge_vertex = |i: usize| 1 + i;
71        let cover_vertex = |j: usize| 1 + m + j;
72        let sink_vertex = |j: usize| 1 + m + n + j;
73
74        let mut arcs = Vec::with_capacity((3 * m) + n);
75        let mut arc_weights = Vec::with_capacity((3 * m) + n);
76
77        for i in 0..m {
78            arcs.push((0, edge_vertex(i)));
79            arc_weights.push(1);
80        }
81
82        for (i, &(u, v)) in edges.iter().enumerate() {
83            arcs.push((edge_vertex(i), cover_vertex(u)));
84            arc_weights.push(1);
85            arcs.push((edge_vertex(i), cover_vertex(v)));
86            arc_weights.push(1);
87        }
88
89        let sink_arc_start = arcs.len();
90        for (j, &weight) in self.weights().iter().enumerate() {
91            arcs.push((cover_vertex(j), sink_vertex(j)));
92            arc_weights.push(weight.max(0));
93        }
94
95        let target =
96            MinimumWeightAndOrGraph::new(num_target_vertices, arcs, 0, gate_types, arc_weights);
97
98        Ok(ReductionVCToAndOrGraph {
99            target,
100            sink_arc_start,
101            forced_cover,
102        })
103    }
104}
105
106#[cfg(any(test, feature = "example-db"))]
107fn issue_example_source() -> MinimumVertexCover<SimpleGraph, i64> {
108    MinimumVertexCover::new(SimpleGraph::new(3, vec![(0, 1), (1, 2)]), vec![1i64; 3])
109}
110
111#[cfg(feature = "example-db")]
112pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
113    use crate::export::SolutionPair;
114
115    vec![crate::example_db::specs::RuleExampleSpec {
116        id: "minimumvertexcover_to_minimumweightandorgraph",
117        build: || {
118            crate::example_db::specs::rule_example_with_witness::<_, MinimumWeightAndOrGraph>(
119                issue_example_source(),
120                SolutionPair {
121                    source_config: serde_json::json!(vec![false, true, false]),
122                    target_config: serde_json::json!(vec![
123                        true, true, false, true, true, false, false, true, false
124                    ]),
125                },
126            )
127        },
128    }]
129}
130
131#[cfg(test)]
132#[path = "../unit_tests/rules/minimumvertexcover_minimumweightandorgraph.rs"]
133mod tests;
problemreductions/rules/minimumvertexcover_minimumweightandorgraph.rs

problemreductions/rules/
minimumvertexcover_minimumweightandorgraph.rs
