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
27/// Extension for problems with a numeric objective to optimize.
28///
29/// The supertrait bound guarantees `Metric = SolutionSize<Self::Value>`,
30/// so the solver can call `metric.is_valid()` and `metric.is_better()`
31/// directly — no per-problem customization needed.
32pub trait OptimizationProblem: Problem<Metric = crate::types::SolutionSize<Self::Value>> {
33    /// The inner objective value type (e.g., `i32`, `f64`).
34    type Value: PartialOrd + Clone;
35    /// Whether to maximize or minimize the metric.
36    fn direction(&self) -> crate::types::Direction;
37}
38
39/// Marker trait for satisfaction (decision) problems.
40///
41/// Satisfaction problems evaluate configurations to `bool`:
42/// `true` if the configuration satisfies all constraints, `false` otherwise.
43pub trait SatisfactionProblem: Problem<Metric = bool> {}
44
45/// Marker trait for explicitly declared problem variants.
46///
47/// Implemented automatically by [`declare_variants!`] for each concrete type.
48/// The [`#[reduction]`] proc macro checks this trait at compile time to ensure
49/// all reduction source/target types have been declared.
50pub trait DeclaredVariant {}
51
52#[cfg(test)]
53#[path = "unit_tests/traits.rs"]
54mod tests;
problemreductions/traits.rs

problemreductions/
traits.rs
