problemreductions/topology/
kings_subgraph.rs

1//! King's Subgraph — an unweighted unit disk graph on a square grid (king's move connectivity).
2//!
3//! This is a public graph type produced by the KSG unit disk mapping reduction.
4//! It stores only integer grid positions; edges are computed on-the-fly from geometry.
5
6use super::graph::Graph;
7use super::unit_disk_graph::UnitDiskGraph;
8use serde::{Deserialize, Serialize};
9
10/// A King's Subgraph — an unweighted unit disk graph on a square lattice.
11///
12/// Vertices occupy integer grid positions with edges determined by distance
13/// (king's move connectivity: adjacent horizontally, vertically, or diagonally).
14/// This is a subtype of [`UnitDiskGraph`] in the variant hierarchy.
15///
16/// Edges are computed on-the-fly: two positions are connected if their
17/// Euclidean distance is strictly less than 1.5.
18#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
19pub struct KingsSubgraph {
20    /// Integer grid positions (row, col) for each vertex.
21    positions: Vec<(i32, i32)>,
22}
23
24/// Fixed radius for king's move connectivity on integer grid.
25const KINGS_RADIUS: f64 = 1.5;
26
27impl KingsSubgraph {
28    /// Create a KingsSubgraph from a list of integer positions.
29    pub fn new(positions: Vec<(i32, i32)>) -> Self {
30        Self { positions }
31    }
32
33    /// Get the positions of all vertices.
34    pub fn positions(&self) -> &[(i32, i32)] {
35        &self.positions
36    }
37
38    /// Get the number of positions (vertices).
39    pub fn num_positions(&self) -> usize {
40        self.positions.len()
41    }
42
43    /// Compute Euclidean distance between two integer positions.
44    fn distance(p1: (i32, i32), p2: (i32, i32)) -> f64 {
45        let dx = (p1.0 - p2.0) as f64;
46        let dy = (p1.1 - p2.1) as f64;
47        (dx * dx + dy * dy).sqrt()
48    }
49}
50
51impl Graph for KingsSubgraph {
52    const NAME: &'static str = "KingsSubgraph";
53
54    fn num_vertices(&self) -> usize {
55        self.positions.len()
56    }
57
58    fn num_edges(&self) -> usize {
59        let n = self.positions.len();
60        let mut count = 0;
61        for i in 0..n {
62            for j in (i + 1)..n {
63                if Self::distance(self.positions[i], self.positions[j]) < KINGS_RADIUS {
64                    count += 1;
65                }
66            }
67        }
68        count
69    }
70
71    fn edges(&self) -> Vec<(usize, usize)> {
72        let n = self.positions.len();
73        let mut edges = Vec::new();
74        for i in 0..n {
75            for j in (i + 1)..n {
76                if Self::distance(self.positions[i], self.positions[j]) < KINGS_RADIUS {
77                    edges.push((i, j));
78                }
79            }
80        }
81        edges
82    }
83
84    fn has_edge(&self, u: usize, v: usize) -> bool {
85        if u >= self.positions.len() || v >= self.positions.len() || u == v {
86            return false;
87        }
88        Self::distance(self.positions[u], self.positions[v]) < KINGS_RADIUS
89    }
90
91    fn neighbors(&self, v: usize) -> Vec<usize> {
92        if v >= self.positions.len() {
93            return Vec::new();
94        }
95        (0..self.positions.len())
96            .filter(|&u| {
97                u != v && Self::distance(self.positions[v], self.positions[u]) < KINGS_RADIUS
98            })
99            .collect()
100    }
101}
102
103impl crate::variant::VariantParam for KingsSubgraph {
104    const CATEGORY: &'static str = "graph";
105    const VALUE: &'static str = "KingsSubgraph";
106    const PARENT_VALUE: Option<&'static str> = Some("UnitDiskGraph");
107}
108impl crate::variant::CastToParent for KingsSubgraph {
109    type Parent = UnitDiskGraph;
110    fn cast_to_parent(&self) -> UnitDiskGraph {
111        let positions: Vec<(f64, f64)> = self
112            .positions
113            .iter()
114            .map(|&(r, c)| (r as f64, c as f64))
115            .collect();
116        UnitDiskGraph::new(positions, KINGS_RADIUS)
117    }
118}
problemreductions/topology/kings_subgraph.rs

problemreductions/topology/
kings_subgraph.rs
