problemreductions/rules/
minimumfaultdetectiontestset_ilp.rs

1//! Reduction from MinimumFaultDetectionTestSet to ILP.
2//!
3//! Each input-output pair becomes a binary decision variable. For every
4//! internal vertex, the ILP requires at least one selected pair whose coverage
5//! set contains that vertex. Minimizing the sum of the pair variables therefore
6//! recovers the minimum-size covering test set.
7
8use crate::models::algebraic::{LinearConstraint, ObjectiveSense, ILP};
9use crate::models::misc::MinimumFaultDetectionTestSet;
10use crate::reduction;
11use crate::rules::traits::{ReduceTo, ReductionResult};
12use std::collections::VecDeque;
13
14/// Result of reducing MinimumFaultDetectionTestSet to ILP<bool>.
15#[derive(Debug, Clone)]
16pub struct ReductionMFDTSToILP {
17    target: ILP<bool>,
18}
19
20impl ReductionResult for ReductionMFDTSToILP {
21    type Source = MinimumFaultDetectionTestSet;
22    type Target = ILP<bool>;
23
24    fn target_problem(&self) -> &ILP<bool> {
25        &self.target
26    }
27
28    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
29        target_solution.to_vec()
30    }
31}
32
33#[reduction(overhead = {
34    num_vars = "num_inputs * num_outputs",
35    num_constraints = "num_vertices - num_inputs - num_outputs",
36})]
37impl ReduceTo<ILP<bool>> for MinimumFaultDetectionTestSet {
38    type Result = ReductionMFDTSToILP;
39
40    fn reduce_to(&self) -> Self::Result {
41        fn reachable(adj: &[Vec<usize>], start: usize) -> Vec<bool> {
42            let mut seen = vec![false; adj.len()];
43            let mut queue = VecDeque::new();
44            seen[start] = true;
45            queue.push_back(start);
46
47            while let Some(vertex) = queue.pop_front() {
48                for &next in &adj[vertex] {
49                    if !seen[next] {
50                        seen[next] = true;
51                        queue.push_back(next);
52                    }
53                }
54            }
55
56            seen
57        }
58
59        let mut adj = vec![Vec::new(); self.num_vertices()];
60        let mut rev_adj = vec![Vec::new(); self.num_vertices()];
61        for &(tail, head) in self.arcs() {
62            adj[tail].push(head);
63            rev_adj[head].push(tail);
64        }
65
66        let input_reachability: Vec<Vec<bool>> = self
67            .inputs()
68            .iter()
69            .map(|&input| reachable(&adj, input))
70            .collect();
71        let output_reachability: Vec<Vec<bool>> = self
72            .outputs()
73            .iter()
74            .map(|&output| reachable(&rev_adj, output))
75            .collect();
76
77        let mut boundary = vec![false; self.num_vertices()];
78        for &input in self.inputs() {
79            boundary[input] = true;
80        }
81        for &output in self.outputs() {
82            boundary[output] = true;
83        }
84
85        let num_pairs = self.num_inputs() * self.num_outputs();
86        let internal_vertices: Vec<usize> = (0..self.num_vertices())
87            .filter(|&vertex| !boundary[vertex])
88            .collect();
89
90        let constraints: Vec<LinearConstraint> = internal_vertices
91            .into_iter()
92            .map(|vertex| {
93                let mut terms = Vec::new();
94                for (input_idx, input_cov) in input_reachability.iter().enumerate() {
95                    for (output_idx, output_cov) in output_reachability.iter().enumerate() {
96                        if input_cov[vertex] && output_cov[vertex] {
97                            let pair_idx = input_idx * self.num_outputs() + output_idx;
98                            terms.push((pair_idx, 1.0));
99                        }
100                    }
101                }
102                LinearConstraint::ge(terms, 1.0)
103            })
104            .collect();
105
106        let objective = (0..num_pairs).map(|pair_idx| (pair_idx, 1.0)).collect();
107
108        ReductionMFDTSToILP {
109            target: ILP::new(num_pairs, constraints, objective, ObjectiveSense::Minimize),
110        }
111    }
112}
113
114#[cfg(feature = "example-db")]
115pub(crate) fn canonical_rule_example_specs() -> Vec<crate::example_db::specs::RuleExampleSpec> {
116    vec![crate::example_db::specs::RuleExampleSpec {
117        id: "minimumfaultdetectiontestset_to_ilp",
118        build: || {
119            let source = MinimumFaultDetectionTestSet::new(
120                7,
121                vec![
122                    (0, 2),
123                    (0, 3),
124                    (1, 3),
125                    (1, 4),
126                    (2, 5),
127                    (3, 5),
128                    (3, 6),
129                    (4, 6),
130                ],
131                vec![0, 1],
132                vec![5, 6],
133            );
134            crate::example_db::specs::rule_example_via_ilp::<_, bool>(source)
135        },
136    }]
137}
138
139#[cfg(test)]
140#[path = "../unit_tests/rules/minimumfaultdetectiontestset_ilp.rs"]
141mod tests;
problemreductions/rules/minimumfaultdetectiontestset_ilp.rs

problemreductions/rules/
minimumfaultdetectiontestset_ilp.rs
