problemreductions/
traits.rs

1//! Core traits for problem definitions.
2
3use crate::graph_types::GraphMarker;
4use crate::types::{EnergyMode, LocalConstraint, LocalSolutionSize, NumericWeight, ProblemSize, SolutionSize};
5use num_traits::{Num, Zero};
6use std::ops::AddAssign;
7
8/// The core trait that all problems must implement.
9///
10/// This trait defines the interface for computational problems that can be
11/// solved by enumeration or reduction to other problems.
12pub trait Problem: Clone {
13    /// Base name of this problem type (e.g., "IndependentSet").
14    const NAME: &'static str;
15
16    /// The graph type this problem operates on.
17    type GraphType: GraphMarker;
18
19    /// The weight type for this problem.
20    type Weight: NumericWeight;
21
22    /// The type used for objective/size values.
23    type Size: Clone + PartialOrd + Num + Zero + AddAssign;
24
25    /// Returns the number of variables in the problem.
26    fn num_variables(&self) -> usize;
27
28    /// Returns the number of possible values (flavors) for each variable.
29    /// For binary problems, this is 2.
30    fn num_flavors(&self) -> usize;
31
32    /// Returns metadata about the problem size.
33    fn problem_size(&self) -> ProblemSize;
34
35    /// Returns whether larger or smaller objective values are better.
36    fn energy_mode(&self) -> EnergyMode;
37
38    /// Evaluate the solution size for a given configuration.
39    ///
40    /// # Arguments
41    /// * `config` - A slice of variable assignments, where each value is in 0..num_flavors.
42    ///
43    /// # Returns
44    /// A `SolutionSize` containing the objective value and validity.
45    fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size>;
46
47    /// Returns the range of variable indices.
48    fn variables(&self) -> std::ops::Range<usize> {
49        0..self.num_variables()
50    }
51
52    /// Returns the possible flavors as a vector.
53    fn flavors(&self) -> Vec<usize> {
54        (0..self.num_flavors()).collect()
55    }
56
57    /// Check if a configuration is valid for this problem.
58    fn is_valid_config(&self, config: &[usize]) -> bool {
59        if config.len() != self.num_variables() {
60            return false;
61        }
62        let num_flavors = self.num_flavors();
63        config.iter().all(|&v| v < num_flavors)
64    }
65
66    /// Evaluate multiple configurations at once (batch evaluation).
67    fn solution_size_multiple(&self, configs: &[Vec<usize>]) -> Vec<SolutionSize<Self::Size>> {
68        configs.iter().map(|c| self.solution_size(c)).collect()
69    }
70}
71
72/// Trait for constraint satisfaction problems.
73///
74/// These problems have explicit constraints that must be satisfied,
75/// and objectives that contribute to the solution size.
76pub trait ConstraintSatisfactionProblem: Problem {
77    /// Returns the hard constraints that must be satisfied.
78    fn constraints(&self) -> Vec<LocalConstraint>;
79
80    /// Returns the local objectives that contribute to solution size.
81    fn objectives(&self) -> Vec<LocalSolutionSize<Self::Size>>;
82
83    /// Returns the weights for the problem (e.g., vertex weights).
84    fn weights(&self) -> Vec<Self::Size>;
85
86    /// Set new weights for the problem.
87    fn set_weights(&mut self, weights: Vec<Self::Size>);
88
89    /// Returns whether the problem has non-uniform weights.
90    fn is_weighted(&self) -> bool;
91
92    /// Check if all constraints are satisfied by a configuration.
93    fn is_satisfied(&self, config: &[usize]) -> bool {
94        self.constraints().iter().all(|c| c.is_satisfied(config))
95    }
96
97    /// Compute the total objective value from all local objectives.
98    fn compute_objective(&self, config: &[usize]) -> Self::Size {
99        let mut total = Self::Size::zero();
100        for obj in self.objectives() {
101            total += obj.evaluate(config);
102        }
103        total
104    }
105}
106
107/// A blanket implementation helper for evaluating CSP solution sizes.
108/// This can be used by implementors of ConstraintSatisfactionProblem.
109pub fn csp_solution_size<P: ConstraintSatisfactionProblem>(
110    problem: &P,
111    config: &[usize],
112) -> SolutionSize<P::Size> {
113    let is_valid = problem.is_satisfied(config);
114    let size = problem.compute_objective(config);
115    SolutionSize::new(size, is_valid)
116}
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121    use crate::graph_types::SimpleGraph;
122
123    // A simple test problem: select binary variables to maximize sum of weights
124    #[derive(Clone)]
125    struct SimpleWeightedProblem {
126        weights: Vec<i32>,
127    }
128
129    impl Problem for SimpleWeightedProblem {
130        const NAME: &'static str = "SimpleWeightedProblem";
131        type GraphType = SimpleGraph;
132        type Weight = i32;
133        type Size = i32;
134
135        fn num_variables(&self) -> usize {
136            self.weights.len()
137        }
138
139        fn num_flavors(&self) -> usize {
140            2
141        }
142
143        fn problem_size(&self) -> ProblemSize {
144            ProblemSize::new(vec![("variables", self.weights.len())])
145        }
146
147        fn energy_mode(&self) -> EnergyMode {
148            EnergyMode::LargerSizeIsBetter
149        }
150
151        fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
152            let sum: i32 = config
153                .iter()
154                .zip(&self.weights)
155                .map(|(&c, &w)| if c == 1 { w } else { 0 })
156                .sum();
157            SolutionSize::valid(sum)
158        }
159    }
160
161    // A simple CSP for testing
162    #[derive(Clone)]
163    struct SimpleCsp {
164        num_vars: usize,
165    }
166
167    impl Problem for SimpleCsp {
168        const NAME: &'static str = "SimpleCsp";
169        type GraphType = SimpleGraph;
170        type Weight = i32;
171        type Size = i32;
172
173        fn num_variables(&self) -> usize {
174            self.num_vars
175        }
176
177        fn num_flavors(&self) -> usize {
178            2
179        }
180
181        fn problem_size(&self) -> ProblemSize {
182            ProblemSize::new(vec![("variables", self.num_vars)])
183        }
184
185        fn energy_mode(&self) -> EnergyMode {
186            EnergyMode::LargerSizeIsBetter
187        }
188
189        fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
190            csp_solution_size(self, config)
191        }
192    }
193
194    impl ConstraintSatisfactionProblem for SimpleCsp {
195        fn constraints(&self) -> Vec<LocalConstraint> {
196            // Constraint: at most one variable can be 1
197            if self.num_vars >= 2 {
198                vec![LocalConstraint::new(
199                    2,
200                    vec![0, 1],
201                    vec![true, true, true, false], // (0,0), (0,1), (1,0) OK; (1,1) invalid
202                )]
203            } else {
204                vec![]
205            }
206        }
207
208        fn objectives(&self) -> Vec<LocalSolutionSize<Self::Size>> {
209            // Each variable contributes 1 if selected
210            (0..self.num_vars)
211                .map(|i| LocalSolutionSize::new(2, vec![i], vec![0, 1]))
212                .collect()
213        }
214
215        fn weights(&self) -> Vec<Self::Size> {
216            vec![1; self.num_vars]
217        }
218
219        fn set_weights(&mut self, _weights: Vec<Self::Size>) {}
220
221        fn is_weighted(&self) -> bool {
222            false
223        }
224    }
225
226    #[test]
227    fn test_simple_problem() {
228        let problem = SimpleWeightedProblem {
229            weights: vec![1, 2, 3],
230        };
231
232        assert_eq!(problem.num_variables(), 3);
233        assert_eq!(problem.num_flavors(), 2);
234        assert_eq!(problem.variables(), 0..3);
235        assert_eq!(problem.flavors(), vec![0, 1]);
236
237        let sol = problem.solution_size(&[0, 0, 0]);
238        assert_eq!(sol.size, 0);
239        assert!(sol.is_valid);
240
241        let sol = problem.solution_size(&[1, 1, 1]);
242        assert_eq!(sol.size, 6);
243        assert!(sol.is_valid);
244
245        let sol = problem.solution_size(&[1, 0, 1]);
246        assert_eq!(sol.size, 4);
247        assert!(sol.is_valid);
248    }
249
250    #[test]
251    fn test_valid_config() {
252        let problem = SimpleWeightedProblem {
253            weights: vec![1, 2, 3],
254        };
255
256        assert!(problem.is_valid_config(&[0, 1, 0]));
257        assert!(problem.is_valid_config(&[1, 1, 1]));
258        assert!(!problem.is_valid_config(&[0, 2, 0])); // invalid flavor
259        assert!(!problem.is_valid_config(&[0, 1])); // wrong length
260        assert!(!problem.is_valid_config(&[0, 1, 0, 1])); // wrong length
261    }
262
263    #[test]
264    fn test_batch_evaluation() {
265        let problem = SimpleWeightedProblem {
266            weights: vec![1, 2, 3],
267        };
268
269        let configs = vec![vec![0, 0, 0], vec![1, 1, 1], vec![1, 0, 1]];
270
271        let results = problem.solution_size_multiple(&configs);
272        assert_eq!(results.len(), 3);
273        assert_eq!(results[0].size, 0);
274        assert_eq!(results[1].size, 6);
275        assert_eq!(results[2].size, 4);
276    }
277
278    #[test]
279    fn test_csp_solution_size() {
280        let problem = SimpleCsp { num_vars: 3 };
281
282        // Test valid configurations
283        let sol = problem.solution_size(&[0, 0, 0]);
284        assert!(sol.is_valid);
285        assert_eq!(sol.size, 0);
286
287        let sol = problem.solution_size(&[1, 0, 0]);
288        assert!(sol.is_valid);
289        assert_eq!(sol.size, 1);
290
291        let sol = problem.solution_size(&[0, 1, 0]);
292        assert!(sol.is_valid);
293        assert_eq!(sol.size, 1);
294
295        // Test invalid configuration (both 0 and 1 are 1)
296        let sol = problem.solution_size(&[1, 1, 0]);
297        assert!(!sol.is_valid);
298        assert_eq!(sol.size, 2);
299    }
300
301    #[test]
302    fn test_csp_is_satisfied() {
303        let problem = SimpleCsp { num_vars: 3 };
304
305        assert!(problem.is_satisfied(&[0, 0, 0]));
306        assert!(problem.is_satisfied(&[1, 0, 0]));
307        assert!(problem.is_satisfied(&[0, 1, 0]));
308        assert!(!problem.is_satisfied(&[1, 1, 0]));
309    }
310
311    #[test]
312    fn test_csp_compute_objective() {
313        let problem = SimpleCsp { num_vars: 3 };
314
315        assert_eq!(problem.compute_objective(&[0, 0, 0]), 0);
316        assert_eq!(problem.compute_objective(&[1, 0, 0]), 1);
317        assert_eq!(problem.compute_objective(&[1, 1, 0]), 2);
318        assert_eq!(problem.compute_objective(&[1, 1, 1]), 3);
319    }
320
321    #[test]
322    fn test_csp_single_variable() {
323        // Test CSP with num_vars = 1 (no constraints, empty constraint list)
324        let problem = SimpleCsp { num_vars: 1 };
325
326        assert!(problem.constraints().is_empty());
327        assert!(problem.is_satisfied(&[0])); // Always satisfied with no constraints
328        assert!(problem.is_satisfied(&[1]));
329
330        let sol = problem.solution_size(&[0]);
331        assert!(sol.is_valid);
332        assert_eq!(sol.size, 0);
333
334        let sol = problem.solution_size(&[1]);
335        assert!(sol.is_valid);
336        assert_eq!(sol.size, 1);
337    }
338
339    #[test]
340    fn test_csp_weights_and_weighted() {
341        let problem = SimpleCsp { num_vars: 3 };
342        assert_eq!(problem.weights(), vec![1, 1, 1]);
343        assert!(!problem.is_weighted());
344    }
345
346    #[test]
347    fn test_csp_set_weights() {
348        let mut problem = SimpleCsp { num_vars: 3 };
349        problem.set_weights(vec![10, 20, 30]);
350        // For SimpleCsp, set_weights is a no-op, so this just tests the call works
351        assert!(!problem.is_weighted());
352    }
353
354    #[test]
355    fn test_problem_size_metadata() {
356        let problem = SimpleWeightedProblem {
357            weights: vec![1, 2, 3, 4, 5],
358        };
359
360        let size = problem.problem_size();
361        assert_eq!(size.get("variables"), Some(5));
362    }
363
364    #[test]
365    fn test_energy_mode() {
366        let problem = SimpleWeightedProblem {
367            weights: vec![1, 2, 3],
368        };
369        assert!(problem.energy_mode().is_maximization());
370    }
371
372    #[test]
373    fn test_batch_evaluation_empty() {
374        let problem = SimpleWeightedProblem {
375            weights: vec![1, 2, 3],
376        };
377
378        let configs: Vec<Vec<usize>> = vec![];
379        let results = problem.solution_size_multiple(&configs);
380        assert!(results.is_empty());
381    }
382
383    #[test]
384    fn test_is_valid_config_empty_problem() {
385        let problem = SimpleWeightedProblem { weights: vec![] };
386
387        assert_eq!(problem.num_variables(), 0);
388        assert!(problem.is_valid_config(&[])); // Empty config for empty problem
389        assert!(!problem.is_valid_config(&[0])); // Non-empty config is invalid
390    }
391
392    #[test]
393    fn test_variables_range() {
394        let problem = SimpleWeightedProblem {
395            weights: vec![1, 2, 3, 4, 5],
396        };
397
398        let vars: Vec<usize> = problem.variables().collect();
399        assert_eq!(vars, vec![0, 1, 2, 3, 4]);
400    }
401
402    #[test]
403    fn test_flavors_list() {
404        let problem = SimpleWeightedProblem {
405            weights: vec![1, 2],
406        };
407
408        assert_eq!(problem.flavors(), vec![0, 1]);
409    }
410
411    #[test]
412    fn test_csp_objectives() {
413        let problem = SimpleCsp { num_vars: 3 };
414        let objectives = problem.objectives();
415
416        assert_eq!(objectives.len(), 3);
417        // Test that each objective evaluates correctly
418        assert_eq!(objectives[0].evaluate(&[0, 0, 0]), 0);
419        assert_eq!(objectives[0].evaluate(&[1, 0, 0]), 1);
420        assert_eq!(objectives[1].evaluate(&[0, 1, 0]), 1);
421        assert_eq!(objectives[2].evaluate(&[0, 0, 1]), 1);
422    }
423
424    #[test]
425    fn test_csp_solution_size_helper_function() {
426        let problem = SimpleCsp { num_vars: 2 };
427
428        // Test via the helper function directly
429        let sol = csp_solution_size(&problem, &[0, 0]);
430        assert!(sol.is_valid);
431        assert_eq!(sol.size, 0);
432
433        let sol = csp_solution_size(&problem, &[1, 0]);
434        assert!(sol.is_valid);
435        assert_eq!(sol.size, 1);
436
437        let sol = csp_solution_size(&problem, &[1, 1]);
438        assert!(!sol.is_valid);
439        assert_eq!(sol.size, 2);
440    }
441
442    // Test problem with more than 2 flavors
443    #[derive(Clone)]
444    struct MultiFlavorProblem {
445        num_vars: usize,
446        num_flavors: usize,
447    }
448
449    impl Problem for MultiFlavorProblem {
450        const NAME: &'static str = "MultiFlavorProblem";
451        type GraphType = SimpleGraph;
452        type Weight = i32;
453        type Size = i32;
454
455        fn num_variables(&self) -> usize {
456            self.num_vars
457        }
458
459        fn num_flavors(&self) -> usize {
460            self.num_flavors
461        }
462
463        fn problem_size(&self) -> ProblemSize {
464            ProblemSize::new(vec![
465                ("variables", self.num_vars),
466                ("flavors", self.num_flavors),
467            ])
468        }
469
470        fn energy_mode(&self) -> EnergyMode {
471            EnergyMode::SmallerSizeIsBetter
472        }
473
474        fn solution_size(&self, config: &[usize]) -> SolutionSize<Self::Size> {
475            let sum: i32 = config.iter().map(|&c| c as i32).sum();
476            SolutionSize::valid(sum)
477        }
478    }
479
480    #[test]
481    fn test_multi_flavor_problem() {
482        let problem = MultiFlavorProblem {
483            num_vars: 3,
484            num_flavors: 4,
485        };
486
487        assert_eq!(problem.num_flavors(), 4);
488        assert_eq!(problem.flavors(), vec![0, 1, 2, 3]);
489        assert!(problem.energy_mode().is_minimization());
490
491        // Valid configs
492        assert!(problem.is_valid_config(&[0, 1, 2]));
493        assert!(problem.is_valid_config(&[3, 3, 3]));
494
495        // Invalid: flavor out of range
496        assert!(!problem.is_valid_config(&[0, 4, 0]));
497        assert!(!problem.is_valid_config(&[5, 0, 0]));
498
499        let sol = problem.solution_size(&[0, 1, 2]);
500        assert_eq!(sol.size, 3);
501
502        let sol = problem.solution_size(&[3, 3, 3]);
503        assert_eq!(sol.size, 9);
504    }
505
506    #[test]
507    fn test_batch_evaluation_with_multi_flavor() {
508        let problem = MultiFlavorProblem {
509            num_vars: 2,
510            num_flavors: 3,
511        };
512
513        let configs = vec![vec![0, 0], vec![1, 1], vec![2, 2], vec![0, 2]];
514        let results = problem.solution_size_multiple(&configs);
515
516        assert_eq!(results.len(), 4);
517        assert_eq!(results[0].size, 0);
518        assert_eq!(results[1].size, 2);
519        assert_eq!(results[2].size, 4);
520        assert_eq!(results[3].size, 2);
521    }
522}
problemreductions/traits.rs

problemreductions/
traits.rs
