problemreductions/rules/
maximumindependentset_casts.rs

1//! Variant reductions for MaximumIndependentSet.
2//!
3//! Each rule converts one registered graph or weight representation.
4
5use crate::impl_variant_reduction;
6use crate::models::graph::MaximumIndependentSet;
7use crate::topology::{Graph, KingsSubgraph, SimpleGraph, TriangularSubgraph, UnitDiskGraph};
8use crate::types::One;
9
10impl_variant_reduction!(
11    MaximumIndependentSet,
12    <KingsSubgraph, i64> => <UnitDiskGraph, i64>,
13    fields: [num_vertices, num_edges],
14    |src| MaximumIndependentSet::new(
15        src.graph().try_to_unit_disk_graph().map_err(
16            crate::rules::ReductionError::construction::<
17                MaximumIndependentSet<KingsSubgraph, i64>,
18                MaximumIndependentSet<UnitDiskGraph, i64>,
19            >,
20        )?,
21        src.weights().to_vec())
22);
23
24impl_variant_reduction!(
25    MaximumIndependentSet,
26    <TriangularSubgraph, i64> => <UnitDiskGraph, i64>,
27    fields: [num_vertices, num_edges],
28    |src| MaximumIndependentSet::new(
29        src.graph().try_to_unit_disk_graph().map_err(
30            crate::rules::ReductionError::construction::<
31                MaximumIndependentSet<TriangularSubgraph, i64>,
32                MaximumIndependentSet<UnitDiskGraph, i64>,
33            >,
34        )?,
35        src.weights().to_vec())
36);
37
38impl_variant_reduction!(
39    MaximumIndependentSet,
40    <UnitDiskGraph, i64> => <SimpleGraph, i64>,
41    fields: [num_vertices, num_edges],
42    |src| MaximumIndependentSet::new(
43        SimpleGraph::new(src.num_vertices(), Graph::edges(src.graph())),
44        src.weights().to_vec())
45);
46
47// Graph representation reductions with unit weights
48impl_variant_reduction!(
49    MaximumIndependentSet,
50    <KingsSubgraph, One> => <UnitDiskGraph, One>,
51    fields: [num_vertices, num_edges],
52    |src| MaximumIndependentSet::new(
53        src.graph().try_to_unit_disk_graph().map_err(
54            crate::rules::ReductionError::construction::<
55                MaximumIndependentSet<KingsSubgraph, One>,
56                MaximumIndependentSet<UnitDiskGraph, One>,
57            >,
58        )?,
59        src.weights().to_vec())
60);
61
62impl_variant_reduction!(
63    MaximumIndependentSet,
64    <UnitDiskGraph, One> => <SimpleGraph, One>,
65    fields: [num_vertices, num_edges],
66    |src| MaximumIndependentSet::new(
67        SimpleGraph::new(src.num_vertices(), Graph::edges(src.graph())),
68        src.weights().to_vec())
69);
70
71// Unit-to-integer weight reductions
72impl_variant_reduction!(
73    MaximumIndependentSet,
74    <SimpleGraph, One> => <SimpleGraph, i64>,
75    fields: [num_vertices, num_edges],
76    |src| MaximumIndependentSet::new(
77        src.graph().clone(), vec![1_i64; src.num_vertices()])
78);
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83    use crate::rules::{ReduceTo, ReductionError};
84    use crate::types::MAX_EXACT_F64_INTEGER;
85
86    #[test]
87    fn kings_to_unit_disk_exposes_coordinate_conversion_error() {
88        let source = MaximumIndependentSet::new(
89            KingsSubgraph::new(vec![(MAX_EXACT_F64_INTEGER + 1, 0)]),
90            vec![1_i64],
91        );
92
93        assert!(matches!(
94            ReduceTo::<MaximumIndependentSet<UnitDiskGraph, i64>>::reduce_to(&source),
95            Err(ReductionError::Construction { .. })
96        ));
97    }
98
99    #[test]
100    fn triangular_to_unit_disk_exposes_adjacency_conversion_error() {
101        let source = MaximumIndependentSet::new(
102            TriangularSubgraph::new(vec![(MAX_EXACT_F64_INTEGER, 0), (MAX_EXACT_F64_INTEGER, 1)]),
103            vec![1_i64, 1_i64],
104        );
105
106        assert!(matches!(
107            ReduceTo::<MaximumIndependentSet<UnitDiskGraph, i64>>::reduce_to(&source),
108            Err(ReductionError::Construction { .. })
109        ));
110    }
111}
112
113impl_variant_reduction!(
114    MaximumIndependentSet,
115    <KingsSubgraph, One> => <KingsSubgraph, i64>,
116    fields: [num_vertices, num_edges],
117    |src| MaximumIndependentSet::new(
118        src.graph().clone(), vec![1_i64; src.num_vertices()])
119);
120
121impl_variant_reduction!(
122    MaximumIndependentSet,
123    <UnitDiskGraph, One> => <UnitDiskGraph, i64>,
124    fields: [num_vertices, num_edges],
125    |src| MaximumIndependentSet::new(
126        src.graph().clone(), vec![1_i64; src.num_vertices()])
127);
128
129crate::register_aggregate_reduction!(
130    crate::rules::VariantReductionResult<
131        MaximumIndependentSet<KingsSubgraph, i64>,
132        MaximumIndependentSet<UnitDiskGraph, i64>,
133    >
134);
135crate::register_aggregate_reduction!(
136    crate::rules::VariantReductionResult<
137        MaximumIndependentSet<TriangularSubgraph, i64>,
138        MaximumIndependentSet<UnitDiskGraph, i64>,
139    >
140);
141crate::register_aggregate_reduction!(
142    crate::rules::VariantReductionResult<
143        MaximumIndependentSet<UnitDiskGraph, i64>,
144        MaximumIndependentSet<SimpleGraph, i64>,
145    >
146);
147crate::register_aggregate_reduction!(
148    crate::rules::VariantReductionResult<
149        MaximumIndependentSet<KingsSubgraph, One>,
150        MaximumIndependentSet<UnitDiskGraph, One>,
151    >
152);
153crate::register_aggregate_reduction!(
154    crate::rules::VariantReductionResult<
155        MaximumIndependentSet<UnitDiskGraph, One>,
156        MaximumIndependentSet<SimpleGraph, One>,
157    >
158);
159crate::register_aggregate_reduction!(
160    crate::rules::VariantReductionResult<
161        MaximumIndependentSet<SimpleGraph, One>,
162        MaximumIndependentSet<SimpleGraph, i64>,
163    >
164);
165crate::register_aggregate_reduction!(
166    crate::rules::VariantReductionResult<
167        MaximumIndependentSet<KingsSubgraph, One>,
168        MaximumIndependentSet<KingsSubgraph, i64>,
169    >
170);
171crate::register_aggregate_reduction!(
172    crate::rules::VariantReductionResult<
173        MaximumIndependentSet<UnitDiskGraph, One>,
174        MaximumIndependentSet<UnitDiskGraph, i64>,
175    >
176);
problemreductions/rules/maximumindependentset_casts.rs

problemreductions/rules/
maximumindependentset_casts.rs
