problemreductions/rules/
minimumvertexcover_longestcommonsubsequence.rs

1//! Reduction from MinimumVertexCover (unit-weight) to LongestCommonSubsequence.
2
3use crate::models::graph::MinimumVertexCover;
4use crate::models::misc::LongestCommonSubsequence;
5use crate::reduction;
6use crate::rules::traits::{ReduceTo, ReductionResult};
7use crate::topology::{Graph, SimpleGraph};
8use crate::types::One;
9
10#[derive(Debug, Clone)]
11pub struct ReductionVCToLCS {
12    target: LongestCommonSubsequence,
13    num_vertices: usize,
14}
15
16impl ReductionResult for ReductionVCToLCS {
17    type Source = MinimumVertexCover<SimpleGraph, One>;
18    type Target = LongestCommonSubsequence;
19
20    fn target_problem(&self) -> &Self::Target {
21        &self.target
22    }
23
24    fn extract_solution(
25        &self,
26        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
27    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
28        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
29
30        Ok({
31            let mut cover = vec![true; self.num_vertices];
32            for &symbol in target_solution {
33                let Some(symbol) = symbol else { break };
34                cover[symbol] = false;
35            }
36            cover
37        })
38    }
39}
40
41#[reduction(
42    transform = exact {
43        alphabet_size = "num_vertices",
44        num_strings = "num_edges + 1",
45        max_length = "num_vertices",
46        total_length = "num_vertices + 2 * num_edges * num_vertices - 2 * num_edges",
47    },
48    unavailable = {
49        cross_frequency_product = "the exact target parameter is not represented by this reduction's symbolic transform",
50        num_transitions = "the exact target parameter is not represented by this reduction's symbolic transform",
51        sum_triangular_lengths = "the exact target parameter is not represented by this reduction's symbolic transform",
52    }
53)]
54impl ReduceTo<LongestCommonSubsequence> for MinimumVertexCover<SimpleGraph, One> {
55    type Result = ReductionVCToLCS;
56
57    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
58        let num_vertices = self.graph().num_vertices();
59        let mut strings = Vec::with_capacity(self.graph().num_edges() + 1);
60        strings.push((0..num_vertices).collect());
61
62        for (left, right) in self.graph().edges() {
63            // The backward direction relies on each edge string forcing the
64            // larger endpoint to appear before the smaller one.
65            let (u, v) = if left < right {
66                (left, right)
67            } else {
68                (right, left)
69            };
70            let mut edge_string = string_without_vertex(num_vertices, u);
71            edge_string.extend(string_without_vertex(num_vertices, v));
72            strings.push(edge_string);
73        }
74
75        let target = LongestCommonSubsequence::new(num_vertices, strings);
76        Ok(ReductionVCToLCS {
77            target,
78            num_vertices,
79        })
80    }
81}
82
83fn string_without_vertex(num_vertices: usize, omitted: usize) -> Vec<usize> {
84    (0..num_vertices)
85        .filter(|&vertex| vertex != omitted)
86        .collect()
87}
88
89#[cfg(feature = "example-db")]
90pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
91    use crate::export::SolutionPair;
92
93    vec![crate::example_db::specs::RuleExampleSpec {
94        id: "minimumvertexcover_to_longestcommonsubsequence",
95        build: || {
96            let source = MinimumVertexCover::new(
97                SimpleGraph::new(4, vec![(0, 1), (1, 2), (2, 3)]),
98                vec![One; 4],
99            );
100            crate::example_db::specs::rule_example_with_witness::<_, LongestCommonSubsequence>(
101                source,
102                SolutionPair {
103                    source_config: serde_json::json!(vec![false, true, true, false]),
104                    target_config: serde_json::json!(vec![Some(0), Some(3), None, None]),
105                },
106            )
107        },
108    }]
109}
110
111#[cfg(test)]
112#[path = "../unit_tests/rules/minimumvertexcover_longestcommonsubsequence.rs"]
113mod tests;
problemreductions/rules/minimumvertexcover_longestcommonsubsequence.rs

problemreductions/rules/
minimumvertexcover_longestcommonsubsequence.rs
