problemreductions/rules/
registry.rs

1//! Automatic reduction registration via inventory.
2
3use crate::polynomial::Polynomial;
4use crate::types::ProblemSize;
5
6/// Overhead specification for a reduction.
7#[derive(Clone, Debug, Default)]
8pub struct ReductionOverhead {
9    /// Output size as polynomials of input size variables.
10    /// Each entry is (output_field_name, polynomial).
11    pub output_size: Vec<(&'static str, Polynomial)>,
12}
13
14impl ReductionOverhead {
15    pub fn new(output_size: Vec<(&'static str, Polynomial)>) -> Self {
16        Self { output_size }
17    }
18
19    /// Evaluate output size given input size.
20    ///
21    /// Uses `round()` for the f64 to usize conversion because polynomial coefficients
22    /// are typically integers (1, 2, 3, 7, 21, etc.) and any fractional results come
23    /// from floating-point arithmetic imprecision, not intentional fractions.
24    /// For problem sizes, rounding to nearest integer is the most intuitive behavior.
25    pub fn evaluate_output_size(&self, input: &ProblemSize) -> ProblemSize {
26        let fields: Vec<_> = self.output_size.iter()
27            .map(|(name, poly)| (*name, poly.evaluate(input).round() as usize))
28            .collect();
29        ProblemSize::new(fields)
30    }
31}
32
33
34/// A registered reduction entry for static inventory registration.
35/// Uses function pointer to lazily create the overhead (avoids static allocation issues).
36pub struct ReductionEntry {
37    /// Base name of source problem (e.g., "IndependentSet").
38    pub source_name: &'static str,
39    /// Base name of target problem (e.g., "VertexCovering").
40    pub target_name: &'static str,
41    /// Graph type of source problem (e.g., "SimpleGraph").
42    pub source_graph: &'static str,
43    /// Graph type of target problem.
44    pub target_graph: &'static str,
45    /// Function to create overhead information (lazy evaluation for static context).
46    pub overhead_fn: fn() -> ReductionOverhead,
47}
48
49impl ReductionEntry {
50    /// Get the overhead by calling the function.
51    pub fn overhead(&self) -> ReductionOverhead {
52        (self.overhead_fn)()
53    }
54}
55
56impl std::fmt::Debug for ReductionEntry {
57    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
58        f.debug_struct("ReductionEntry")
59            .field("source_name", &self.source_name)
60            .field("target_name", &self.target_name)
61            .field("source_graph", &self.source_graph)
62            .field("target_graph", &self.target_graph)
63            .field("overhead", &self.overhead())
64            .finish()
65    }
66}
67
68inventory::collect!(ReductionEntry);
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73    use crate::poly;
74
75    #[test]
76    fn test_reduction_overhead_evaluate() {
77        let overhead = ReductionOverhead::new(vec![
78            ("n", poly!(3 * m)),
79            ("m", poly!(m^2)),
80        ]);
81
82        let input = ProblemSize::new(vec![("m", 4)]);
83        let output = overhead.evaluate_output_size(&input);
84
85        assert_eq!(output.get("n"), Some(12));  // 3 * 4
86        assert_eq!(output.get("m"), Some(16));  // 4^2
87    }
88
89    #[test]
90    fn test_reduction_overhead_default() {
91        let overhead = ReductionOverhead::default();
92        assert!(overhead.output_size.is_empty());
93    }
94
95    #[test]
96    fn test_reduction_entry_overhead() {
97        let entry = ReductionEntry {
98            source_name: "TestSource",
99            target_name: "TestTarget",
100            source_graph: "SimpleGraph",
101            target_graph: "SimpleGraph",
102            overhead_fn: || ReductionOverhead::new(vec![("n", poly!(2 * n))]),
103        };
104
105        let overhead = entry.overhead();
106        let input = ProblemSize::new(vec![("n", 5)]);
107        let output = overhead.evaluate_output_size(&input);
108        assert_eq!(output.get("n"), Some(10));
109    }
110
111    #[test]
112    fn test_reduction_entry_debug() {
113        let entry = ReductionEntry {
114            source_name: "A",
115            target_name: "B",
116            source_graph: "SimpleGraph",
117            target_graph: "SimpleGraph",
118            overhead_fn: || ReductionOverhead::default(),
119        };
120
121        let debug_str = format!("{:?}", entry);
122        assert!(debug_str.contains("A"));
123        assert!(debug_str.contains("B"));
124    }
125
126    #[test]
127    fn test_reduction_entries_registered() {
128        let entries: Vec<_> = inventory::iter::<ReductionEntry>().collect();
129
130        // Should have at least some registered reductions
131        assert!(entries.len() >= 10);
132
133        // Check specific reductions exist
134        assert!(entries
135            .iter()
136            .any(|e| e.source_name == "IndependentSet" && e.target_name == "VertexCovering"));
137    }
138}
problemreductions/rules/registry.rs

problemreductions/rules/
registry.rs
