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(
28        &self,
29        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
30    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
31        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
32
33        Ok(target_solution.iter().map(|row| row[0]).collect())
34    }
35}
36
37#[reduction(
38    transform = exact {
39        num_vertices = "num_subsets + universe_size + 1",
40        num_arcs = "3 * num_subsets + universe_size",
41        num_inputs = "num_subsets",
42        num_outputs = "1",
43    })]
44impl ReduceTo<MinimumFaultDetectionTestSet> for ExactCoverBy3Sets {
45    type Result = ReductionXC3SToMinimumFaultDetectionTestSet;
46
47    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
48        let num_inputs = self.num_subsets();
49        let element_offset = num_inputs;
50        let output = element_offset + self.universe_size();
51
52        let mut arcs = Vec::with_capacity(3 * self.num_subsets() + self.universe_size());
53        for (set_idx, subset) in self.subsets().iter().enumerate() {
54            for &element in subset {
55                arcs.push((set_idx, element_offset + element));
56            }
57        }
58        for element in 0..self.universe_size() {
59            arcs.push((element_offset + element, output));
60        }
61
62        Ok(ReductionXC3SToMinimumFaultDetectionTestSet {
63            target: MinimumFaultDetectionTestSet::new(
64                output + 1,
65                arcs,
66                (0..num_inputs).collect(),
67                vec![output],
68            ),
69        })
70    }
71}
72
73#[cfg(feature = "example-db")]
74pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
75    use crate::export::SolutionPair;
76
77    vec![crate::example_db::specs::RuleExampleSpec {
78        id: "exactcoverby3sets_to_minimumfaultdetectiontestset",
79        build: || {
80            let source = ExactCoverBy3Sets::new(6, vec![[0, 1, 2], [3, 4, 5], [0, 3, 4]]);
81            crate::example_db::specs::rule_example_with_witness::<_, MinimumFaultDetectionTestSet>(
82                source,
83                SolutionPair {
84                    source_config: serde_json::json!(vec![true, true, false]),
85                    target_config: serde_json::json!(vec![vec![true], vec![true], vec![false]]),
86                },
87            )
88        },
89    }]
90}
91
92#[cfg(test)]
93#[path = "../unit_tests/rules/exactcoverby3sets_minimumfaultdetectiontestset.rs"]
94mod tests;
problemreductions/rules/exactcoverby3sets_minimumfaultdetectiontestset.rs

problemreductions/rules/
exactcoverby3sets_minimumfaultdetectiontestset.rs
