problemreductions/
lib.rs

1//! # Problem Reductions
2//!
3//! A Rust library for reducing NP-hard problems.
4//!
5//! This library provides implementations of various NP-hard computational problems
6//! and reduction rules between them. It is designed for algorithm research,
7//! education, and quantum optimization studies.
8//!
9//! ## Features
10//!
11//! - **Problem Definitions**: Implementations of 18+ NP-hard problems
12//! - **Reduction Rules**: Transform problems into equivalent problems
13//! - **Solvers**: Brute-force solver for testing and verification
14//! - **Validation**: Utilities to verify solution validity
15//!
16//! ## Example
17//!
18//! ```rust
19//! use problemreductions::prelude::*;
20//! use problemreductions::models::graph::IndependentSet;
21//!
22//! // Create an Independent Set problem on a triangle graph
23//! let problem = IndependentSet::<i32>::new(3, vec![(0, 1), (1, 2), (0, 2)]);
24//!
25//! // Solve with brute force
26//! let solver = BruteForce::new();
27//! let solutions = solver.find_best(&problem);
28//!
29//! // Maximum independent set in a triangle has size 1
30//! assert!(solutions.iter().all(|s| s.iter().sum::<usize>() == 1));
31//! ```
32//!
33//! ## Problem Categories
34//!
35//! ### Satisfiability
36//! - SAT: Boolean satisfiability with CNF clauses
37//! - K-SAT: SAT restricted to k-literal clauses
38//! - CircuitSAT: Boolean circuit satisfiability
39//! - Factoring: Integer factorization
40//!
41//! ### Graph Problems
42//! - IndependentSet: Maximum weight independent set
43//! - MaximalIS: Maximal independent set
44//! - VertexCovering: Minimum weight vertex cover
45//! - DominatingSet: Minimum dominating set
46//! - Coloring: K-vertex coloring
47//!
48//! ### Set Problems
49//! - SetCovering: Minimum weight set cover
50//! - SetPacking: Maximum weight set packing
51//!
52//! ### Optimization Problems
53//! - MaxCut: Maximum cut on weighted graphs
54//! - SpinGlass: Ising model Hamiltonian
55//! - QUBO: Quadratic unconstrained binary optimization
56//! - Matching: Maximum weight matching
57//!
58//! ### Specialized Problems
59//! - Paintshop: Minimize color switches
60//! - BicliqueCover: Biclique cover on bipartite graphs
61//! - BMF: Boolean matrix factorization
62
63pub mod config;
64pub mod error;
65pub mod graph_types;
66pub mod io;
67pub mod models;
68pub mod polynomial;
69pub mod registry;
70pub mod rules;
71pub mod solvers;
72pub mod testing;
73pub mod topology;
74pub mod traits;
75pub mod truth_table;
76pub mod types;
77
78/// Prelude module for convenient imports.
79pub mod prelude {
80    pub use crate::config::{
81        bits_to_config, config_to_bits, config_to_index, index_to_config, ConfigIterator,
82    };
83    pub use crate::error::{ProblemError, Result};
84    pub use crate::models::graph::{
85        Coloring, DominatingSet, IndependentSet, Matching, MaxCut, MaximalIS, VertexCovering,
86    };
87    pub use crate::models::optimization::{
88        Comparison, LinearConstraint, ObjectiveSense, SpinGlass, VarBounds, ILP, QUBO,
89    };
90    pub use crate::models::satisfiability::{CNFClause, KSatisfiability, Satisfiability};
91    pub use crate::models::set::{SetCovering, SetPacking};
92    pub use crate::models::specialized::{BicliqueCover, CircuitSAT, Factoring, PaintShop, BMF};
93    pub use crate::registry::{
94        ComplexityClass, GraphSubcategory, ProblemCategory, ProblemInfo, ProblemMetadata,
95    };
96    pub use crate::solvers::{BruteForce, Solver};
97    pub use crate::rules::{ReduceTo, ReductionResult};
98    pub use crate::traits::{csp_solution_size, ConstraintSatisfactionProblem, Problem};
99    pub use crate::types::{
100        EnergyMode, LocalConstraint, LocalSolutionSize, NumericWeight, ProblemSize, SolutionSize,
101    };
102}
103
104// Re-export commonly used items at crate root
105pub use error::{ProblemError, Result};
106pub use registry::{ComplexityClass, ProblemCategory, ProblemInfo};
107pub use solvers::{BruteForce, Solver};
108pub use traits::{ConstraintSatisfactionProblem, Problem};
109pub use types::{EnergyMode, LocalConstraint, LocalSolutionSize, ProblemSize, SolutionSize};
problemreductions/lib.rs

problemreductions/
lib.rs
