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        Self::try_new(data.num_vertices, data.arcs, data.inputs, data.outputs)
91            .map_err(serde::de::Error::custom)
92    }
93}
94
95impl MinimumFaultDetectionTestSet {
96    /// Create a new Minimum Fault Detection Test Set instance.
97    ///
98    /// # Panics
99    ///
100    /// Panics if any arc index is out of bounds, if any input or output index
101    /// is out of bounds, or if inputs or outputs are empty.
102    pub fn new(
103        num_vertices: usize,
104        arcs: Vec<(usize, usize)>,
105        inputs: Vec<usize>,
106        outputs: Vec<usize>,
107    ) -> Self {
108        Self::try_new(num_vertices, arcs, inputs, outputs).unwrap_or_else(|error| panic!("{error}"))
109    }
110
111    fn try_new(
112        num_vertices: usize,
113        arcs: Vec<(usize, usize)>,
114        inputs: Vec<usize>,
115        outputs: Vec<usize>,
116    ) -> Result<Self, crate::registry::ConstructionError> {
117        if inputs.is_empty() {
118            return Err("Inputs must not be empty".into());
119        }
120        if outputs.is_empty() {
121            return Err("Outputs must not be empty".into());
122        }
123        for (i, &(u, v)) in arcs.iter().enumerate() {
124            if u >= num_vertices || v >= num_vertices {
125                return Err(format!(
126                    "Arc {} ({}, {}) out of bounds for {} vertices",
127                    i, u, v, num_vertices
128                )
129                .into());
130            }
131        }
132        for &inp in &inputs {
133            if inp >= num_vertices {
134                return Err(format!(
135                    "Input vertex {} out of bounds for {} vertices",
136                    inp, num_vertices
137                )
138                .into());
139            }
140        }
141        for &out in &outputs {
142            if out >= num_vertices {
143                return Err(format!(
144                    "Output vertex {} out of bounds for {} vertices",
145                    out, num_vertices
146                )
147                .into());
148            }
149        }
150        let coverage = Self::build_coverage(num_vertices, &arcs, &inputs, &outputs);
151        Ok(Self {
152            num_vertices,
153            arcs,
154            inputs,
155            outputs,
156            coverage,
157        })
158    }
159
160    /// Compute forward reachability from a given vertex using BFS on the DAG.
161    fn forward_reachable(num_vertices: usize, adj: &[Vec<usize>], start: usize) -> HashSet<usize> {
162        let mut visited = HashSet::new();
163        let mut queue = VecDeque::new();
164        visited.insert(start);
165        queue.push_back(start);
166        while let Some(v) = queue.pop_front() {
167            if v < adj.len() {
168                for &w in &adj[v] {
169                    if visited.insert(w) {
170                        queue.push_back(w);
171                    }
172                }
173            }
174        }
175        let _ = num_vertices; // used only to clarify signature
176        visited
177    }
178
179    /// Compute backward reachability from a given vertex using BFS on the reverse DAG.
180    fn backward_reachable(
181        num_vertices: usize,
182        rev_adj: &[Vec<usize>],
183        start: usize,
184    ) -> HashSet<usize> {
185        let mut visited = HashSet::new();
186        let mut queue = VecDeque::new();
187        visited.insert(start);
188        queue.push_back(start);
189        while let Some(v) = queue.pop_front() {
190            if v < rev_adj.len() {
191                for &w in &rev_adj[v] {
192                    if visited.insert(w) {
193                        queue.push_back(w);
194                    }
195                }
196            }
197        }
198        let _ = num_vertices;
199        visited
200    }
201
202    /// Build coverage sets for all input-output pairs.
203    fn build_coverage(
204        num_vertices: usize,
205        arcs: &[(usize, usize)],
206        inputs: &[usize],
207        outputs: &[usize],
208    ) -> Vec<HashSet<usize>> {
209        // Build adjacency lists
210        let mut adj = vec![vec![]; num_vertices];
211        let mut rev_adj = vec![vec![]; num_vertices];
212        for &(u, v) in arcs {
213            adj[u].push(v);
214            rev_adj[v].push(u);
215        }
216
217        // Precompute forward reachability from each input
218        let fwd: Vec<HashSet<usize>> = inputs
219            .iter()
220            .map(|&inp| Self::forward_reachable(num_vertices, &adj, inp))
221            .collect();
222
223        // Precompute backward reachability from each output
224        let bwd: Vec<HashSet<usize>> = outputs
225            .iter()
226            .map(|&out| Self::backward_reachable(num_vertices, &rev_adj, out))
227            .collect();
228
229        let num_outputs = outputs.len();
230        let mut coverage = Vec::with_capacity(inputs.len() * num_outputs);
231        for (i_idx, _) in inputs.iter().enumerate() {
232            for (o_idx, _) in outputs.iter().enumerate() {
233                // Coverage = vertices reachable from input i AND reachable backwards from output o
234                let cov: HashSet<usize> = fwd[i_idx].intersection(&bwd[o_idx]).copied().collect();
235                coverage.push(cov);
236            }
237        }
238        coverage
239    }
240
241    /// Get the number of vertices.
242    pub fn num_vertices(&self) -> usize {
243        self.num_vertices
244    }
245
246    /// Get the number of arcs.
247    pub fn num_arcs(&self) -> usize {
248        self.arcs.len()
249    }
250
251    /// Get the arcs.
252    pub fn arcs(&self) -> &[(usize, usize)] {
253        &self.arcs
254    }
255
256    /// Get the input vertices.
257    pub fn inputs(&self) -> &[usize] {
258        &self.inputs
259    }
260
261    /// Get the output vertices.
262    pub fn outputs(&self) -> &[usize] {
263        &self.outputs
264    }
265
266    /// Get the number of input vertices.
267    pub fn num_inputs(&self) -> usize {
268        self.inputs.len()
269    }
270
271    /// Get the number of output vertices.
272    pub fn num_outputs(&self) -> usize {
273        self.outputs.len()
274    }
275}
276
277impl Problem for MinimumFaultDetectionTestSet {
278    const NAME: &'static str = "MinimumFaultDetectionTestSet";
279    type Solution = Vec<Vec<bool>>;
280    type Value = Min<i64>;
281
282    crate::problem_parameters![
283        ("num_arcs", num_arcs),
284        ("num_inputs", num_inputs),
285        ("num_outputs", num_outputs),
286        ("num_vertices", num_vertices),
287    ];
288
289    fn variant() -> Vec<(&'static str, &'static str)> {
290        crate::variant_params![]
291    }
292
293    fn evaluate(
294        &self,
295        solution: &Self::Solution,
296    ) -> Result<Min<i64>, crate::traits::EvaluationError> {
297        if solution.len() != self.inputs.len()
298            || solution.iter().any(|row| row.len() != self.outputs.len())
299        {
300            return Err(crate::traits::EvaluationError::InvalidConfiguration(
301                "fault-test matrix dimensions do not match the instance".into(),
302            ));
303        }
304        Ok({
305            let mut boundary = vec![false; self.num_vertices];
306            for &input in &self.inputs {
307                boundary[input] = true;
308            }
309            for &output in &self.outputs {
310                boundary[output] = true;
311            }
312            let required_internal_vertices =
313                boundary.iter().filter(|&&is_boundary| !is_boundary).count();
314
315            // Collect union of internal vertices covered by the selected pairs.
316            let mut covered: HashSet<usize> = HashSet::new();
317            let mut count = 0usize;
318            for (idx, &selected) in solution.iter().flatten().enumerate() {
319                if selected {
320                    count += 1;
321                    covered.extend(
322                        self.coverage[idx]
323                            .iter()
324                            .copied()
325                            .filter(|&vertex| !boundary[vertex]),
326                    );
327                }
328            }
329
330            // Check all internal vertices are covered.
331            if covered.len() == required_internal_vertices {
332                Min(Some(i64::try_from(count).map_err(|_| {
333                    crate::traits::EvaluationError::IntegerOverflow(
334                        "converting test-set size to i64".into(),
335                    )
336                })?))
337            } else {
338                Min(None)
339            }
340        })
341    }
342}
343
344impl crate::solvers::BruteForceProblem for MinimumFaultDetectionTestSet {
345    fn dimensions(&self) -> Vec<usize> {
346        vec![2; self.inputs.len() * self.outputs.len()]
347    }
348}
349
350crate::declare_variants! {
351    default MinimumFaultDetectionTestSet => "2^(num_inputs * num_outputs)",
352}
353
354crate::register_brute_force! {
355    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() },
356}
357
358#[cfg(feature = "example-db")]
359pub(crate) fn canonical_model_example_specs() -> Vec<crate::example_db::specs::ModelExampleSpec> {
360    // 7 vertices, inputs={0,1}, outputs={5,6}
361    // Internal vertices are {2,3,4}
362    // Arcs: (0,2),(0,3),(1,3),(1,4),(2,5),(3,5),(3,6),(4,6)
363    // Pairs: (0,5)->{0,2,3,5}, (0,6)->{0,3,6}, (1,5)->{1,3,5}, (1,6)->{1,3,4,6}
364    // Config [1,0,0,1]: select pairs (0,5) and (1,6) -> covers all internal vertices -> Min(2)
365    vec![crate::example_db::specs::ModelExampleSpec {
366        id: "minimum_fault_detection_test_set",
367        instance: Box::new(MinimumFaultDetectionTestSet::new(
368            7,
369            vec![
370                (0, 2),
371                (0, 3),
372                (1, 3),
373                (1, 4),
374                (2, 5),
375                (3, 5),
376                (3, 6),
377                (4, 6),
378            ],
379            vec![0, 1],
380            vec![5, 6],
381        )),
382        optimal_config: serde_json::json!(vec![vec![true, false], vec![false, true]]),
383        optimal_value: serde_json::json!(2),
384    }]
385}
386
387#[cfg(test)]
388#[path = "../../unit_tests/models/misc/minimum_fault_detection_test_set.rs"]
389mod tests;
problemreductions/models/misc/minimum_fault_detection_test_set.rs

problemreductions/models/misc/
minimum_fault_detection_test_set.rs
