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    source_universe_size: usize,
18}
19
20impl ReductionResult for ReductionXC3SToMinimumFaultDetectionTestSet {
21    type Source = ExactCoverBy3Sets;
22    type Target = MinimumFaultDetectionTestSet;
23
24    fn target_problem(&self) -> &MinimumFaultDetectionTestSet {
25        &self.target
26    }
27
28    fn extract_solution(
29        &self,
30        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
31    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
32        crate::rules::traits::validate_target_witness(
33            self.target_problem(),
34            target_solution,
35            |value| crate::rules::AggregateReductionResult::extract_value(self, value).0,
36            "target witness does not certify a YES answer for the source",
37        )?;
38
39        if self.source_universe_size == 0 {
40            return Ok(vec![]);
41        }
42        Ok(target_solution.iter().map(|row| row[0]).collect())
43    }
44}
45
46#[crate::aggregate_reduction]
47impl crate::rules::AggregateReductionResult for ReductionXC3SToMinimumFaultDetectionTestSet {
48    type Source = ExactCoverBy3Sets;
49    type Target = MinimumFaultDetectionTestSet;
50
51    fn target_problem(&self) -> &Self::Target {
52        &self.target
53    }
54
55    fn extract_value(&self, value: crate::types::Min<i64>) -> crate::types::Or {
56        crate::types::Or(
57            value
58                .0
59                .is_some_and(|count| i128::from(count) == self.source_universe_size as i128 / 3),
60        )
61    }
62}
63
64#[reduction(
65    transform = upper_bound {
66        num_vertices = "num_subsets + universe_size + 2",
67        num_arcs = "3 * num_subsets + universe_size + 1",
68        num_inputs = "num_subsets + 1",
69        num_outputs = "1",
70    })]
71impl ReduceTo<MinimumFaultDetectionTestSet> for ExactCoverBy3Sets {
72    type Result = ReductionXC3SToMinimumFaultDetectionTestSet;
73
74    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
75        let num_inputs = self.num_subsets();
76        if num_inputs == 0 {
77            // The target requires an input and an output. With no internal
78            // vertices its optimum is zero, matching q only for an empty universe.
79            return Ok(ReductionXC3SToMinimumFaultDetectionTestSet {
80                target: MinimumFaultDetectionTestSet::new(2, vec![(0, 1)], vec![0], vec![1]),
81                source_universe_size: self.universe_size(),
82            });
83        }
84        let element_offset = num_inputs;
85        let output = element_offset + self.universe_size();
86
87        let mut arcs = Vec::with_capacity(3 * self.num_subsets() + self.universe_size());
88        for (set_idx, subset) in self.subsets().iter().enumerate() {
89            for &element in subset {
90                arcs.push((set_idx, element_offset + element));
91            }
92        }
93        for element in 0..self.universe_size() {
94            arcs.push((element_offset + element, output));
95        }
96
97        Ok(ReductionXC3SToMinimumFaultDetectionTestSet {
98            source_universe_size: self.universe_size(),
99            target: MinimumFaultDetectionTestSet::new(
100                output + 1,
101                arcs,
102                (0..num_inputs).collect(),
103                vec![output],
104            ),
105        })
106    }
107}
108
109#[cfg(feature = "example-db")]
110pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
111    use crate::export::SolutionPair;
112
113    vec![crate::example_db::specs::RuleExampleSpec {
114        id: "exactcoverby3sets_to_minimumfaultdetectiontestset",
115        build: || {
116            let source = ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]]);
117            crate::example_db::specs::rule_example_with_witness::<_, MinimumFaultDetectionTestSet>(
118                source,
119                SolutionPair {
120                    source_config: serde_json::json!(vec![true, true, false]),
121                    target_config: serde_json::json!(vec![vec![true], vec![true], vec![false]]),
122                },
123            )
124        },
125    }]
126}
127
128#[cfg(test)]
129#[path = "../unit_tests/rules/exactcoverby3sets_minimumfaultdetectiontestset.rs"]
130mod tests;
problemreductions/rules/exactcoverby3sets_minimumfaultdetectiontestset.rs

problemreductions/rules/
exactcoverby3sets_minimumfaultdetectiontestset.rs
