problemreductions/topology/
triangular_subgraph.rs

1//! Triangular Subgraph — an unweighted unit disk graph on a triangular lattice.
2//!
3//! This is a public graph type produced by the triangular 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 Triangular Subgraph — an unweighted unit disk graph on a triangular lattice.
13///
14/// Vertices occupy positions on a triangular grid with edges determined by distance.
15/// This is a subtype of [`UnitDiskGraph`] in the variant hierarchy.
16///
17/// Physical position for integer coordinates `(row, col)`:
18/// - `x = row + 0.5` if col is even, else `x = row`
19/// - `y = col * sqrt(3)/2`
20///
21/// Edges are computed on-the-fly: two positions are connected if their
22/// physical Euclidean distance is strictly less than 1.1.
23#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
24pub struct TriangularSubgraph {
25    /// Integer grid positions (row, col) for each vertex.
26    positions: Vec<(i64, i64)>,
27}
28
29/// Fixed radius for triangular lattice adjacency.
30const TRIANGULAR_RADIUS: f64 = 1.1;
31
32impl TriangularSubgraph {
33    /// Create a TriangularSubgraph from a list of integer positions.
34    pub fn new(positions: Vec<(i64, i64)>) -> Self {
35        Self { positions }
36    }
37
38    /// Get the positions of all vertices.
39    pub fn positions(&self) -> &[(i64, i64)] {
40        &self.positions
41    }
42
43    /// Get the number of positions (vertices).
44    pub fn num_positions(&self) -> usize {
45        self.positions.len()
46    }
47
48    /// Compute the physical position for a triangular lattice coordinate.
49    ///
50    /// Uses `offset_even_cols = true` convention:
51    /// - `x = row + 0.5` if col is even, else `x = row`
52    /// - `y = col * sqrt(3)/2`
53    #[allow(unknown_lints, clippy::manual_is_multiple_of)]
54    fn physical_position(row: i64, col: i64) -> Result<(f64, f64), ConstructionError> {
55        let row = i64_to_exact_f64(row)?;
56        let offset = if col % 2 == 0 { 0.5 } else { 0.0 };
57        let col = i64_to_exact_f64(col)?;
58        let y = col * (3.0_f64.sqrt() / 2.0);
59        let x = row + offset;
60        Ok((x, y))
61    }
62
63    fn are_adjacent(p1: (i64, i64), p2: (i64, i64)) -> bool {
64        let column_delta = (i128::from(p1.1) - i128::from(p2.1)).abs();
65        if column_delta > 1 {
66            return false;
67        }
68        let x1 = 2 * i128::from(p1.0) + i128::from(p1.1.rem_euclid(2) == 0);
69        let x2 = 2 * i128::from(p2.0) + i128::from(p2.1.rem_euclid(2) == 0);
70        let x_delta = (x1 - x2).abs();
71        x_delta <= 2 && x_delta * x_delta + 3 * column_delta * column_delta <= 4
72    }
73
74    pub(crate) fn try_to_unit_disk_graph(&self) -> Result<UnitDiskGraph, ConstructionError> {
75        let positions = self
76            .positions
77            .iter()
78            .map(|&(row, column)| Self::physical_position(row, column))
79            .collect::<Result<Vec<_>, _>>()?;
80        let graph = UnitDiskGraph::new(positions, TRIANGULAR_RADIUS)?;
81        for first in 0..self.positions.len() {
82            for second in (first + 1)..self.positions.len() {
83                if Self::are_adjacent(self.positions[first], self.positions[second])
84                    != graph.has_edge(first, second)
85                {
86                    return Err(ConstructionError::Conversion(format!(
87                        "triangular-subgraph coordinates at indices {first} and {second} cannot be represented in UnitDiskGraph without changing adjacency"
88                    )));
89                }
90            }
91        }
92        Ok(graph)
93    }
94}
95
96impl Graph for TriangularSubgraph {
97    const NAME: &'static str = "TriangularSubgraph";
98
99    fn num_vertices(&self) -> usize {
100        self.positions.len()
101    }
102
103    fn num_edges(&self) -> usize {
104        let n = self.positions.len();
105        let mut count = 0;
106        for i in 0..n {
107            for j in (i + 1)..n {
108                if Self::are_adjacent(self.positions[i], self.positions[j]) {
109                    count += 1;
110                }
111            }
112        }
113        count
114    }
115
116    fn edges(&self) -> Vec<(usize, usize)> {
117        let n = self.positions.len();
118        let mut edges = Vec::new();
119        for i in 0..n {
120            for j in (i + 1)..n {
121                if Self::are_adjacent(self.positions[i], self.positions[j]) {
122                    edges.push((i, j));
123                }
124            }
125        }
126        edges
127    }
128
129    fn has_edge(&self, u: usize, v: usize) -> bool {
130        if u >= self.positions.len() || v >= self.positions.len() || u == v {
131            return false;
132        }
133        Self::are_adjacent(self.positions[u], self.positions[v])
134    }
135
136    fn neighbors(&self, v: usize) -> Vec<usize> {
137        if v >= self.positions.len() {
138            return Vec::new();
139        }
140        (0..self.positions.len())
141            .filter(|&u| u != v && Self::are_adjacent(self.positions[v], self.positions[u]))
142            .collect()
143    }
144}
145
146impl crate::variant::VariantParam for TriangularSubgraph {
147    const CATEGORY: &'static str = "graph";
148    const VALUE: &'static str = "TriangularSubgraph";
149}
150
151#[cfg(test)]
152mod tests {
153    use super::*;
154    use crate::types::MAX_EXACT_F64_INTEGER;
155
156    #[test]
157    fn adjacency_handles_full_i64_coordinate_range() {
158        let graph = TriangularSubgraph::new(vec![(i64::MAX, 0), (i64::MAX, 1), (i64::MIN, 0)]);
159
160        assert!(graph.has_edge(0, 1));
161        assert!(!graph.has_edge(0, 2));
162    }
163
164    #[test]
165    fn integer_adjacency_matches_euclidean_definition() {
166        for row_a in -4..=4 {
167            for column_a in -4..=4 {
168                for row_b in -4..=4 {
169                    for column_b in -4..=4 {
170                        let a = TriangularSubgraph::physical_position(row_a, column_a).unwrap();
171                        let b = TriangularSubgraph::physical_position(row_b, column_b).unwrap();
172                        let euclidean = (a.0 - b.0).hypot(a.1 - b.1) < TRIANGULAR_RADIUS;
173                        assert_eq!(
174                            TriangularSubgraph::are_adjacent((row_a, column_a), (row_b, column_b)),
175                            euclidean
176                        );
177                    }
178                }
179            }
180        }
181    }
182
183    #[test]
184    fn unit_disk_conversion_rejects_inexact_coordinates() {
185        let graph = TriangularSubgraph::new(vec![(MAX_EXACT_F64_INTEGER + 1, 0)]);
186
187        assert!(matches!(
188            graph.try_to_unit_disk_graph(),
189            Err(ConstructionError::InexactFloatConversion(_))
190        ));
191    }
192
193    #[test]
194    fn unit_disk_conversion_rejects_changed_adjacency() {
195        let graph =
196            TriangularSubgraph::new(vec![(MAX_EXACT_F64_INTEGER, 0), (MAX_EXACT_F64_INTEGER, 1)]);
197
198        assert!(matches!(
199            graph.try_to_unit_disk_graph(),
200            Err(ConstructionError::Conversion(_))
201        ));
202    }
203}
problemreductions/topology/triangular_subgraph.rs

problemreductions/topology/
triangular_subgraph.rs
