problemreductions/rules/
maximumindependentset_gridgraph.rs

1//! Reduction from unweighted MaximumIndependentSet on SimpleGraph to KingsSubgraph
2//! using the King's Subgraph (KSG) unit disk mapping.
3//!
4//! Maps an arbitrary graph's MIS problem to an equivalent MIS on a grid graph.
5
6use crate::models::graph::MaximumIndependentSet;
7use crate::reduction;
8use crate::rules::traits::{ReduceTo, ReductionResult};
9use crate::rules::unitdiskmapping::ksg;
10use crate::topology::{Graph, KingsSubgraph, SimpleGraph};
11use crate::types::One;
12
13/// Result of reducing MIS<SimpleGraph, One> to MIS<KingsSubgraph, One>.
14#[derive(Debug, Clone)]
15pub struct ReductionISSimpleOneToGridOne {
16    target: MaximumIndependentSet<KingsSubgraph, One>,
17    mapping_result: ksg::MappingResult<ksg::KsgTapeEntry>,
18}
19
20impl ReductionResult for ReductionISSimpleOneToGridOne {
21    type Source = MaximumIndependentSet<SimpleGraph, One>;
22    type Target = MaximumIndependentSet<KingsSubgraph, One>;
23
24    fn target_problem(&self) -> &Self::Target {
25        &self.target
26    }
27
28    fn extract_solution(&self, target_solution: &[usize]) -> Vec<usize> {
29        self.mapping_result.map_config_back(target_solution)
30    }
31}
32
33#[reduction(
34    overhead = {
35        num_vertices = "num_vertices * num_vertices",
36        num_edges = "num_vertices * num_vertices",
37    }
38)]
39impl ReduceTo<MaximumIndependentSet<KingsSubgraph, One>>
40    for MaximumIndependentSet<SimpleGraph, One>
41{
42    type Result = ReductionISSimpleOneToGridOne;
43
44    fn reduce_to(&self) -> Self::Result {
45        let n = self.graph().num_vertices();
46        let edges = self.graph().edges();
47        let result = ksg::map_unweighted(n, &edges);
48        let grid = result.to_kings_subgraph();
49        let weights = vec![One; grid.num_vertices()];
50        let target = MaximumIndependentSet::new(grid, weights);
51        ReductionISSimpleOneToGridOne {
52            target,
53            mapping_result: result,
54        }
55    }
56}
57
58#[cfg(test)]
59#[path = "../unit_tests/rules/maximumindependentset_gridgraph.rs"]
60mod tests;
problemreductions/rules/maximumindependentset_gridgraph.rs

problemreductions/rules/
maximumindependentset_gridgraph.rs
