problemreductions/rules/
maximumindependentset_triangular.rs

1//! Reduction from unweighted MaximumIndependentSet on SimpleGraph to TriangularSubgraph
2//! using the triangular unit disk mapping.
3//!
4//! Maps an arbitrary graph's MIS problem to an equivalent weighted MIS on a
5//! triangular lattice grid graph.
6
7use crate::models::graph::MaximumIndependentSet;
8use crate::reduction;
9use crate::rules::traits::{ReduceTo, ReductionResult};
10use crate::rules::unitdiskmapping::ksg;
11use crate::rules::unitdiskmapping::triangular;
12use crate::topology::{Graph, SimpleGraph, TriangularSubgraph};
13use crate::types::One;
14
15/// Result of reducing MIS<SimpleGraph, One> to MIS<TriangularSubgraph, i64>.
16#[derive(Debug, Clone)]
17pub struct ReductionISSimpleToTriangular {
18    target: MaximumIndependentSet<TriangularSubgraph, i64>,
19    mapping_result: ksg::MappingResult<ksg::KsgTapeEntry>,
20}
21
22impl ReductionResult for ReductionISSimpleToTriangular {
23    type Source = MaximumIndependentSet<SimpleGraph, One>;
24    type Target = MaximumIndependentSet<TriangularSubgraph, i64>;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    fn extract_solution(
31        &self,
32        target_solution: &<Self::Target as crate::traits::Problem>::Solution,
33    ) -> crate::rules::ExtractionResult<<Self::Source as crate::traits::Problem>::Solution> {
34        crate::rules::traits::validate_target_solution(self.target_problem(), target_solution)?;
35
36        let encoded = crate::config::bits_to_config(target_solution);
37        let mapped = triangular::map_config_back(&self.mapping_result, &encoded)?;
38        Ok(crate::config::config_to_bits(&mapped))
39    }
40}
41
42#[reduction(
43    transform = upper_bound {
44        num_vertices = "36 * num_vertices^2 + 36 * num_vertices",
45        num_edges = "108 * num_vertices^2 + 108 * num_vertices",
46    }
47)]
48impl ReduceTo<MaximumIndependentSet<TriangularSubgraph, i64>>
49    for MaximumIndependentSet<SimpleGraph, One>
50{
51    type Result = ReductionISSimpleToTriangular;
52
53    fn reduce_to(&self) -> Result<Self::Result, crate::rules::ReductionError> {
54        let n = self.graph().num_vertices();
55        let edges = self.graph().edges();
56        let mapping_error = |error: crate::rules::ReductionError| {
57            error.for_reduction::<Self, MaximumIndependentSet<TriangularSubgraph, i64>>()
58        };
59        let result = triangular::map_weighted(n, &edges).map_err(&mapping_error)?;
60        let weights = triangular::map_unit_weights(&result).map_err(mapping_error)?;
61        let grid = result.to_triangular_subgraph();
62        let target = MaximumIndependentSet::new(grid, weights);
63        Ok(ReductionISSimpleToTriangular {
64            target,
65            mapping_result: result,
66        })
67    }
68}
69
70#[cfg(test)]
71#[path = "../unit_tests/rules/maximumindependentset_triangular.rs"]
72mod tests;
problemreductions/rules/maximumindependentset_triangular.rs

problemreductions/rules/
maximumindependentset_triangular.rs
