problemreductions/rules/
traits.rs

1//! Core traits for problem reductions.
2
3use crate::traits::Problem;
4use std::any::Any;
5use std::marker::PhantomData;
6
7/// Result of reducing a source problem to a target problem.
8///
9/// This trait encapsulates the target problem and provides methods
10/// to extract solutions back to the source problem space.
11pub trait ReductionResult {
12    /// The source problem type.
13    type Source: Problem;
14    /// The target problem type.
15    type Target: Problem;
16
17    /// Get a reference to the target problem.
18    fn target_problem(&self) -> &Self::Target;
19
20    /// Extract a solution from target problem space to source problem space.
21    ///
22    /// # Arguments
23    /// * `target_solution` - A solution to the target problem
24    ///
25    /// # Returns
26    /// The corresponding solution in the source problem space
27    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize>;
28}
29
30/// Trait for problems that can be reduced to target type T.
31///
32/// # Example
33/// ```text
34/// // Example showing reduction workflow
35/// use problemreductions::prelude::*;
36/// use problemreductions::rules::ReduceTo;
37///
38/// let sat_problem: Satisfiability = Satisfiability::new(
39///     3,  // 3 variables
40///     vec![
41///         CNFClause::new(vec![0, 1]),     // (x0 OR x1)
42///         CNFClause::new(vec![1, 2]),     // (x1 OR x2)
43///     ]
44/// );
45///
46/// // Reduce to Independent Set
47/// let reduction = sat_problem.reduce_to();
48/// let is_problem = reduction.target_problem();
49///
50/// // Solve and extract solutions
51/// let solver = BruteForce::new();
52/// let solutions = solver.find_all_best(is_problem);
53/// let sat_solutions: Vec<_> = solutions.iter()
54///     .map(|s| reduction.extract_solution(s))
55///     .collect();
56/// ```
57pub trait ReduceTo<T: Problem>: Problem {
58    /// The reduction result type.
59    type Result: ReductionResult<Source = Self, Target = T>;
60
61    /// Reduce this problem to the target problem type.
62    fn reduce_to(&self) -> Self::Result;
63}
64
65/// Generic reduction result for natural-edge (subtype) reductions.
66///
67/// Used when a problem on a specific graph type is trivially reducible to
68/// the same problem on a more general graph type (e.g., `MIS<Triangular>` →
69/// `MIS<SimpleGraph>`). The solution mapping is identity — vertex indices
70/// are preserved.
71#[derive(Debug, Clone)]
72pub struct ReductionAutoCast<S: Problem, T: Problem> {
73    target: T,
74    _phantom: PhantomData<S>,
75}
76
77impl<S: Problem, T: Problem> ReductionAutoCast<S, T> {
78    /// Create a new auto-cast reduction result.
79    pub fn new(target: T) -> Self {
80        Self {
81            target,
82            _phantom: PhantomData,
83        }
84    }
85}
86
87impl<S: Problem, T: Problem> ReductionResult for ReductionAutoCast<S, T> {
88    type Source = S;
89    type Target = T;
90
91    fn target_problem(&self) -> &Self::Target {
92        &self.target
93    }
94
95    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
96        target_solution.to_vec()
97    }
98}
99
100/// Type-erased reduction result for runtime-discovered paths.
101///
102/// Implemented automatically for all `ReductionResult` types via blanket impl.
103/// Used internally by `ReductionChain`.
104pub trait DynReductionResult {
105    /// Get the target problem as a type-erased reference.
106    fn target_problem_any(&self) -> &dyn Any;
107    /// Extract a solution from target space to source space.
108    fn extract_solution_dyn(&self, target_solution: &[usize]) -> Vec<usize>;
109}
110
111impl<R: ReductionResult + 'static> DynReductionResult for R
112where
113    R::Target: 'static,
114{
115    fn target_problem_any(&self) -> &dyn Any {
116        self.target_problem() as &dyn Any
117    }
118    fn extract_solution_dyn(&self, target_solution: &[usize]) -> Vec<usize> {
119        self.extract_solution(target_solution)
120    }
121}
122
123#[cfg(test)]
124#[path = "../unit_tests/rules/traits.rs"]
125mod tests;
problemreductions/rules/traits.rs

problemreductions/rules/
traits.rs
