genalg/constraints/
combinatorial.rs

1//! # Combinatorial Constraints
2//!
3//! This module provides common constraints for combinatorial optimization problems.
4//! These constraints are particularly useful for problems involving selection, assignment,
5//! or sequencing of discrete elements.
6
7use std::collections::{HashMap, HashSet};
8use std::fmt::Debug;
9use std::hash::Hash;
10use std::marker::PhantomData;
11
12use crate::constraints::{Constraint, ConstraintError, ConstraintViolation};
13use crate::phenotype::Phenotype;
14use crate::rng::RandomNumberGenerator;
15
16/// Result type for constraint operations.
17pub type Result<T> = std::result::Result<T, ConstraintError>;
18
19/// Ensures that all elements in a collection are unique.
20///
21/// This constraint is useful for problems where each element can only be used once,
22/// such as assignment problems or permutation problems.
23#[derive(Debug, Clone)]
24pub struct UniqueElementsConstraint<P, T, F>
25where
26    P: Phenotype,
27    T: Eq + Hash + Debug + Clone + Send + Sync,
28    F: Fn(&P) -> Vec<T> + Send + Sync + Debug,
29{
30    /// Name of the constraint for error messages
31    name: String,
32    /// Function to extract the elements to check for uniqueness
33    extractor: F,
34    _marker: PhantomData<(P, T)>,
35}
36
37impl<P, T, F> UniqueElementsConstraint<P, T, F>
38where
39    P: Phenotype,
40    T: Eq + Hash + Debug + Clone + Send + Sync,
41    F: Fn(&P) -> Vec<T> + Send + Sync + Debug,
42{
43    /// Creates a new unique elements constraint with the given name and extractor function.
44    ///
45    /// The extractor function is used to extract the elements to check for uniqueness
46    /// from the phenotype.
47    ///
48    /// # Arguments
49    ///
50    /// * `name` - The name of the constraint for error messages.
51    /// * `extractor` - A function that extracts the elements to check for uniqueness from the phenotype.
52    ///
53    /// # Returns
54    ///
55    /// A new unique elements constraint, or an error if the name is empty.
56    pub fn new<S: Into<String>>(name: S, extractor: F) -> Result<Self> {
57        let name = name.into();
58        if name.is_empty() {
59            return Err(ConstraintError::EmptyName);
60        }
61        Ok(Self {
62            name,
63            extractor,
64            _marker: PhantomData,
65        })
66    }
67
68    /// Returns the name of the constraint.
69    pub fn name(&self) -> &str {
70        &self.name
71    }
72}
73
74impl<P, T, F> Constraint<P> for UniqueElementsConstraint<P, T, F>
75where
76    P: Phenotype,
77    T: Eq + Hash + Debug + Clone + Send + Sync,
78    F: Fn(&P) -> Vec<T> + Send + Sync + Debug,
79{
80    fn check(&self, phenotype: &P) -> Vec<ConstraintViolation> {
81        let elements = (self.extractor)(phenotype);
82        let mut seen = HashSet::new();
83        let mut violations = Vec::new();
84
85        for (idx, element) in elements.iter().enumerate() {
86            if !seen.insert(element) {
87                violations.push(ConstraintViolation::new(
88                    &self.name,
89                    format!("Duplicate element {:?} at position {}", element, idx),
90                ));
91            }
92        }
93
94        violations
95    }
96
97    fn repair_with_rng(&self, phenotype: &mut P, rng: &mut RandomNumberGenerator) -> bool {
98        // This is a generic implementation that might not work for all phenotypes
99        // It relies on the phenotype's mutate method to potentially fix the uniqueness issue
100
101        // Check if there are any violations
102        let violations = self.check(phenotype);
103        if violations.is_empty() {
104            return false; // No violations to repair
105        }
106
107        // Try to repair by mutating the phenotype
108        phenotype.mutate(rng);
109
110        // Check if repair was successful
111        let new_violations = self.check(phenotype);
112        new_violations.is_empty()
113    }
114}
115
116/// Ensures that all required keys are assigned a value.
117///
118/// This constraint is useful for assignment problems where each key must be assigned
119/// a value from a set of possible values.
120#[derive(Debug, Clone)]
121pub struct CompleteAssignmentConstraint<P, K, V, F>
122where
123    P: Phenotype,
124    K: Eq + Hash + Debug + Clone + Send + Sync,
125    V: Debug + Clone + Send + Sync,
126    F: Fn(&P) -> HashMap<K, V> + Send + Sync + Debug,
127{
128    /// Name of the constraint for error messages
129    name: String,
130    /// Function to extract the assignments from the phenotype
131    extractor: F,
132    /// The set of keys that must be assigned
133    required_keys: HashSet<K>,
134    /// Phantom data for the value type
135    _marker: PhantomData<P>,
136}
137
138impl<P, K, V, F> CompleteAssignmentConstraint<P, K, V, F>
139where
140    P: Phenotype,
141    K: Eq + Hash + Debug + Clone + Send + Sync,
142    V: Debug + Clone + Send + Sync,
143    F: Fn(&P) -> HashMap<K, V> + Send + Sync + Debug,
144{
145    /// Creates a new complete assignment constraint with the given name, extractor function,
146    /// and set of required keys.
147    ///
148    /// # Arguments
149    ///
150    /// * `name` - The name of the constraint for error messages.
151    /// * `extractor` - A function that extracts the assignments from the phenotype.
152    /// * `required_keys` - The set of keys that must be assigned.
153    ///
154    /// # Returns
155    ///
156    /// A new complete assignment constraint, or an error if the name is empty or if the required keys set is empty.
157    pub fn new<S: Into<String>>(name: S, extractor: F, required_keys: HashSet<K>) -> Result<Self> {
158        let name = name.into();
159        if name.is_empty() {
160            return Err(ConstraintError::EmptyName);
161        }
162        if required_keys.is_empty() {
163            return Err(ConstraintError::EmptyCollection(
164                "Required keys set".to_string(),
165            ));
166        }
167        Ok(Self {
168            name,
169            extractor,
170            required_keys,
171            _marker: PhantomData,
172        })
173    }
174}
175
176impl<P, K, V, F> Constraint<P> for CompleteAssignmentConstraint<P, K, V, F>
177where
178    P: Phenotype,
179    K: Eq + Hash + Debug + Clone + Send + Sync,
180    V: Debug + Clone + Send + Sync,
181    F: Fn(&P) -> HashMap<K, V> + Send + Sync + Debug,
182{
183    fn check(&self, phenotype: &P) -> Vec<ConstraintViolation> {
184        let assignments = (self.extractor)(phenotype);
185        let mut violations = Vec::new();
186
187        for key in &self.required_keys {
188            if !assignments.contains_key(key) {
189                violations.push(ConstraintViolation::new(
190                    &self.name,
191                    format!("Missing assignment for key {:?}", key),
192                ));
193            }
194        }
195
196        violations
197    }
198
199    fn repair_with_rng(&self, phenotype: &mut P, rng: &mut RandomNumberGenerator) -> bool {
200        // This is a generic implementation that might not work for all phenotypes
201        // It relies on the phenotype's mutate method to potentially fix the assignment issue
202
203        // Check if there are any violations
204        let violations = self.check(phenotype);
205        if violations.is_empty() {
206            return false; // No violations to repair
207        }
208
209        // Try to repair by mutating the phenotype
210        phenotype.mutate(rng);
211
212        // Check if repair was successful
213        let new_violations = self.check(phenotype);
214        new_violations.is_empty()
215    }
216}
217
218/// Ensures that assignments satisfy capacity constraints.
219///
220/// This constraint is useful for bin packing or resource allocation problems
221/// where each bin or resource has a limited capacity.
222#[derive(Debug, Clone)]
223pub struct CapacityConstraint<P, K, V, F, G>
224where
225    P: Phenotype,
226    K: Eq + Hash + Debug + Clone + Send + Sync,
227    V: Eq + Hash + Debug + Clone + Send + Sync,
228    F: Fn(&P) -> HashMap<V, Vec<K>> + Send + Sync + Debug,
229    G: Fn(&V) -> usize + Send + Sync + Debug,
230{
231    /// Name of the constraint for error messages
232    name: String,
233    /// Function to extract the assignments from the phenotype
234    extractor: F,
235    /// Function to get the capacity of each bin
236    capacity_fn: G,
237    /// Phantom data for the key and value types
238    _marker: PhantomData<P>,
239}
240
241impl<P, K, V, F, G> CapacityConstraint<P, K, V, F, G>
242where
243    P: Phenotype,
244    K: Eq + Hash + Debug + Clone + Send + Sync,
245    V: Eq + Hash + Debug + Clone + Send + Sync,
246    F: Fn(&P) -> HashMap<V, Vec<K>> + Send + Sync + Debug,
247    G: Fn(&V) -> usize + Send + Sync + Debug,
248{
249    /// Creates a new capacity constraint with the given name, extractor function,
250    /// and capacity function.
251    ///
252    /// # Arguments
253    ///
254    /// * `name` - The name of the constraint for error messages.
255    /// * `extractor` - A function that extracts the assignments from the phenotype.
256    /// * `capacity_fn` - A function that returns the capacity of each bin.
257    ///
258    /// # Returns
259    ///
260    /// A new capacity constraint, or an error if the name is empty.
261    pub fn new<S: Into<String>>(name: S, extractor: F, capacity_fn: G) -> Result<Self> {
262        let name = name.into();
263        if name.is_empty() {
264            return Err(ConstraintError::EmptyName);
265        }
266        Ok(Self {
267            name,
268            extractor,
269            capacity_fn,
270            _marker: PhantomData,
271        })
272    }
273}
274
275impl<P, K, V, F, G> Constraint<P> for CapacityConstraint<P, K, V, F, G>
276where
277    P: Phenotype,
278    K: Eq + Hash + Debug + Clone + Send + Sync,
279    V: Eq + Hash + Debug + Clone + Send + Sync,
280    F: Fn(&P) -> HashMap<V, Vec<K>> + Send + Sync + Debug,
281    G: Fn(&V) -> usize + Send + Sync + Debug,
282{
283    fn check(&self, phenotype: &P) -> Vec<ConstraintViolation> {
284        let assignments = (self.extractor)(phenotype);
285        let mut violations = Vec::new();
286
287        for (bin, items) in assignments.iter() {
288            let capacity = (self.capacity_fn)(bin);
289            if items.len() > capacity {
290                violations.push(ConstraintViolation::new(
291                    &self.name,
292                    format!(
293                        "Bin {:?} has {} items but capacity is {}",
294                        bin,
295                        items.len(),
296                        capacity
297                    ),
298                ));
299            }
300        }
301
302        violations
303    }
304
305    fn repair_with_rng(&self, phenotype: &mut P, rng: &mut RandomNumberGenerator) -> bool {
306        // This is a generic implementation that might not work for all phenotypes
307        // It relies on the phenotype's mutate method to potentially fix the capacity issue
308
309        // Check if there are any violations
310        let violations = self.check(phenotype);
311        if violations.is_empty() {
312            return false; // No violations to repair
313        }
314
315        // Try to repair by mutating the phenotype
316        phenotype.mutate(rng);
317
318        // Check if repair was successful
319        let new_violations = self.check(phenotype);
320        new_violations.is_empty()
321    }
322}
323
324/// Ensures that dependencies between elements are satisfied.
325///
326/// This constraint is useful for problems where some elements must come before
327/// others, such as scheduling or sequencing problems.
328#[derive(Debug, Clone)]
329pub struct DependencyConstraint<P, T, F>
330where
331    P: Phenotype,
332    T: Eq + Hash + Debug + Clone + Send + Sync,
333    F: Fn(&P) -> Vec<T> + Send + Sync + Debug,
334{
335    /// Name of the constraint for error messages
336    name: String,
337    /// Function to extract the sequence from the phenotype
338    extractor: F,
339    /// The set of dependencies (before, after) pairs
340    dependencies: Vec<(T, T)>,
341    /// Phantom data for the phenotype type
342    _marker: PhantomData<P>,
343}
344
345impl<P, T, F> DependencyConstraint<P, T, F>
346where
347    P: Phenotype,
348    T: Eq + Hash + Debug + Clone + Send + Sync,
349    F: Fn(&P) -> Vec<T> + Send + Sync + Debug,
350{
351    /// Creates a new dependency constraint with the given name, extractor function,
352    /// and dependencies.
353    ///
354    /// # Arguments
355    ///
356    /// * `name` - The name of the constraint for error messages.
357    /// * `extractor` - A function that extracts the sequence from the phenotype.
358    /// * `dependencies` - A vector of (before, after) pairs representing dependencies.
359    ///
360    /// # Returns
361    ///
362    /// A new dependency constraint, or an error if the name is empty or if the dependencies vector is empty.
363    pub fn new<S: Into<String>>(name: S, extractor: F, dependencies: Vec<(T, T)>) -> Result<Self> {
364        let name = name.into();
365        if name.is_empty() {
366            return Err(ConstraintError::EmptyName);
367        }
368        if dependencies.is_empty() {
369            return Err(ConstraintError::EmptyCollection(
370                "Dependencies vector".to_string(),
371            ));
372        }
373        Ok(Self {
374            name,
375            extractor,
376            dependencies,
377            _marker: PhantomData,
378        })
379    }
380}
381
382impl<P, T, F> Constraint<P> for DependencyConstraint<P, T, F>
383where
384    P: Phenotype,
385    T: Eq + Hash + Debug + Clone + Send + Sync,
386    F: Fn(&P) -> Vec<T> + Send + Sync + Debug,
387{
388    fn check(&self, phenotype: &P) -> Vec<ConstraintViolation> {
389        let sequence = (self.extractor)(phenotype);
390        let mut violations = Vec::new();
391
392        // Build a map of element to position
393        let mut positions = HashMap::new();
394        for (pos, element) in sequence.iter().enumerate() {
395            positions.insert(element, pos);
396        }
397
398        // Check each dependency
399        for (before, after) in &self.dependencies {
400            if let (Some(&before_pos), Some(&after_pos)) =
401                (positions.get(before), positions.get(after))
402            {
403                if before_pos >= after_pos {
404                    violations.push(ConstraintViolation::new(
405                        &self.name,
406                        format!(
407                            "Dependency violation: {:?} must come before {:?}",
408                            before, after
409                        ),
410                    ));
411                }
412            }
413        }
414
415        violations
416    }
417
418    fn repair_with_rng(&self, phenotype: &mut P, rng: &mut RandomNumberGenerator) -> bool {
419        // This is a generic implementation that might not work for all phenotypes
420        // It relies on the phenotype's mutate method to potentially fix the dependency issue
421
422        // Check if there are any violations
423        let violations = self.check(phenotype);
424        if violations.is_empty() {
425            return false; // No violations to repair
426        }
427
428        // Try to repair by mutating the phenotype
429        phenotype.mutate(rng);
430
431        // Check if repair was successful
432        let new_violations = self.check(phenotype);
433        new_violations.is_empty()
434    }
435}
436
437#[cfg(test)]
438mod tests {
439    use super::*;
440
441    // Test the constraint violation struct
442    #[test]
443    fn test_constraint_violation() {
444        let violation = ConstraintViolation::new("TestConstraint", "Test violation");
445        assert_eq!(violation.constraint_name(), "TestConstraint");
446        assert_eq!(violation.description(), "Test violation");
447        assert!(violation.severity().is_none());
448
449        let violation_with_severity =
450            ConstraintViolation::with_severity("TestConstraint", "Test violation", 2.5);
451        assert_eq!(violation_with_severity.constraint_name(), "TestConstraint");
452        assert_eq!(violation_with_severity.description(), "Test violation");
453        assert_eq!(violation_with_severity.severity(), Some(2.5));
454    }
455
456    // Test the constraint module documentation examples
457    #[test]
458    fn test_constraint_documentation_examples() {
459        // This test verifies that the examples in the module documentation compile
460        // and work as expected. It doesn't directly test the constraints themselves,
461        // but ensures that the API is usable as documented.
462
463        // Example of creating a constraint violation
464        let violation = ConstraintViolation::new("UniqueValues", "Duplicate value 2 at position 3");
465        assert_eq!(violation.constraint_name(), "UniqueValues");
466        assert_eq!(violation.description(), "Duplicate value 2 at position 3");
467
468        // Example of creating a constraint violation with severity
469        let violation = ConstraintViolation::with_severity(
470            "CapacityConstraint",
471            "Bin 1 exceeds capacity by 3 items",
472            3.0,
473        );
474        assert_eq!(violation.severity(), Some(3.0));
475
476        // Example of formatting a constraint violation
477        let violation = ConstraintViolation::new("TestConstraint", "Test violation");
478        let formatted = format!("{}", violation);
479        assert!(formatted.contains("TestConstraint"));
480        assert!(formatted.contains("Test violation"));
481    }
482
483    #[test]
484    fn test_empty_name_validation() {
485        // Test that empty names are rejected
486        let empty_name = "".to_string();
487        let valid_name = "Test".to_string();
488
489        // Check that empty names are rejected
490        assert!(empty_name.is_empty());
491        assert!(!valid_name.is_empty());
492    }
493
494    #[test]
495    fn test_empty_collection_validation() {
496        // Test that empty collections are rejected
497        let empty_keys: HashSet<i32> = HashSet::new();
498        let valid_keys: HashSet<i32> = [1, 2, 3].iter().cloned().collect();
499
500        let empty_deps: Vec<(i32, i32)> = Vec::new();
501        let valid_deps: Vec<(i32, i32)> = vec![(1, 2), (2, 3)];
502
503        // Check that empty collections are rejected
504        assert!(empty_keys.is_empty());
505        assert!(!valid_keys.is_empty());
506
507        assert!(empty_deps.is_empty());
508        assert!(!valid_deps.is_empty());
509    }
510}
genalg/constraints/combinatorial.rs

genalg/constraints/
combinatorial.rs
