problemreductions/models/misc/
minimum_fault_detection_test_set.rs

1//! Minimum Fault Detection Test Set problem implementation.
2//!
3//! Given a directed acyclic graph with designated input and output vertices,
4//! find the minimum set of input-output pairs whose coverage sets cover all
5//! internal vertices.
6
7use crate::registry::{FieldInfo, ProblemSchemaEntry};
8use crate::traits::Problem;
9use crate::types::Min;
10use serde::{Deserialize, Deserializer, Serialize};
11use std::collections::{HashSet, VecDeque};
12
13inventory::submit! {
14    ProblemSchemaEntry {
15        name: "MinimumFaultDetectionTestSet",
16        display_name: "Minimum Fault Detection Test Set",
17        aliases: &[],
18        dimensions: &[],
19        category: crate::registry::ProblemCategory::Misc,
20        module_path: module_path!(),
21        description: "Find minimum set of input-output paths covering all internal DAG vertices",
22        fields: &[
23            FieldInfo { name: "num_vertices", type_name: "usize", description: "Number of vertices in the DAG" },
24            FieldInfo { name: "arcs", type_name: "Vec<(usize, usize)>", description: "Directed arcs (u, v)" },
25            FieldInfo { name: "inputs", type_name: "Vec<usize>", description: "Input vertex indices" },
26            FieldInfo { name: "outputs", type_name: "Vec<usize>", description: "Output vertex indices" },
27        ],
28    }
29}
30
31/// The Minimum Fault Detection Test Set problem.
32///
33/// Given a directed acyclic graph G = (V, A) with designated input vertices
34/// I ⊆ V and output vertices O ⊆ V, find the minimum number of input-output
35/// pairs (i, o) ∈ I × O such that the union of their coverage sets covers
36/// every internal vertex V \ (I ∪ O).
37///
38/// For a pair (i, o), the coverage set is the set of vertices reachable from i
39/// that can also reach o (i.e., vertices on some i-to-o path). Inputs and
40/// outputs themselves are not required to be covered.
41///
42/// The configuration space is binary over all |I| × |O| pairs.
43///
44/// # Example
45///
46/// ```
47/// use problemreductions::models::misc::MinimumFaultDetectionTestSet;
48/// use problemreductions::{Problem, BruteForce};
49///
50/// let problem = MinimumFaultDetectionTestSet::new(
51///     7,
52///     vec![(0,2),(0,3),(1,3),(1,4),(2,5),(3,5),(3,6),(4,6)],
53///     vec![0, 1],
54///     vec![5, 6],
55/// );
56/// let solver = BruteForce::new();
57/// let solution = solver.solve(&problem).unwrap().unwrap();
58/// assert_eq!(problem.evaluate(&solution).unwrap(), problemreductions::types::Min(Some(2)));
59/// ```
60#[derive(Debug, Clone, Serialize)]
61pub struct MinimumFaultDetectionTestSet {
62    /// Number of vertices.
63    num_vertices: usize,
64    /// Directed arcs (u, v).
65    arcs: Vec<(usize, usize)>,
66    /// Input vertex indices.
67    inputs: Vec<usize>,
68    /// Output vertex indices.
69    outputs: Vec<usize>,
70    /// Precomputed coverage sets for each (input_idx, output_idx) pair.
71    /// Indexed as coverage[i_idx * num_outputs + o_idx].
72    #[serde(skip)]
73    coverage: Vec<HashSet<usize>>,
74}
75
76#[derive(Deserialize)]
77struct MinimumFaultDetectionTestSetData {
78    num_vertices: usize,
79    arcs: Vec<(usize, usize)>,
80    inputs: Vec<usize>,
81    outputs: Vec<usize>,
82}
83
84impl<'de> Deserialize<'de> for MinimumFaultDetectionTestSet {
85    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
86    where
87        D: Deserializer<'de>,
88    {
89        let data = MinimumFaultDetectionTestSetData::deserialize(deserializer)?;
90        let coverage =
91            Self::build_coverage(data.num_vertices, &data.arcs, &data.inputs, &data.outputs);
92        Ok(Self {
93            num_vertices: data.num_vertices,
94            arcs: data.arcs,
95            inputs: data.inputs,
96            outputs: data.outputs,
97            coverage,
98        })
99    }
100}
101
102impl MinimumFaultDetectionTestSet {
103    /// Create a new Minimum Fault Detection Test Set instance.
104    ///
105    /// # Panics
106    ///
107    /// Panics if any arc index is out of bounds, if any input or output index
108    /// is out of bounds, or if inputs or outputs are empty.
109    pub fn new(
110        num_vertices: usize,
111        arcs: Vec<(usize, usize)>,
112        inputs: Vec<usize>,
113        outputs: Vec<usize>,
114    ) -> Self {
115        assert!(!inputs.is_empty(), "Inputs must not be empty");
116        assert!(!outputs.is_empty(), "Outputs must not be empty");
117        for (i, &(u, v)) in arcs.iter().enumerate() {
118            assert!(
119                u < num_vertices && v < num_vertices,
120                "Arc {} ({}, {}) out of bounds for {} vertices",
121                i,
122                u,
123                v,
124                num_vertices
125            );
126        }
127        for &inp in &inputs {
128            assert!(
129                inp < num_vertices,
130                "Input vertex {} out of bounds for {} vertices",
131                inp,
132                num_vertices
133            );
134        }
135        for &out in &outputs {
136            assert!(
137                out < num_vertices,
138                "Output vertex {} out of bounds for {} vertices",
139                out,
140                num_vertices
141            );
142        }
143        let coverage = Self::build_coverage(num_vertices, &arcs, &inputs, &outputs);
144        Self {
145            num_vertices,
146            arcs,
147            inputs,
148            outputs,
149            coverage,
150        }
151    }
152
153    /// Compute forward reachability from a given vertex using BFS on the DAG.
154    fn forward_reachable(num_vertices: usize, adj: &[Vec<usize>], start: usize) -> HashSet<usize> {
155        let mut visited = HashSet::new();
156        let mut queue = VecDeque::new();
157        visited.insert(start);
158        queue.push_back(start);
159        while let Some(v) = queue.pop_front() {
160            if v < adj.len() {
161                for &w in &adj[v] {
162                    if visited.insert(w) {
163                        queue.push_back(w);
164                    }
165                }
166            }
167        }
168        let _ = num_vertices; // used only to clarify signature
169        visited
170    }
171
172    /// Compute backward reachability from a given vertex using BFS on the reverse DAG.
173    fn backward_reachable(
174        num_vertices: usize,
175        rev_adj: &[Vec<usize>],
176        start: usize,
177    ) -> HashSet<usize> {
178        let mut visited = HashSet::new();
179        let mut queue = VecDeque::new();
180        visited.insert(start);
181        queue.push_back(start);
182        while let Some(v) = queue.pop_front() {
183            if v < rev_adj.len() {
184                for &w in &rev_adj[v] {
185                    if visited.insert(w) {
186                        queue.push_back(w);
187                    }
188                }
189            }
190        }
191        let _ = num_vertices;
192        visited
193    }
194
195    /// Build coverage sets for all input-output pairs.
196    fn build_coverage(
197        num_vertices: usize,
198        arcs: &[(usize, usize)],
199        inputs: &[usize],
200        outputs: &[usize],
201    ) -> Vec<HashSet<usize>> {
202        // Build adjacency lists
203        let mut adj = vec![vec![]; num_vertices];
204        let mut rev_adj = vec![vec![]; num_vertices];
205        for &(u, v) in arcs {
206            adj[u].push(v);
207            rev_adj[v].push(u);
208        }
209
210        // Precompute forward reachability from each input
211        let fwd: Vec<HashSet<usize>> = inputs
212            .iter()
213            .map(|&inp| Self::forward_reachable(num_vertices, &adj, inp))
214            .collect();
215
216        // Precompute backward reachability from each output
217        let bwd: Vec<HashSet<usize>> = outputs
218            .iter()
219            .map(|&out| Self::backward_reachable(num_vertices, &rev_adj, out))
220            .collect();
221
222        let num_outputs = outputs.len();
223        let mut coverage = Vec::with_capacity(inputs.len() * num_outputs);
224        for (i_idx, _) in inputs.iter().enumerate() {
225            for (o_idx, _) in outputs.iter().enumerate() {
226                // Coverage = vertices reachable from input i AND reachable backwards from output o
227                let cov: HashSet<usize> = fwd[i_idx].intersection(&bwd[o_idx]).copied().collect();
228                coverage.push(cov);
229            }
230        }
231        coverage
232    }
233
234    /// Get the number of vertices.
235    pub fn num_vertices(&self) -> usize {
236        self.num_vertices
237    }
238
239    /// Get the number of arcs.
240    pub fn num_arcs(&self) -> usize {
241        self.arcs.len()
242    }
243
244    /// Get the arcs.
245    pub fn arcs(&self) -> &[(usize, usize)] {
246        &self.arcs
247    }
248
249    /// Get the input vertices.
250    pub fn inputs(&self) -> &[usize] {
251        &self.inputs
252    }
253
254    /// Get the output vertices.
255    pub fn outputs(&self) -> &[usize] {
256        &self.outputs
257    }
258
259    /// Get the number of input vertices.
260    pub fn num_inputs(&self) -> usize {
261        self.inputs.len()
262    }
263
264    /// Get the number of output vertices.
265    pub fn num_outputs(&self) -> usize {
266        self.outputs.len()
267    }
268}
269
270impl Problem for MinimumFaultDetectionTestSet {
271    const NAME: &'static str = "MinimumFaultDetectionTestSet";
272    type Solution = Vec<Vec<bool>>;
273    type Value = Min<i64>;
274
275    crate::problem_parameters![
276        ("num_arcs", num_arcs),
277        ("num_inputs", num_inputs),
278        ("num_outputs", num_outputs),
279        ("num_vertices", num_vertices),
280    ];
281
282    fn variant() -> Vec<(&'static str, &'static str)> {
283        crate::variant_params![]
284    }
285
286    fn evaluate(
287        &self,
288        solution: &Self::Solution,
289    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
290        if solution.len() != self.inputs.len()
291            || solution.iter().any(|row| row.len() != self.outputs.len())
292        {
293            return Err(crate::traits::EvaluationError::InvalidConfiguration(
294                "fault-test matrix dimensions do not match the instance".into(),
295            ));
296        }
297        Ok({
298            let mut boundary = vec![false; self.num_vertices];
299            for &input in &self.inputs {
300                boundary[input] = true;
301            }
302            for &output in &self.outputs {
303                boundary[output] = true;
304            }
305            let required_internal_vertices =
306                boundary.iter().filter(|&&is_boundary| !is_boundary).count();
307
308            // Collect union of internal vertices covered by the selected pairs.
309            let mut covered: HashSet<usize> = HashSet::new();
310            let mut count = 0usize;
311            for (idx, &selected) in solution.iter().flatten().enumerate() {
312                if selected {
313                    count += 1;
314                    covered.extend(
315                        self.coverage[idx]
316                            .iter()
317                            .copied()
318                            .filter(|&vertex| !boundary[vertex]),
319                    );
320                }
321            }
322
323            // Check all internal vertices are covered.
324            if covered.len() == required_internal_vertices {
325                Min(Some(i64::try_from(count).map_err(|_| {
326                    crate::traits::EvaluationError::IntegerOverflow(
327                        "converting test-set size to i64".into(),
328                    )
329                })?))
330            } else {
331                Min(None)
332            }
333        })
334    }
335}
336
337impl crate::solvers::BruteForceProblem for MinimumFaultDetectionTestSet {
338    fn dimensions(&self) -> Vec<usize> {
339        vec![2; self.inputs.len() * self.outputs.len()]
340    }
341}
342
343crate::declare_variants! {
344    default MinimumFaultDetectionTestSet => "2^(num_inputs * num_outputs)",
345}
346
347crate::register_brute_force! {
348    MinimumFaultDetectionTestSet decode |problem: &MinimumFaultDetectionTestSet, indices: Vec<usize>| if problem.num_outputs() == 0 { vec![Vec::new(); problem.num_inputs()] } else { indices.chunks(problem.num_outputs()).map(crate::config::config_to_bits).collect() },
349}
350
351#[cfg(feature = "example-db")]
352pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
353    // 7 vertices, inputs={0,1}, outputs={5,6}
354    // Internal vertices are {2,3,4}
355    // Arcs: (0,2),(0,3),(1,3),(1,4),(2,5),(3,5),(3,6),(4,6)
356    // Pairs: (0,5)->{0,2,3,5}, (0,6)->{0,3,6}, (1,5)->{1,3,5}, (1,6)->{1,3,4,6}
357    // Config [1,0,0,1]: select pairs (0,5) and (1,6) -> covers all internal vertices -> Min(2)
358    vec![crate::example_db::specs::ModelExampleSpec {
359        id: "minimum_fault_detection_test_set",
360        instance: Box::new(MinimumFaultDetectionTestSet::new(
361            7,
362            vec![
363                (0, 2),
364                (0, 3),
365                (1, 3),
366                (1, 4),
367                (2, 5),
368                (3, 5),
369                (3, 6),
370                (4, 6),
371            ],
372            vec![0, 1],
373            vec![5, 6],
374        )),
375        optimal_config: serde_json::json!(vec![vec![true, false], vec![false, true]]),
376        optimal_value: serde_json::json!(2),
377    }]
378}
379
380#[cfg(test)]
381#[path = "../../unit_tests/models/misc/minimum_fault_detection_test_set.rs"]
382mod tests;
problemreductions/models/misc/minimum_fault_detection_test_set.rs

problemreductions/models/misc/
minimum_fault_detection_test_set.rs
