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, i32>.
16#[derive(Debug, Clone)]
17pub struct ReductionISSimpleToTriangular {
18    target: MaximumIndependentSet<TriangularSubgraph, i32>,
19    mapping_result: ksg::MappingResult<ksg::KsgTapeEntry>,
20}
21
22impl ReductionResult for ReductionISSimpleToTriangular {
23    type Source = MaximumIndependentSet<SimpleGraph, One>;
24    type Target = MaximumIndependentSet<TriangularSubgraph, i32>;
25
26    fn target_problem(&self) -> &Self::Target {
27        &self.target
28    }
29
30    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
31        self.mapping_result
32            .map_config_back_via_centers(target_solution)
33    }
34}
35
36#[reduction(
37    overhead = {
38        num_vertices = "num_vertices * num_vertices",
39        num_edges = "num_vertices * num_vertices",
40    }
41)]
42impl ReduceTo<MaximumIndependentSet<TriangularSubgraph, i32>>
43    for MaximumIndependentSet<SimpleGraph, One>
44{
45    type Result = ReductionISSimpleToTriangular;
46
47    fn reduce_to(&self) -> Self::Result {
48        let n = self.graph().num_vertices();
49        let edges = self.graph().edges();
50        let result = triangular::map_weighted(n, &edges);
51        let weights = result.node_weights.clone();
52        let grid = result.to_triangular_subgraph();
53        let target = MaximumIndependentSet::new(grid, weights);
54        ReductionISSimpleToTriangular {
55            target,
56            mapping_result: result,
57        }
58    }
59}
60
61#[cfg(test)]
62#[path = "../unit_tests/rules/maximumindependentset_triangular.rs"]
63mod tests;
problemreductions/rules/maximumindependentset_triangular.rs

problemreductions/rules/
maximumindependentset_triangular.rs
