pub trait ReduceTo<T: Problem>: Problem {
type Result: ReductionResult<Source = Self, Target = T>;
// Required method
fn reduce_to(&self) -> Result<Self::Result, ReductionError>;
// Provided methods
fn target_construction(error: ConstructionError) -> ReductionError
where Self: Sized { ... }
fn exact_i64(
value: usize,
operation: impl Into<String>,
) -> Result<i64, ReductionError>
where Self: Sized { ... }
}Expand description
Trait for problems that can be reduced to target type T.
§Example
// Example showing reduction workflow
use problemreductions::prelude::*;
use problemreductions::rules::ReduceTo;
let sat_problem: Satisfiability = Satisfiability::new(
3, // 3 variables
vec![
CNFClause::new(vec![0, 1]), // (x0 OR x1)
CNFClause::new(vec![1, 2]), // (x1 OR x2)
]
);
// Reduce to Independent Set
let reduction = sat_problem.reduce_to().expect("reduction should succeed");
let is_problem = reduction.target_problem();
// Solve and extract solutions
let solver = BruteForce::new();
let solutions = solver.find_all_witnesses(is_problem).unwrap();
let sat_solutions: Vec<_> = solutions.iter()
.map(|s| reduction.extract_solution(s))
.collect();Required Associated Types§
Sourcetype Result: ReductionResult<Source = Self, Target = T>
type Result: ReductionResult<Source = Self, Target = T>
The reduction result type.
Required Methods§
Sourcefn reduce_to(&self) -> Result<Self::Result, ReductionError>
fn reduce_to(&self) -> Result<Self::Result, ReductionError>
Reduce this problem to the target problem type.
Provided Methods§
Sourcefn target_construction(error: ConstructionError) -> ReductionErrorwhere
Self: Sized,
fn target_construction(error: ConstructionError) -> ReductionErrorwhere
Self: Sized,
Attach this reduction edge to a target-construction failure.
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".