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.map_config_back(target_solution)
32    }
33}
34
35#[reduction(
36    overhead = {
37        num_vertices = "num_vertices * num_vertices",
38        num_edges = "num_vertices * num_vertices",
39    }
40)]
41impl ReduceTo<MaximumIndependentSet<TriangularSubgraph, i32>>
42    for MaximumIndependentSet<SimpleGraph, One>
43{
44    type Result = ReductionISSimpleToTriangular;
45
46    fn reduce_to(&self) -> Self::Result {
47        let n = self.graph().num_vertices();
48        let edges = self.graph().edges();
49        let result = triangular::map_weighted(n, &edges);
50        let weights = result.node_weights.clone();
51        let grid = result.to_triangular_subgraph();
52        let target = MaximumIndependentSet::new(grid, weights);
53        ReductionISSimpleToTriangular {
54            target,
55            mapping_result: result,
56        }
57    }
58}
59
60#[cfg(test)]
61#[path = "../unit_tests/rules/maximumindependentset_triangular.rs"]
62mod tests;
problemreductions/rules/maximumindependentset_triangular.rs

problemreductions/rules/
maximumindependentset_triangular.rs
