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`], [`ProblemSize`], [`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(crate) mod canonical;
24pub mod config;
25pub mod error;
26#[cfg(feature = "example-db")]
27pub mod example_db;
28pub mod export;
29pub(crate) mod expr;
30pub mod io;
31pub mod models;
32pub mod registry;
33pub mod rules;
34pub mod solvers;
35pub mod topology;
36pub mod traits;
37#[allow(dead_code)]
38pub(crate) mod truth_table;
39pub mod types;
40pub mod variant;
41
42/// Prelude module for convenient imports.
43pub mod prelude {
44    // Problem types
45    pub use crate::models::algebraic::{
46        AlgebraicEquationsOverGF2, ConsecutiveOnesMatrixAugmentation,
47        MinimumWeightSolutionToLinearEquations, QuadraticAssignment, QuadraticCongruences,
48        SimultaneousIncongruences, SparseMatrixCompression, BMF, QUBO,
49    };
50    pub use crate::models::formula::{
51        CNFClause, CircuitSAT, KSatisfiability, Maximum2Satisfiability, NAESatisfiability,
52        NonTautology, OneInThreeSatisfiability, Planar3Satisfiability, QuantifiedBooleanFormulas,
53        Satisfiability,
54    };
55    pub use crate::models::graph::{
56        AcyclicPartition, BalancedCompleteBipartiteSubgraph, BicliqueCover,
57        BiconnectivityAugmentation, BottleneckTravelingSalesman, BoundedComponentSpanningForest,
58        DegreeConstrainedSpanningTree, DirectedTwoCommodityIntegralFlow, DisjointConnectingPaths,
59        GeneralizedHex, GraphPartitioning, HamiltonianCircuit, HamiltonianPath,
60        HamiltonianPathBetweenTwoVertices, IntegralFlowBundles, IntegralFlowHomologousArcs,
61        IntegralFlowWithMultipliers, IsomorphicSpanningTree, KClique, Kernel, KthBestSpanningTree,
62        LengthBoundedDisjointPaths, LongestPath, MixedChinesePostman, SpinGlass, SteinerTree,
63        StrongConnectivityAugmentation, SubgraphIsomorphism,
64    };
65    pub use crate::models::graph::{
66        KColoring, LongestCircuit, MaxCut, MaximalIS, MaximumClique, MaximumIndependentSet,
67        MaximumLeafSpanningTree, MaximumMatching, MinMaxMulticenter, MinimumCutIntoBoundedSets,
68        MinimumDominatingSet, MinimumDummyActivitiesPert, MinimumFeedbackArcSet,
69        MinimumFeedbackVertexSet, MinimumGeometricConnectedDominatingSet, MinimumGraphBandwidth,
70        MinimumMultiwayCut, MinimumSumMulticenter, MinimumVertexCover, MonochromaticTriangle,
71        MultipleChoiceBranching, MultipleCopyFileAllocation, OptimalLinearArrangement,
72        PartialFeedbackEdgeSet, PartitionIntoCliques, PartitionIntoPathsOfLength2,
73        PartitionIntoTriangles, PathConstrainedNetworkFlow, RootedTreeArrangement, RuralPostman,
74        ShortestWeightConstrainedPath, SteinerTreeInGraphs, TravelingSalesman,
75        UndirectedFlowLowerBounds, UndirectedTwoCommodityIntegralFlow,
76    };
77    pub use crate::models::misc::{
78        AdditionalKey, BinPacking, BoyceCoddNormalFormViolation, CapacityAssignment, CbqRelation,
79        ConjunctiveBooleanQuery, ConjunctiveQueryFoldability, ConsistencyOfDatabaseFrequencyTables,
80        CosineProductIntegration, EnsembleComputation, ExpectedRetrievalCost, Factoring,
81        FlowShopScheduling, GroupingBySwapping, IntegerExpressionMembership, JobShopScheduling,
82        Knapsack, LongestCommonSubsequence, MinimumTardinessSequencing, MultiprocessorScheduling,
83        OpenShopScheduling, PaintShop, Partition, PreemptiveScheduling, ProductionPlanning,
84        QueryArg, RectilinearPictureCompression, ResourceConstrainedScheduling,
85        SchedulingWithIndividualDeadlines, SequencingToMinimizeMaximumCumulativeCost,
86        SequencingToMinimizeTardyTaskWeight, SequencingToMinimizeWeightedCompletionTime,
87        SequencingToMinimizeWeightedTardiness, SequencingWithDeadlinesAndSetUpTimes,
88        SequencingWithReleaseTimesAndDeadlines, SequencingWithinIntervals,
89        ShortestCommonSupersequence, StackerCrane, StaffScheduling, StringToStringCorrection,
90        SubsetProduct, SubsetSum, SumOfSquaresPartition, Term, ThreePartition, TimetableDesign,
91    };
92    pub use crate::models::set::{
93        ComparativeContainment, ConsecutiveSets, ExactCoverBy3Sets, IntegerKnapsack,
94        MaximumSetPacking, MinimumCardinalityKey, MinimumHittingSet, MinimumSetCovering,
95        PrimeAttributeName, RootedTreeStorageAssignment, SetBasis, SetSplitting,
96        ThreeMatroidIntersection,
97    };
98
99    // Core traits
100    pub use crate::rules::{ReduceTo, ReductionResult};
101    pub use crate::solvers::{BruteForce, Solver};
102    pub use crate::traits::Problem;
103
104    // Types
105    pub use crate::error::{ProblemError, Result};
106    pub use crate::types::{
107        And, Extremum, ExtremumSense, Max, Min, One, Or, ProblemSize, Sum, Unweighted,
108    };
109}
110
111// Re-export commonly used items at crate root
112pub use big_o::big_o_normal_form;
113pub use canonical::canonical_form;
114pub use error::{ProblemError, Result};
115pub use expr::{asymptotic_normal_form, AsymptoticAnalysisError, CanonicalizationError, Expr};
116pub use registry::{ComplexityClass, ProblemInfo};
117pub use solvers::{BruteForce, Solver};
118pub use traits::Problem;
119pub use types::{
120    And, Extremum, ExtremumSense, Max, Min, NumericSize, One, Or, ProblemSize, Sum, Unweighted,
121    WeightElement,
122};
123
124// Re-export proc macros for reduction registration and variant declaration
125pub use problemreductions_macros::{declare_variants, reduction};
126
127// Re-export inventory so `declare_variants!` can use `$crate::inventory::submit!`
128pub use inventory;
129
130#[cfg(test)]
131#[path = "unit_tests/graph_models.rs"]
132mod test_graph_models;
133#[cfg(test)]
134#[path = "unit_tests/prelude.rs"]
135mod test_prelude;
136#[cfg(test)]
137#[path = "unit_tests/property.rs"]
138mod test_property;
139#[cfg(test)]
140#[path = "unit_tests/reduction_graph.rs"]
141mod test_reduction_graph;
142#[cfg(test)]
143#[path = "unit_tests/unitdiskmapping_algorithms/mod.rs"]
144mod test_unitdiskmapping_algorithms;
problemreductions/lib.rs

problemreductions/
lib.rs
