problemreductions/rules/
exactcoverby3sets_minimumfaultdetectiontestset.rs

1//! Reduction from ExactCoverBy3Sets to MinimumFaultDetectionTestSet.
2//!
3//! The target DAG has one input per source subset, one internal vertex per
4//! universe element, and a single shared output. Under the target model's
5//! internal-vertex semantics, selecting an input-output pair covers exactly the
6//! three internal vertices corresponding to that subset.
7
8use crate::models::misc::MinimumFaultDetectionTestSet;
9use crate::models::set::ExactCoverBy3Sets;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12
13/// Result of reducing ExactCoverBy3Sets to MinimumFaultDetectionTestSet.
14#[derive(Debug, Clone)]
15pub struct ReductionXC3SToMinimumFaultDetectionTestSet {
16    target: MinimumFaultDetectionTestSet,
17}
18
19impl ReductionResult for ReductionXC3SToMinimumFaultDetectionTestSet {
20    type Source = ExactCoverBy3Sets;
21    type Target = MinimumFaultDetectionTestSet;
22
23    fn target_problem(&self) -> &MinimumFaultDetectionTestSet {
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 = {
33    num_vertices = "num_subsets + universe_size + 1",
34    num_arcs = "3 * num_subsets + universe_size",
35    num_inputs = "num_subsets",
36    num_outputs = "1",
37})]
38impl ReduceTo<MinimumFaultDetectionTestSet> for ExactCoverBy3Sets {
39    type Result = ReductionXC3SToMinimumFaultDetectionTestSet;
40
41    fn reduce_to(&self) -> Self::Result {
42        let num_inputs = self.num_subsets();
43        let element_offset = num_inputs;
44        let output = element_offset + self.universe_size();
45
46        let mut arcs = Vec::with_capacity(3 * self.num_subsets() + self.universe_size());
47        for (set_idx, subset) in self.subsets().iter().enumerate() {
48            for &element in subset {
49                arcs.push((set_idx, element_offset + element));
50            }
51        }
52        for element in 0..self.universe_size() {
53            arcs.push((element_offset + element, output));
54        }
55
56        ReductionXC3SToMinimumFaultDetectionTestSet {
57            target: MinimumFaultDetectionTestSet::new(
58                output + 1,
59                arcs,
60                (0..num_inputs).collect(),
61                vec![output],
62            ),
63        }
64    }
65}
66
67#[cfg(feature = "example-db")]
68pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
69    use crate::export::SolutionPair;
70
71    vec![crate::example_db::specs::RuleExampleSpec {
72        id: "exactcoverby3sets_to_minimumfaultdetectiontestset",
73        build: || {
74            let source = ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]]);
75            crate::example_db::specs::rule_example_with_witness::<_, MinimumFaultDetectionTestSet>(
76                source,
77                SolutionPair {
78                    source_config: vec![1, 1, 0],
79                    target_config: vec![1, 1, 0],
80                },
81            )
82        },
83    }]
84}
85
86#[cfg(test)]
87#[path = "../unit_tests/rules/exactcoverby3sets_minimumfaultdetectiontestset.rs"]
88mod tests;
problemreductions/rules/exactcoverby3sets_minimumfaultdetectiontestset.rs

problemreductions/rules/
exactcoverby3sets_minimumfaultdetectiontestset.rs
