problemreductions/registry/
category.rs

1//! Problem category types for classification and discovery.
2//!
3//! This module defines a hierarchical category system for NP-complete problems.
4//! Each problem belongs to a top-level category (e.g., Graph, Satisfiability)
5//! and a subcategory (e.g., Independent, Coloring).
6//!
7//! # Category Hierarchy
8//!
9//! ```text
10//! ProblemCategory
11//! ├── Graph
12//! │   ├── Coloring      (3-Coloring, Chromatic Number)
13//! │   ├── Covering      (Vertex Cover, Dominating Set)
14//! │   ├── Independent   (Independent Set, Clique)
15//! │   ├── Paths         (Hamiltonian Path, TSP)
16//! │   ├── Structure     (Graph Partition)
17//! │   ├── Trees         (Steiner Tree)
18//! │   └── Matching      (3D Matching)
19//! ├── Satisfiability
20//! │   ├── Sat           (SAT, 3-SAT, Max-SAT)
21//! │   ├── Circuit       (Circuit SAT)
22//! │   └── Qbf           (QBF)
23//! ├── Set
24//! │   ├── Covering      (Set Cover, Exact Cover)
25//! │   ├── Packing       (Bin Packing, Knapsack)
26//! │   ├── Partition     (Partition, Subset Sum)
27//! │   └── Matching      (Hitting Set)
28//! ├── Optimization
29//! │   ├── Quadratic     (QUBO, Max-Cut)
30//! │   ├── Linear        (ILP)
31//! │   └── Constraint    (CSP)
32//! ├── Scheduling
33//! │   ├── Machine       (Job Shop)
34//! │   ├── Sequencing    (Sequencing)
35//! │   └── Resource      (Resource Allocation)
36//! ├── Network
37//! │   ├── Flow          (Network Flow)
38//! │   ├── Routing       (Routing)
39//! │   └── Connectivity  (k-Connectivity)
40//! ├── String
41//! │   ├── Sequence      (Shortest Superstring)
42//! │   ├── Matching      (String Matching)
43//! │   └── Compression   (Grammar Compression)
44//! └── Specialized
45//!     ├── Geometry      (Protein Folding)
46//!     ├── Number        (Factoring)
47//!     ├── Game          (Game Theory)
48//!     └── Other
49//! ```
50
51use serde::{Deserialize, Serialize};
52use std::fmt;
53
54/// Top-level problem category.
55///
56/// Problems are organized into a two-level hierarchy: category and subcategory.
57/// Use [`path()`](ProblemCategory::path) to get the full path (e.g., "graph/independent").
58///
59/// # Example
60///
61/// ```rust
62/// use problemreductions::registry::{ProblemCategory, GraphSubcategory};
63///
64/// let cat = ProblemCategory::Graph(GraphSubcategory::Independent);
65/// assert_eq!(cat.name(), "graph");
66/// assert_eq!(cat.subcategory_name(), "independent");
67/// assert_eq!(cat.path(), "graph/independent");
68/// ```
69#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
70pub enum ProblemCategory {
71    /// Graph-based problems (coloring, covering, paths, etc.)
72    Graph(GraphSubcategory),
73    /// Boolean satisfiability problems
74    Satisfiability(SatisfiabilitySubcategory),
75    /// Set-based problems (covering, packing, partition)
76    Set(SetSubcategory),
77    /// Optimization problems (quadratic, linear, constraint)
78    Optimization(OptimizationSubcategory),
79    /// Scheduling and resource allocation
80    Scheduling(SchedulingSubcategory),
81    /// Network flow and routing problems
82    Network(NetworkSubcategory),
83    /// String and sequence problems
84    String(StringSubcategory),
85    /// Specialized domain-specific problems
86    Specialized(SpecializedSubcategory),
87}
88
89impl ProblemCategory {
90    /// Get the top-level category name.
91    pub fn name(&self) -> &'static str {
92        match self {
93            ProblemCategory::Graph(_) => "graph",
94            ProblemCategory::Satisfiability(_) => "satisfiability",
95            ProblemCategory::Set(_) => "set",
96            ProblemCategory::Optimization(_) => "optimization",
97            ProblemCategory::Scheduling(_) => "scheduling",
98            ProblemCategory::Network(_) => "network",
99            ProblemCategory::String(_) => "string",
100            ProblemCategory::Specialized(_) => "specialized",
101        }
102    }
103
104    /// Get the subcategory name.
105    pub fn subcategory_name(&self) -> &'static str {
106        match self {
107            ProblemCategory::Graph(sub) => sub.name(),
108            ProblemCategory::Satisfiability(sub) => sub.name(),
109            ProblemCategory::Set(sub) => sub.name(),
110            ProblemCategory::Optimization(sub) => sub.name(),
111            ProblemCategory::Scheduling(sub) => sub.name(),
112            ProblemCategory::Network(sub) => sub.name(),
113            ProblemCategory::String(sub) => sub.name(),
114            ProblemCategory::Specialized(sub) => sub.name(),
115        }
116    }
117
118    /// Get the full path as "category/subcategory".
119    pub fn path(&self) -> String {
120        format!("{}/{}", self.name(), self.subcategory_name())
121    }
122}
123
124impl fmt::Display for ProblemCategory {
125    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
126        write!(f, "{}", self.path())
127    }
128}
129
130/// Graph problem subcategories.
131#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
132pub enum GraphSubcategory {
133    /// Vertex/edge coloring problems
134    Coloring,
135    /// Vertex/edge covering problems
136    Covering,
137    /// Independent set and clique problems
138    Independent,
139    /// Path and cycle problems (Hamiltonian, TSP)
140    Paths,
141    /// Graph structure and partitioning
142    Structure,
143    /// Tree problems (Steiner, spanning)
144    Trees,
145    /// Matching problems
146    Matching,
147}
148
149impl GraphSubcategory {
150    /// Get the subcategory name.
151    pub fn name(&self) -> &'static str {
152        match self {
153            GraphSubcategory::Coloring => "coloring",
154            GraphSubcategory::Covering => "covering",
155            GraphSubcategory::Independent => "independent",
156            GraphSubcategory::Paths => "paths",
157            GraphSubcategory::Structure => "structure",
158            GraphSubcategory::Trees => "trees",
159            GraphSubcategory::Matching => "matching",
160        }
161    }
162}
163
164/// Satisfiability problem subcategories.
165#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
166pub enum SatisfiabilitySubcategory {
167    /// SAT and variants (3-SAT, Max-SAT)
168    Sat,
169    /// Circuit satisfiability
170    Circuit,
171    /// Quantified Boolean formulas
172    Qbf,
173}
174
175impl SatisfiabilitySubcategory {
176    /// Get the subcategory name.
177    pub fn name(&self) -> &'static str {
178        match self {
179            SatisfiabilitySubcategory::Sat => "sat",
180            SatisfiabilitySubcategory::Circuit => "circuit",
181            SatisfiabilitySubcategory::Qbf => "qbf",
182        }
183    }
184}
185
186/// Set problem subcategories.
187#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
188pub enum SetSubcategory {
189    /// Set covering and exact cover
190    Covering,
191    /// Set packing, bin packing, knapsack
192    Packing,
193    /// Partition and subset sum
194    Partition,
195    /// Set splitting and hitting set
196    Matching,
197}
198
199impl SetSubcategory {
200    /// Get the subcategory name.
201    pub fn name(&self) -> &'static str {
202        match self {
203            SetSubcategory::Covering => "covering",
204            SetSubcategory::Packing => "packing",
205            SetSubcategory::Partition => "partition",
206            SetSubcategory::Matching => "matching",
207        }
208    }
209}
210
211/// Optimization problem subcategories.
212#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
213pub enum OptimizationSubcategory {
214    /// Quadratic optimization (QUBO, Max-Cut, Ising)
215    Quadratic,
216    /// Linear and integer programming
217    Linear,
218    /// Constraint-based optimization
219    Constraint,
220}
221
222impl OptimizationSubcategory {
223    /// Get the subcategory name.
224    pub fn name(&self) -> &'static str {
225        match self {
226            OptimizationSubcategory::Quadratic => "quadratic",
227            OptimizationSubcategory::Linear => "linear",
228            OptimizationSubcategory::Constraint => "constraint",
229        }
230    }
231}
232
233/// Scheduling problem subcategories.
234#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
235pub enum SchedulingSubcategory {
236    /// Multiprocessor and machine scheduling
237    Machine,
238    /// Sequencing with constraints
239    Sequencing,
240    /// Resource allocation
241    Resource,
242}
243
244impl SchedulingSubcategory {
245    /// Get the subcategory name.
246    pub fn name(&self) -> &'static str {
247        match self {
248            SchedulingSubcategory::Machine => "machine",
249            SchedulingSubcategory::Sequencing => "sequencing",
250            SchedulingSubcategory::Resource => "resource",
251        }
252    }
253}
254
255/// Network problem subcategories.
256#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
257pub enum NetworkSubcategory {
258    /// Network flow problems
259    Flow,
260    /// Routing and path problems
261    Routing,
262    /// Connectivity problems
263    Connectivity,
264}
265
266impl NetworkSubcategory {
267    /// Get the subcategory name.
268    pub fn name(&self) -> &'static str {
269        match self {
270            NetworkSubcategory::Flow => "flow",
271            NetworkSubcategory::Routing => "routing",
272            NetworkSubcategory::Connectivity => "connectivity",
273        }
274    }
275}
276
277/// String problem subcategories.
278#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
279pub enum StringSubcategory {
280    /// Sequence problems (superstring, subsequence)
281    Sequence,
282    /// String matching
283    Matching,
284    /// Compression problems
285    Compression,
286}
287
288impl StringSubcategory {
289    /// Get the subcategory name.
290    pub fn name(&self) -> &'static str {
291        match self {
292            StringSubcategory::Sequence => "sequence",
293            StringSubcategory::Matching => "matching",
294            StringSubcategory::Compression => "compression",
295        }
296    }
297}
298
299/// Specialized problem subcategories.
300#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
301pub enum SpecializedSubcategory {
302    /// Geometric problems
303    Geometry,
304    /// Number-theoretic problems
305    Number,
306    /// Game-theoretic problems
307    Game,
308    /// Other specialized problems
309    Other,
310}
311
312impl SpecializedSubcategory {
313    /// Get the subcategory name.
314    pub fn name(&self) -> &'static str {
315        match self {
316            SpecializedSubcategory::Geometry => "geometry",
317            SpecializedSubcategory::Number => "number",
318            SpecializedSubcategory::Game => "game",
319            SpecializedSubcategory::Other => "other",
320        }
321    }
322}
323
324#[cfg(test)]
325mod tests {
326    use super::*;
327
328    #[test]
329    fn test_category_path() {
330        let cat = ProblemCategory::Graph(GraphSubcategory::Independent);
331        assert_eq!(cat.path(), "graph/independent");
332        assert_eq!(cat.name(), "graph");
333        assert_eq!(cat.subcategory_name(), "independent");
334    }
335
336    #[test]
337    fn test_category_display() {
338        let cat = ProblemCategory::Satisfiability(SatisfiabilitySubcategory::Sat);
339        assert_eq!(format!("{}", cat), "satisfiability/sat");
340    }
341
342    #[test]
343    fn test_all_subcategories() {
344        // Graph
345        assert_eq!(GraphSubcategory::Coloring.name(), "coloring");
346        assert_eq!(GraphSubcategory::Covering.name(), "covering");
347        assert_eq!(GraphSubcategory::Independent.name(), "independent");
348        assert_eq!(GraphSubcategory::Paths.name(), "paths");
349        assert_eq!(GraphSubcategory::Structure.name(), "structure");
350        assert_eq!(GraphSubcategory::Trees.name(), "trees");
351        assert_eq!(GraphSubcategory::Matching.name(), "matching");
352
353        // Satisfiability
354        assert_eq!(SatisfiabilitySubcategory::Sat.name(), "sat");
355        assert_eq!(SatisfiabilitySubcategory::Circuit.name(), "circuit");
356        assert_eq!(SatisfiabilitySubcategory::Qbf.name(), "qbf");
357
358        // Set
359        assert_eq!(SetSubcategory::Covering.name(), "covering");
360        assert_eq!(SetSubcategory::Packing.name(), "packing");
361        assert_eq!(SetSubcategory::Partition.name(), "partition");
362        assert_eq!(SetSubcategory::Matching.name(), "matching");
363
364        // Optimization
365        assert_eq!(OptimizationSubcategory::Quadratic.name(), "quadratic");
366        assert_eq!(OptimizationSubcategory::Linear.name(), "linear");
367        assert_eq!(OptimizationSubcategory::Constraint.name(), "constraint");
368
369        // Scheduling
370        assert_eq!(SchedulingSubcategory::Machine.name(), "machine");
371        assert_eq!(SchedulingSubcategory::Sequencing.name(), "sequencing");
372        assert_eq!(SchedulingSubcategory::Resource.name(), "resource");
373
374        // Network
375        assert_eq!(NetworkSubcategory::Flow.name(), "flow");
376        assert_eq!(NetworkSubcategory::Routing.name(), "routing");
377        assert_eq!(NetworkSubcategory::Connectivity.name(), "connectivity");
378
379        // String
380        assert_eq!(StringSubcategory::Sequence.name(), "sequence");
381        assert_eq!(StringSubcategory::Matching.name(), "matching");
382        assert_eq!(StringSubcategory::Compression.name(), "compression");
383
384        // Specialized
385        assert_eq!(SpecializedSubcategory::Geometry.name(), "geometry");
386        assert_eq!(SpecializedSubcategory::Number.name(), "number");
387        assert_eq!(SpecializedSubcategory::Game.name(), "game");
388        assert_eq!(SpecializedSubcategory::Other.name(), "other");
389    }
390}
problemreductions/registry/category.rs

problemreductions/registry/
category.rs
