problemreductions/
lib.rs

1//! # Problem Reductions
2//!
3//! NP-hard problem definitions and reductions.
4//! See the [user guide](https://codingthrust.github.io/problem-reductions/) for tutorials and examples.
5//!
6//! ## API Overview
7//!
8//! | Module | Purpose |
9//! |--------|---------|
10//! | [`models`] | Problem types — [`graph`](models::graph), [`formula`](models::formula), [`set`](models::set), [`algebraic`](models::algebraic), [`misc`](models::misc) |
11//! | [`rules`] | Reduction rules, [`ReductionGraph`](rules::ReductionGraph) for path search |
12//! | [`solvers`] | [`BruteForce`] and [`ILPSolver`](solvers::ILPSolver) |
13//! | [`topology`] | Graph types — [`SimpleGraph`](topology::SimpleGraph), [`UnitDiskGraph`](topology::UnitDiskGraph), etc. |
14//! | [`traits`] | Core traits — [`Problem`] |
15//! | [`types`] | [`Max`], [`Min`], [`Extremum`], [`ExtremumSense`], [`ProblemParameters`], [`WeightElement`] |
16//! | [`variant`] | Variant parameter system for problem type parameterization |
17//!
18//! Use [`prelude`] for convenient imports.
19
20extern crate self as problemreductions;
21
22pub(crate) mod big_o;
23pub mod config;
24pub mod error;
25#[cfg(feature = "example-db")]
26pub mod example_db;
27pub mod export;
28pub mod expr;
29// Growth is an explicit terminal projection for complexity display. Exact and certified
30// parameter propagation never re-enters this domain.
31pub mod growth;
32pub mod io;
33pub mod models;
34pub mod parameters;
35pub mod random;
36pub mod registry;
37pub mod rules;
38pub mod solvers;
39pub mod topology;
40pub mod traits;
41#[allow(dead_code)]
42pub(crate) mod truth_table;
43pub mod types;
44pub mod variant;
45
46/// Prelude module for convenient imports.
47pub mod prelude {
48    // Problem types
49    pub use crate::models::algebraic::{
50        AlgebraicEquationsOverGF2, ConsecutiveOnesMatrixAugmentation,
51        MinimumWeightSolutionToLinearEquations, QuadraticAssignment, QuadraticCongruences,
52        SimultaneousIncongruences, SparseMatrixCompression, BMF, QUBO,
53    };
54    pub use crate::models::formula::{
55        CNFClause, CircuitSAT, KSatisfiability, Maximum2Satisfiability, NAESatisfiability,
56        NonTautology, OneInThreeSatisfiability, Planar3Satisfiability, QuantifiedBooleanFormulas,
57        Satisfiability,
58    };
59    pub use crate::models::graph::{
60        AcyclicPartition, BalancedCompleteBipartiteSubgraph, BicliqueCover,
61        BiconnectivityAugmentation, BottleneckTravelingSalesman, BoundedComponentSpanningForest,
62        DegreeConstrainedSpanningTree, DirectedTwoCommodityIntegralFlow, DisjointConnectingPaths,
63        GeneralizedHex, GraphPartitioning, HamiltonianCircuit, HamiltonianPath,
64        HamiltonianPathBetweenTwoVertices, IntegralFlowBundles, IntegralFlowHomologousArcs,
65        IntegralFlowWithMultipliers, IsomorphicSpanningTree, KClique, Kernel, KthBestSpanningTree,
66        LengthBoundedDisjointPaths, LongestPath, MixedChinesePostman, SpinGlass, SteinerTree,
67        StrongConnectivityAugmentation, SubgraphIsomorphism,
68    };
69    pub use crate::models::graph::{
70        KColoring, LongestCircuit, MaxCut, MaximalIS, MaximumClique, MaximumIndependentSet,
71        MaximumLeafSpanningTree, MaximumMatching, MinMaxMulticenter, MinimumCutIntoBoundedSets,
72        MinimumDominatingSet, MinimumDummyActivitiesPert, MinimumFeedbackArcSet,
73        MinimumFeedbackVertexSet, MinimumGeometricConnectedDominatingSet, MinimumGraphBandwidth,
74        MinimumMultiwayCut, MinimumSumMulticenter, MinimumVertexCover, MonochromaticTriangle,
75        MultipleChoiceBranching, MultipleCopyFileAllocation, OptimalLinearArrangement,
76        PartialFeedbackEdgeSet, PartitionIntoCliques, PartitionIntoPathsOfLength2,
77        PartitionIntoTriangles, PathConstrainedNetworkFlow, RootedTreeArrangement, RuralPostman,
78        ShortestWeightConstrainedPath, SteinerTreeInGraphs, TravelingSalesman,
79        UndirectedFlowLowerBounds, UndirectedTwoCommodityIntegralFlow,
80    };
81    pub use crate::models::misc::{
82        AdditionalKey, BinPacking, BoyceCoddNormalFormViolation, CapacityAssignment, CbqRelation,
83        ConjunctiveBooleanQuery, ConjunctiveQueryFoldability, ConsistencyOfDatabaseFrequencyTables,
84        CosineProductIntegration, EnsembleComputation, ExpectedRetrievalCost, Factoring,
85        FlowShopScheduling, GroupingBySwapping, IntegerExpressionMembership, JobShopScheduling,
86        Knapsack, LongestCommonSubsequence, MinimumTardinessSequencing, MultiprocessorScheduling,
87        OpenShopScheduling, PaintShop, Partition, PreemptiveScheduling, ProductionPlanning,
88        QueryArg, RectilinearPictureCompression, ResourceConstrainedScheduling,
89        SchedulingWithIndividualDeadlines, SequencingToMinimizeMaximumCumulativeCost,
90        SequencingToMinimizeTardyTaskWeight, SequencingToMinimizeWeightedCompletionTime,
91        SequencingToMinimizeWeightedTardiness, SequencingWithDeadlinesAndSetUpTimes,
92        SequencingWithReleaseTimesAndDeadlines, SequencingWithinIntervals,
93        ShortestCommonSupersequence, StackerCrane, StaffScheduling, StringToStringCorrection,
94        SubsetProduct, SubsetSum, SumOfSquaresPartition, Term, ThreePartition, TimetableDesign,
95    };
96    pub use crate::models::set::{
97        ComparativeContainment, ConsecutiveSets, ExactCoverBy3Sets, IntegerKnapsack,
98        MaximumSetPacking, MinimumCardinalityKey, MinimumHittingSet, MinimumSetCovering,
99        PrimeAttributeName, RootedTreeStorageAssignment, SetBasis, SetSplitting,
100    };
101
102    // Core traits
103    pub use crate::rules::{ReduceTo, ReductionResult};
104    pub use crate::solvers::BruteForce;
105    pub use crate::traits::Problem;
106
107    // Types
108    pub use crate::error::{ProblemError, Result};
109    pub use crate::types::{
110        And, Extremum, ExtremumSense, Max, Min, One, Or, ProblemParameters, Sum,
111    };
112}
113
114// Re-export commonly used items at crate root
115pub use big_o::big_o_normal_form;
116pub use error::{ProblemError, Result};
117pub use expr::{
118    evaluate_approximate, ApproximationError, AsymptoticAnalysisError, Expr, ParseError,
119};
120pub use growth::Growth;
121pub use registry::{ComplexityClass, ProblemInfo};
122pub use solvers::BruteForce;
123pub use traits::Problem;
124pub use types::{
125    And, Extremum, ExtremumSense, Max, Min, NumericSize, One, Or, ProblemParameters, Sum,
126    WeightElement,
127};
128
129// Re-export proc macros for reduction registration and variant declaration
130pub use problemreductions_macros::{declare_variants, reduction, register_brute_force, CreateSpec};
131
132// Re-export inventory so `declare_variants!` can use `$crate::inventory::submit!`
133pub use inventory;
134
135#[cfg(all(test, feature = "example-db"))]
136#[path = "unit_tests/symbolic_parameter_contracts.rs"]
137mod symbolic_parameter_contracts;
138#[cfg(test)]
139#[path = "unit_tests/graph_models.rs"]
140mod test_graph_models;
141#[cfg(test)]
142#[path = "unit_tests/prelude.rs"]
143mod test_prelude;
144#[cfg(test)]
145#[path = "unit_tests/problem_parameters.rs"]
146mod test_problem_parameters;
147#[cfg(test)]
148#[path = "unit_tests/property.rs"]
149mod test_property;
150#[cfg(test)]
151#[path = "unit_tests/reduction_graph.rs"]
152mod test_reduction_graph;
153#[cfg(test)]
154#[path = "unit_tests/unitdiskmapping_algorithms/mod.rs"]
155mod test_unitdiskmapping_algorithms;
problemreductions/lib.rs

problemreductions/
lib.rs
