problemreductions/rules/
mod.rs

1//! Reduction rules between NP-hard problems.
2
3pub mod analysis;
4pub mod cost;
5pub mod registry;
6pub use cost::{CustomCost, Minimize, MinimizeSteps, PathCostFn};
7pub use registry::{ReductionEntry, ReductionOverhead};
8
9mod circuit_spinglass;
10mod coloring_qubo;
11mod factoring_circuit;
12mod graph;
13mod kcoloring_casts;
14mod ksatisfiability_casts;
15mod ksatisfiability_qubo;
16mod ksatisfiability_subsetsum;
17mod maximumindependentset_casts;
18mod maximumindependentset_gridgraph;
19mod maximumindependentset_maximumclique;
20mod maximumindependentset_maximumsetpacking;
21mod maximumindependentset_triangular;
22mod maximummatching_maximumsetpacking;
23mod maximumsetpacking_casts;
24mod maximumsetpacking_qubo;
25mod minimumvertexcover_maximumindependentset;
26mod minimumvertexcover_minimumsetcovering;
27mod sat_circuitsat;
28mod sat_coloring;
29mod sat_ksat;
30mod sat_maximumindependentset;
31mod sat_minimumdominatingset;
32mod spinglass_casts;
33mod spinglass_maxcut;
34mod spinglass_qubo;
35mod traits;
36
37pub mod unitdiskmapping;
38
39#[cfg(feature = "ilp-solver")]
40mod binpacking_ilp;
41#[cfg(feature = "ilp-solver")]
42mod circuit_ilp;
43#[cfg(feature = "ilp-solver")]
44mod coloring_ilp;
45#[cfg(feature = "ilp-solver")]
46mod factoring_ilp;
47#[cfg(feature = "ilp-solver")]
48mod ilp_bool_ilp_i32;
49#[cfg(feature = "ilp-solver")]
50mod ilp_qubo;
51#[cfg(feature = "ilp-solver")]
52mod maximumclique_ilp;
53#[cfg(feature = "ilp-solver")]
54mod maximummatching_ilp;
55#[cfg(feature = "ilp-solver")]
56mod maximumsetpacking_ilp;
57#[cfg(feature = "ilp-solver")]
58mod minimumdominatingset_ilp;
59#[cfg(feature = "ilp-solver")]
60mod minimumsetcovering_ilp;
61#[cfg(feature = "ilp-solver")]
62mod qubo_ilp;
63#[cfg(feature = "ilp-solver")]
64mod travelingsalesman_ilp;
65
66pub use graph::{
67    NeighborInfo, NeighborTree, ReductionChain, ReductionEdgeInfo, ReductionGraph, ReductionPath,
68    ReductionStep, TraversalDirection,
69};
70pub use traits::{ReduceTo, ReductionAutoCast, ReductionResult};
71
72/// Generates a variant-cast `ReduceTo` impl with `#[reduction]` registration.
73///
74/// Variant casts convert a problem from one variant to another (e.g.,
75/// `MIS<KingsSubgraph, i32>` -> `MIS<UnitDiskGraph, i32>`). The solution
76/// mapping is identity -- vertex/element indices are preserved.
77///
78/// The problem name is specified once, followed by `<SourceParams> => <TargetParams>`.
79/// This works with any number of type parameters.
80///
81/// # Example
82///
83/// ```text
84/// impl_variant_reduction!(
85///     MaximumIndependentSet,
86///     <KingsSubgraph, i32> => <UnitDiskGraph, i32>,
87///     fields: [num_vertices, num_edges],
88///     |src| MaximumIndependentSet::new(
89///         src.graph().cast_to_parent(), src.weights())
90/// );
91/// ```
92#[macro_export]
93macro_rules! impl_variant_reduction {
94    ($problem:ident,
95     < $($src_param:ty),+ > => < $($dst_param:ty),+ >,
96     fields: [$($field:ident),+],
97     |$src:ident| $body:expr) => {
98        #[$crate::reduction(
99            overhead = {
100                $crate::rules::registry::ReductionOverhead::identity(
101                    &[$(stringify!($field)),+]
102                )
103            }
104        )]
105        impl $crate::rules::ReduceTo<$problem<$($dst_param),+>>
106            for $problem<$($src_param),+>
107        {
108            type Result = $crate::rules::ReductionAutoCast<
109                $problem<$($src_param),+>,
110                $problem<$($dst_param),+>,
111            >;
112            fn reduce_to(&self) -> Self::Result {
113                let $src = self;
114                $crate::rules::ReductionAutoCast::new($body)
115            }
116        }
117    };
118}
problemreductions/rules/mod.rs

problemreductions/rules/
mod.rs
