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 serde::{Deserialize, Serialize};
9
10/// A Triangular Subgraph — an unweighted unit disk graph on a triangular lattice.
11///
12/// Vertices occupy positions on a triangular grid with edges determined by distance.
13/// This is a subtype of [`UnitDiskGraph`] in the variant hierarchy.
14///
15/// Physical position for integer coordinates `(row, col)`:
16/// - `x = row + 0.5` if col is even, else `x = row`
17/// - `y = col * sqrt(3)/2`
18///
19/// Edges are computed on-the-fly: two positions are connected if their
20/// physical Euclidean distance is strictly less than 1.1.
21#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
22pub struct TriangularSubgraph {
23    /// Integer grid positions (row, col) for each vertex.
24    positions: Vec<(i32, i32)>,
25}
26
27/// Fixed radius for triangular lattice adjacency.
28const TRIANGULAR_RADIUS: f64 = 1.1;
29
30impl TriangularSubgraph {
31    /// Create a TriangularSubgraph from a list of integer positions.
32    pub fn new(positions: Vec<(i32, i32)>) -> Self {
33        Self { positions }
34    }
35
36    /// Get the positions of all vertices.
37    pub fn positions(&self) -> &[(i32, i32)] {
38        &self.positions
39    }
40
41    /// Get the number of positions (vertices).
42    pub fn num_positions(&self) -> usize {
43        self.positions.len()
44    }
45
46    /// Compute the physical position for a triangular lattice coordinate.
47    ///
48    /// Uses `offset_even_cols = true` convention:
49    /// - `x = row + 0.5` if col is even, else `x = row`
50    /// - `y = col * sqrt(3)/2`
51    #[allow(unknown_lints, clippy::manual_is_multiple_of)]
52    fn physical_position(row: i32, col: i32) -> (f64, f64) {
53        let y = col as f64 * (3.0_f64.sqrt() / 2.0);
54        let offset = if col % 2 == 0 { 0.5 } else { 0.0 };
55        let x = row as f64 + offset;
56        (x, y)
57    }
58
59    /// Compute Euclidean distance between two physical positions.
60    fn distance(p1: (f64, f64), p2: (f64, f64)) -> f64 {
61        let dx = p1.0 - p2.0;
62        let dy = p1.1 - p2.1;
63        (dx * dx + dy * dy).sqrt()
64    }
65}
66
67impl Graph for TriangularSubgraph {
68    const NAME: &'static str = "TriangularSubgraph";
69
70    fn num_vertices(&self) -> usize {
71        self.positions.len()
72    }
73
74    fn num_edges(&self) -> usize {
75        let n = self.positions.len();
76        let mut count = 0;
77        for i in 0..n {
78            let pi = Self::physical_position(self.positions[i].0, self.positions[i].1);
79            for j in (i + 1)..n {
80                let pj = Self::physical_position(self.positions[j].0, self.positions[j].1);
81                if Self::distance(pi, pj) < TRIANGULAR_RADIUS {
82                    count += 1;
83                }
84            }
85        }
86        count
87    }
88
89    fn edges(&self) -> Vec<(usize, usize)> {
90        let n = self.positions.len();
91        let mut edges = Vec::new();
92        for i in 0..n {
93            let pi = Self::physical_position(self.positions[i].0, self.positions[i].1);
94            for j in (i + 1)..n {
95                let pj = Self::physical_position(self.positions[j].0, self.positions[j].1);
96                if Self::distance(pi, pj) < TRIANGULAR_RADIUS {
97                    edges.push((i, j));
98                }
99            }
100        }
101        edges
102    }
103
104    fn has_edge(&self, u: usize, v: usize) -> bool {
105        if u >= self.positions.len() || v >= self.positions.len() || u == v {
106            return false;
107        }
108        let pu = Self::physical_position(self.positions[u].0, self.positions[u].1);
109        let pv = Self::physical_position(self.positions[v].0, self.positions[v].1);
110        Self::distance(pu, pv) < TRIANGULAR_RADIUS
111    }
112
113    fn neighbors(&self, v: usize) -> Vec<usize> {
114        if v >= self.positions.len() {
115            return Vec::new();
116        }
117        let pv = Self::physical_position(self.positions[v].0, self.positions[v].1);
118        (0..self.positions.len())
119            .filter(|&u| {
120                u != v && {
121                    let pu = Self::physical_position(self.positions[u].0, self.positions[u].1);
122                    Self::distance(pv, pu) < TRIANGULAR_RADIUS
123                }
124            })
125            .collect()
126    }
127}
128
129impl crate::variant::VariantParam for TriangularSubgraph {
130    const CATEGORY: &'static str = "graph";
131    const VALUE: &'static str = "TriangularSubgraph";
132    const PARENT_VALUE: Option<&'static str> = Some("UnitDiskGraph");
133}
134impl crate::variant::CastToParent for TriangularSubgraph {
135    type Parent = UnitDiskGraph;
136    fn cast_to_parent(&self) -> UnitDiskGraph {
137        let positions: Vec<(f64, f64)> = self
138            .positions
139            .iter()
140            .map(|&(r, c)| Self::physical_position(r, c))
141            .collect();
142        UnitDiskGraph::new(positions, TRIANGULAR_RADIUS)
143    }
144}
problemreductions/topology/triangular_subgraph.rs

problemreductions/topology/
triangular_subgraph.rs
