problemreductions/rules/
traits.rs

1//! Core traits for problem reductions.
2
3use crate::traits::Problem;
4use crate::types::ProblemSize;
5
6/// Result of reducing a source problem to a target problem.
7///
8/// This trait encapsulates the target problem and provides methods
9/// to extract solutions back to the source problem space.
10pub trait ReductionResult: Clone {
11    /// The source problem type.
12    type Source: Problem;
13    /// The target problem type.
14    type Target: Problem;
15
16    /// Get a reference to the target problem.
17    fn target_problem(&self) -> &Self::Target;
18
19    /// Extract a solution from target problem space to source problem space.
20    ///
21    /// # Arguments
22    /// * `target_solution` - A solution to the target problem
23    ///
24    /// # Returns
25    /// The corresponding solution in the source problem space
26    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize>;
27
28    /// Get the size of the source problem (for complexity analysis).
29    fn source_size(&self) -> ProblemSize;
30
31    /// Get the size of the target problem (for complexity analysis).
32    fn target_size(&self) -> ProblemSize;
33}
34
35/// Trait for problems that can be reduced to target type T.
36///
37/// # Example
38/// ```ignore
39/// let sat_problem = Satisfiability::new(...);
40/// let reduction = sat_problem.reduce_to::<IndependentSet<i32>>();
41/// let is_problem = reduction.target_problem();
42/// let solutions = solver.find_best(is_problem);
43/// let sat_solutions: Vec<_> = solutions.iter()
44///     .map(|s| reduction.extract_solution(s))
45///     .collect();
46/// ```
47pub trait ReduceTo<T: Problem>: Problem {
48    /// The reduction result type.
49    type Result: ReductionResult<Source = Self, Target = T>;
50
51    /// Reduce this problem to the target problem type.
52    fn reduce_to(&self) -> Self::Result;
53}
54
55#[cfg(test)]
56mod tests {
57    #[test]
58    fn test_traits_compile() {
59        // Traits should compile - actual tests in reduction implementations
60    }
61}
problemreductions/rules/traits.rs

problemreductions/rules/
traits.rs
