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    aggregate: identity,
15    |src| MaximumIndependentSet::new(
16        src.graph().try_to_unit_disk_graph().map_err(
17            crate::rules::ReductionError::construction::<
18                MaximumIndependentSet<KingsSubgraph, i64>,
19                MaximumIndependentSet<UnitDiskGraph, i64>,
20            >,
21        )?,
22        src.weights().to_vec())
23);
24
25impl_variant_reduction!(
26    MaximumIndependentSet,
27    <TriangularSubgraph, i64> => <UnitDiskGraph, i64>,
28    fields: [num_vertices, num_edges],
29    aggregate: identity,
30    |src| MaximumIndependentSet::new(
31        src.graph().try_to_unit_disk_graph().map_err(
32            crate::rules::ReductionError::construction::<
33                MaximumIndependentSet<TriangularSubgraph, i64>,
34                MaximumIndependentSet<UnitDiskGraph, i64>,
35            >,
36        )?,
37        src.weights().to_vec())
38);
39
40impl_variant_reduction!(
41    MaximumIndependentSet,
42    <UnitDiskGraph, i64> => <SimpleGraph, i64>,
43    fields: [num_vertices, num_edges],
44    aggregate: identity,
45    |src| MaximumIndependentSet::new(
46        SimpleGraph::new(src.num_vertices(), Graph::edges(src.graph())),
47        src.weights().to_vec())
48);
49
50// Graph representation reductions with unit weights
51impl_variant_reduction!(
52    MaximumIndependentSet,
53    <KingsSubgraph, One> => <UnitDiskGraph, One>,
54    fields: [num_vertices, num_edges],
55    aggregate: identity,
56    |src| MaximumIndependentSet::new(
57        src.graph().try_to_unit_disk_graph().map_err(
58            crate::rules::ReductionError::construction::<
59                MaximumIndependentSet<KingsSubgraph, One>,
60                MaximumIndependentSet<UnitDiskGraph, One>,
61            >,
62        )?,
63        src.weights().to_vec())
64);
65
66impl_variant_reduction!(
67    MaximumIndependentSet,
68    <UnitDiskGraph, One> => <SimpleGraph, One>,
69    fields: [num_vertices, num_edges],
70    aggregate: identity,
71    |src| MaximumIndependentSet::new(
72        SimpleGraph::new(src.num_vertices(), Graph::edges(src.graph())),
73        src.weights().to_vec())
74);
75
76// Unit-to-integer weight reductions
77impl_variant_reduction!(
78    MaximumIndependentSet,
79    <SimpleGraph, One> => <SimpleGraph, i64>,
80    fields: [num_vertices, num_edges],
81    aggregate: identity,
82    |src| MaximumIndependentSet::new(
83        src.graph().clone(), vec![1_i64; src.num_vertices()])
84);
85
86#[cfg(test)]
87mod tests {
88    use super::*;
89    use crate::rules::{ReduceTo, ReductionError};
90    use crate::types::MAX_EXACT_F64_INTEGER;
91
92    #[test]
93    fn kings_to_unit_disk_exposes_coordinate_conversion_error() {
94        let source = MaximumIndependentSet::new(
95            KingsSubgraph::new(vec![(MAX_EXACT_F64_INTEGER + 1, 0)]),
96            vec![1_i64],
97        );
98
99        assert!(matches!(
100            ReduceTo::<MaximumIndependentSet<UnitDiskGraph, i64>>::reduce_to(&source),
101            Err(ReductionError::Construction { .. })
102        ));
103    }
104
105    #[test]
106    fn triangular_to_unit_disk_exposes_adjacency_conversion_error() {
107        let source = MaximumIndependentSet::new(
108            TriangularSubgraph::new(vec![(MAX_EXACT_F64_INTEGER, 0), (MAX_EXACT_F64_INTEGER, 1)]),
109            vec![1_i64, 1_i64],
110        );
111
112        assert!(matches!(
113            ReduceTo::<MaximumIndependentSet<UnitDiskGraph, i64>>::reduce_to(&source),
114            Err(ReductionError::Construction { .. })
115        ));
116    }
117}
118
119impl_variant_reduction!(
120    MaximumIndependentSet,
121    <KingsSubgraph, One> => <KingsSubgraph, i64>,
122    fields: [num_vertices, num_edges],
123    aggregate: identity,
124    |src| MaximumIndependentSet::new(
125        src.graph().clone(), vec![1_i64; src.num_vertices()])
126);
127
128impl_variant_reduction!(
129    MaximumIndependentSet,
130    <UnitDiskGraph, One> => <UnitDiskGraph, i64>,
131    fields: [num_vertices, num_edges],
132    aggregate: identity,
133    |src| MaximumIndependentSet::new(
134        src.graph().clone(), vec![1_i64; src.num_vertices()])
135);
problemreductions/rules/maximumindependentset_casts.rs

problemreductions/rules/
maximumindependentset_casts.rs
