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 crate::registry::ConstructionError;
9use crate::types::i64_to_exact_f64;
10use serde::{Deserialize, Serialize};
11
12/// A King's Subgraph — an unweighted unit disk graph on a square lattice.
13///
14/// Vertices occupy integer grid positions with edges determined by distance
15/// (king's move connectivity: adjacent horizontally, vertically, or diagonally).
16/// This is a subtype of [`UnitDiskGraph`] in the variant hierarchy.
17///
18/// Edges are computed on-the-fly: two positions are connected if their
19/// Euclidean distance is strictly less than 1.5.
20#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
21pub struct KingsSubgraph {
22    /// Integer grid positions (row, col) for each vertex.
23    positions: Vec<(i64, i64)>,
24}
25
26/// Fixed radius for king's move connectivity on integer grid.
27const KINGS_RADIUS: f64 = 1.5;
28
29impl KingsSubgraph {
30    /// Create a KingsSubgraph from a list of integer positions.
31    pub fn new(positions: Vec<(i64, i64)>) -> Self {
32        Self { positions }
33    }
34
35    /// Get the positions of all vertices.
36    pub fn positions(&self) -> &[(i64, i64)] {
37        &self.positions
38    }
39
40    /// Get the number of positions (vertices).
41    pub fn num_positions(&self) -> usize {
42        self.positions.len()
43    }
44
45    fn are_adjacent(p1: (i64, i64), p2: (i64, i64)) -> bool {
46        p1.0.abs_diff(p2.0) <= 1 && p1.1.abs_diff(p2.1) <= 1
47    }
48
49    pub(crate) fn try_to_unit_disk_graph(&self) -> Result<UnitDiskGraph, ConstructionError> {
50        let positions = self
51            .positions
52            .iter()
53            .map(|&(row, column)| {
54                let row = i64_to_exact_f64(row)?;
55                let column = i64_to_exact_f64(column)?;
56                Ok((row, column))
57            })
58            .collect::<Result<Vec<_>, ConstructionError>>()?;
59        let graph = UnitDiskGraph::new(positions, KINGS_RADIUS)?;
60        for first in 0..self.positions.len() {
61            for second in (first + 1)..self.positions.len() {
62                if Self::are_adjacent(self.positions[first], self.positions[second])
63                    != graph.has_edge(first, second)
64                {
65                    return Err(ConstructionError::Conversion(format!(
66                        "king's-subgraph coordinates at indices {first} and {second} cannot be represented in UnitDiskGraph without changing adjacency"
67                    )));
68                }
69            }
70        }
71        Ok(graph)
72    }
73}
74
75impl Graph for KingsSubgraph {
76    const NAME: &'static str = "KingsSubgraph";
77
78    fn num_vertices(&self) -> usize {
79        self.positions.len()
80    }
81
82    fn num_edges(&self) -> usize {
83        let n = self.positions.len();
84        let mut count = 0;
85        for i in 0..n {
86            for j in (i + 1)..n {
87                if Self::are_adjacent(self.positions[i], self.positions[j]) {
88                    count += 1;
89                }
90            }
91        }
92        count
93    }
94
95    fn edges(&self) -> Vec<(usize, usize)> {
96        let n = self.positions.len();
97        let mut edges = Vec::new();
98        for i in 0..n {
99            for j in (i + 1)..n {
100                if Self::are_adjacent(self.positions[i], self.positions[j]) {
101                    edges.push((i, j));
102                }
103            }
104        }
105        edges
106    }
107
108    fn has_edge(&self, u: usize, v: usize) -> bool {
109        if u >= self.positions.len() || v >= self.positions.len() || u == v {
110            return false;
111        }
112        Self::are_adjacent(self.positions[u], self.positions[v])
113    }
114
115    fn neighbors(&self, v: usize) -> Vec<usize> {
116        if v >= self.positions.len() {
117            return Vec::new();
118        }
119        (0..self.positions.len())
120            .filter(|&u| u != v && Self::are_adjacent(self.positions[v], self.positions[u]))
121            .collect()
122    }
123}
124
125impl crate::variant::VariantParam for KingsSubgraph {
126    const CATEGORY: &'static str = "graph";
127    const VALUE: &'static str = "KingsSubgraph";
128}
129
130#[cfg(test)]
131mod tests {
132    use super::*;
133    use crate::types::MAX_EXACT_F64_INTEGER;
134
135    #[test]
136    fn adjacency_handles_full_i64_coordinate_range() {
137        let graph = KingsSubgraph::new(vec![
138            (i64::MAX, i64::MAX),
139            (i64::MAX - 1, i64::MAX - 1),
140            (i64::MIN, i64::MIN),
141        ]);
142
143        assert!(graph.has_edge(0, 1));
144        assert!(!graph.has_edge(0, 2));
145    }
146
147    #[test]
148    fn integer_adjacency_matches_euclidean_definition() {
149        for row_a in -4..=4 {
150            for column_a in -4..=4 {
151                for row_b in -4..=4 {
152                    for column_b in -4..=4 {
153                        let dr = (row_a - row_b) as f64;
154                        let dc = (column_a - column_b) as f64;
155                        let euclidean = dr.hypot(dc) < KINGS_RADIUS;
156                        assert_eq!(
157                            KingsSubgraph::are_adjacent((row_a, column_a), (row_b, column_b)),
158                            euclidean
159                        );
160                    }
161                }
162            }
163        }
164    }
165
166    #[test]
167    fn unit_disk_conversion_rejects_inexact_coordinates() {
168        let graph = KingsSubgraph::new(vec![(MAX_EXACT_F64_INTEGER + 1, 0)]);
169
170        assert!(matches!(
171            graph.try_to_unit_disk_graph(),
172            Err(ConstructionError::InexactFloatConversion(_))
173        ));
174    }
175}
problemreductions/topology/kings_subgraph.rs

problemreductions/topology/
kings_subgraph.rs
