Struct MinimumFaultDetectionTestSet 

pub struct MinimumFaultDetectionTestSet { /* private fields */ }

The Minimum Fault Detection Test Set problem.

Given a directed acyclic graph G = (V, A) with designated input vertices I ⊆ V and output vertices O ⊆ V, find the minimum number of input-output pairs (i, o) ∈ I × O such that the union of their coverage sets covers every internal vertex V \ (I ∪ O).

For a pair (i, o), the coverage set is the set of vertices reachable from i that can also reach o (i.e., vertices on some i-to-o path). Inputs and outputs themselves are not required to be covered.

The configuration space is binary over all |I| × |O| pairs.

Example

use problemreductions::models::misc::MinimumFaultDetectionTestSet;
use problemreductions::{Problem, Solver, BruteForce};

let problem = MinimumFaultDetectionTestSet::new(
    7,
    vec![(0,2),(0,3),(1,3),(1,4),(2,5),(3,5),(3,6),(4,6)],
    vec![0, 1],
    vec![5, 6],
);
let solver = BruteForce::new();
use problemreductions::solvers::Solver as _;
let optimal = solver.solve(&problem);
assert_eq!(optimal, problemreductions::types::Min(Some(2)));

Implementations

impl MinimumFaultDetectionTestSet

pub fn new( num_vertices: usize, arcs: Vec<(usize, usize)>, inputs: Vec<usize>, outputs: Vec<usize>, ) -> Self

Create a new Minimum Fault Detection Test Set instance.

Panics

Panics if any arc index is out of bounds, if any input or output index is out of bounds, or if inputs or outputs are empty.

pub fn num_vertices(&self) -> usize

Get the number of vertices.

pub fn num_arcs(&self) -> usize

Get the number of arcs.

pub fn arcs(&self) -> &[(usize, usize)]

Get the arcs.

pub fn inputs(&self) -> &[usize]

Get the input vertices.

pub fn outputs(&self) -> &[usize]

Get the output vertices.

pub fn num_inputs(&self) -> usize

Get the number of input vertices.

pub fn num_outputs(&self) -> usize

Get the number of output vertices.

Trait Implementations

impl Clone for MinimumFaultDetectionTestSet

fn clone(&self) -> MinimumFaultDetectionTestSet

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for MinimumFaultDetectionTestSet

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for MinimumFaultDetectionTestSet

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Problem for MinimumFaultDetectionTestSet

const NAME: &'static str = "MinimumFaultDetectionTestSet"

Base name of this problem type (e.g., “MaximumIndependentSet”).

type Value = Min<usize>

The evaluation value type.

fn variant() -> Vec<(&'static str, &'static str)>

Returns variant attributes derived from type parameters.

fn dims(&self) -> Vec<usize>

Configuration space dimensions. Each entry is the cardinality of that variable.

fn evaluate(&self, config: &[usize]) -> Min<usize>

Evaluate the problem on a configuration.

fn num_variables(&self) -> usize

Number of variables (derived from dims).

fn problem_type() -> ProblemType

Look up this problem’s catalog entry.

impl ReduceTo<ILP> for MinimumFaultDetectionTestSet

type Result = ReductionMFDTSToILP

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl ReduceTo<MinimumFaultDetectionTestSet> for ExactCoverBy3Sets

type Result = ReductionXC3SToMinimumFaultDetectionTestSet

The reduction result type.

fn reduce_to(&self) -> Self::Result

Reduce this problem to the target problem type.

impl Serialize for MinimumFaultDetectionTestSet

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl DeclaredVariant for MinimumFaultDetectionTestSet