problemreductions/
traits.rs

1//! Core traits for problem definitions.
2
3/// Minimal problem trait — a problem is a function from configuration to metric.
4///
5/// This trait defines the interface for computational problems that can be
6/// solved by enumeration or reduction to other problems.
7pub trait Problem: Clone {
8    /// Base name of this problem type (e.g., "MaximumIndependentSet").
9    const NAME: &'static str;
10    /// The evaluation metric type.
11    type Metric: Clone;
12    /// Configuration space dimensions. Each entry is the cardinality of that variable.
13    fn dims(&self) -> Vec<usize>;
14    /// Evaluate the problem on a configuration.
15    fn evaluate(&self, config: &[usize]) -> Self::Metric;
16    /// Number of variables (derived from dims).
17    fn num_variables(&self) -> usize {
18        self.dims().len()
19    }
20    /// Returns variant attributes derived from type parameters.
21    ///
22    /// Used for generating variant IDs in the reduction graph schema.
23    /// Returns pairs like `[("graph", "SimpleGraph"), ("weight", "i32")]`.
24    fn variant() -> Vec<(&'static str, &'static str)>;
25
26    /// Look up this problem's catalog entry.
27    ///
28    /// Returns the full [`ProblemType`] metadata from the catalog registry.
29    /// The default implementation uses `Self::NAME` to perform the lookup.
30    fn problem_type() -> crate::registry::ProblemType {
31        crate::registry::find_problem_type(Self::NAME)
32            .unwrap_or_else(|| panic!("no catalog entry for Problem::NAME = {:?}", Self::NAME))
33    }
34}
35
36/// Extension for problems with a numeric objective to optimize.
37///
38/// The supertrait bound guarantees `Metric = SolutionSize<Self::Value>`,
39/// so the solver can call `metric.is_valid()` and `metric.is_better()`
40/// directly — no per-problem customization needed.
41pub trait OptimizationProblem: Problem<Metric = crate::types::SolutionSize<Self::Value>> {
42    /// The inner objective value type (e.g., `i32`, `f64`).
43    type Value: PartialOrd + Clone;
44    /// Whether to maximize or minimize the metric.
45    fn direction(&self) -> crate::types::Direction;
46}
47
48/// Marker trait for satisfaction (decision) problems.
49///
50/// Satisfaction problems evaluate configurations to `bool`:
51/// `true` if the configuration satisfies all constraints, `false` otherwise.
52pub trait SatisfactionProblem: Problem<Metric = bool> {}
53
54/// Marker trait for explicitly declared problem variants.
55///
56/// Implemented automatically by [`declare_variants!`] for each concrete type.
57/// The [`#[reduction]`] proc macro checks this trait at compile time to ensure
58/// all reduction source/target types have been declared.
59pub trait DeclaredVariant {}
60
61#[cfg(test)]
62#[path = "unit_tests/traits.rs"]
63mod tests;
problemreductions/traits.rs

problemreductions/
traits.rs
