problemreductions/topology/
unit_disk_graph.rs

1//! Unit Disk Graph implementation.
2//!
3//! A unit disk graph (UDG) is a graph where vertices have positions in 2D space,
4//! and two vertices are connected if their distance is at most a threshold (radius).
5
6use super::graph::Graph;
7use crate::registry::ConstructionError;
8use crate::types::i64_to_exact_f64;
9use serde::{Deserialize, Serialize};
10
11/// A unit disk graph with vertices at 2D positions.
12///
13/// Two vertices are connected by an edge if their Euclidean distance
14/// is at most the specified radius.
15///
16/// # Example
17///
18/// ```
19/// use problemreductions::topology::UnitDiskGraph;
20///
21/// // Create a UDG with 3 vertices at positions (0,0), (1,0), (3,0)
22/// // with unit radius (distance <= 1.0 creates an edge)
23/// let udg = UnitDiskGraph::new(
24///     vec![(0.0, 0.0), (1.0, 0.0), (3.0, 0.0)],
25///     1.0,
26/// ).unwrap();
27///
28/// // Vertices 0 and 1 are connected (distance = 1.0)
29/// // Vertex 2 is isolated (distance > 1.0 from both)
30/// assert!(udg.has_edge(0, 1));
31/// assert!(!udg.has_edge(0, 2));
32/// assert!(!udg.has_edge(1, 2));
33/// ```
34#[derive(Debug, Clone, PartialEq, Serialize)]
35pub struct UnitDiskGraph {
36    /// Positions of vertices as (x, y) coordinates.
37    positions: Vec<(f64, f64)>,
38    /// Radius threshold for edge creation.
39    radius: f64,
40    /// Precomputed edges.
41    edges: Vec<(usize, usize)>,
42}
43
44impl UnitDiskGraph {
45    /// Create a new unit disk graph.
46    ///
47    /// # Arguments
48    ///
49    /// * `positions` - 2D coordinates for each vertex
50    /// * `radius` - Maximum distance for an edge to exist
51    pub fn new(positions: Vec<(f64, f64)>, radius: f64) -> Result<Self, ConstructionError> {
52        if !radius.is_finite() {
53            return Err(ConstructionError::NonFiniteFloat(
54                "unit-disk radius must be finite".into(),
55            ));
56        }
57        if radius < 0.0 {
58            return Err(ConstructionError::Conversion(
59                "unit-disk radius must be nonnegative".into(),
60            ));
61        }
62        for (index, &(x, y)) in positions.iter().enumerate() {
63            if !x.is_finite() || !y.is_finite() {
64                return Err(ConstructionError::NonFiniteFloat(format!(
65                    "unit-disk position at index {index} must be finite"
66                )));
67            }
68        }
69        let n = positions.len();
70        let mut edges = Vec::new();
71
72        // Compute all edges based on distance
73        for i in 0..n {
74            for j in (i + 1)..n {
75                if Self::distance(&positions[i], &positions[j])? <= radius {
76                    edges.push((i, j));
77                }
78            }
79        }
80
81        Ok(Self {
82            positions,
83            radius,
84            edges,
85        })
86    }
87
88    /// Create a unit disk graph with radius 1.0.
89    pub fn unit(positions: Vec<(f64, f64)>) -> Result<Self, ConstructionError> {
90        Self::new(positions, 1.0)
91    }
92
93    /// Compute Euclidean distance between two points.
94    fn distance(p1: &(f64, f64), p2: &(f64, f64)) -> Result<f64, ConstructionError> {
95        let dx = p1.0 - p2.0;
96        let dy = p1.1 - p2.1;
97        let distance = (dx * dx + dy * dy).sqrt();
98        distance.is_finite().then_some(distance).ok_or_else(|| {
99            ConstructionError::NonFiniteFloat(
100                "computing a unit-disk distance produced a non-finite value".into(),
101            )
102        })
103    }
104
105    /// Get the number of vertices.
106    pub fn num_vertices(&self) -> usize {
107        self.positions.len()
108    }
109
110    /// Get the number of edges.
111    pub fn num_edges(&self) -> usize {
112        self.edges.len()
113    }
114
115    /// Get the radius threshold.
116    pub fn radius(&self) -> f64 {
117        self.radius
118    }
119
120    /// Get the position of a vertex.
121    pub fn position(&self, v: usize) -> Option<(f64, f64)> {
122        self.positions.get(v).copied()
123    }
124
125    /// Get all positions.
126    pub fn positions(&self) -> &[(f64, f64)] {
127        &self.positions
128    }
129
130    /// Get all edges.
131    pub fn edges(&self) -> &[(usize, usize)] {
132        &self.edges
133    }
134
135    /// Check if an edge exists between two vertices.
136    pub fn has_edge(&self, u: usize, v: usize) -> bool {
137        let (u, v) = if u < v { (u, v) } else { (v, u) };
138        self.edges.contains(&(u, v))
139    }
140
141    /// Get the distance between two vertices.
142    pub fn vertex_distance(&self, u: usize, v: usize) -> Option<f64> {
143        match (self.positions.get(u), self.positions.get(v)) {
144            (Some(p1), Some(p2)) => Some(
145                Self::distance(p1, p2)
146                    .expect("validated unit-disk graph has finite pairwise distances"),
147            ),
148            _ => None,
149        }
150    }
151
152    /// Get all neighbors of a vertex.
153    pub fn neighbors(&self, v: usize) -> Vec<usize> {
154        self.edges
155            .iter()
156            .filter_map(|&(u1, u2)| {
157                if u1 == v {
158                    Some(u2)
159                } else if u2 == v {
160                    Some(u1)
161                } else {
162                    None
163                }
164            })
165            .collect()
166    }
167
168    /// Get the degree of a vertex.
169    pub fn degree(&self, v: usize) -> usize {
170        self.neighbors(v).len()
171    }
172
173    /// Get the bounding box of all positions.
174    pub fn bounding_box(&self) -> Option<((f64, f64), (f64, f64))> {
175        if self.positions.is_empty() {
176            return None;
177        }
178
179        let min_x = self
180            .positions
181            .iter()
182            .map(|p| p.0)
183            .fold(f64::INFINITY, f64::min);
184        let max_x = self
185            .positions
186            .iter()
187            .map(|p| p.0)
188            .fold(f64::NEG_INFINITY, f64::max);
189        let min_y = self
190            .positions
191            .iter()
192            .map(|p| p.1)
193            .fold(f64::INFINITY, f64::min);
194        let max_y = self
195            .positions
196            .iter()
197            .map(|p| p.1)
198            .fold(f64::NEG_INFINITY, f64::max);
199
200        Some(((min_x, min_y), (max_x, max_y)))
201    }
202
203    /// Create a unit disk graph on a regular grid.
204    ///
205    /// # Arguments
206    ///
207    /// * `rows` - Number of rows
208    /// * `cols` - Number of columns
209    /// * `spacing` - Distance between adjacent grid points
210    /// * `radius` - Edge creation threshold
211    pub fn grid(
212        rows: usize,
213        cols: usize,
214        spacing: f64,
215        radius: f64,
216    ) -> Result<Self, ConstructionError> {
217        if !spacing.is_finite() {
218            return Err(ConstructionError::NonFiniteFloat(
219                "unit-disk grid spacing must be finite".into(),
220            ));
221        }
222        let capacity = rows.checked_mul(cols).ok_or_else(|| {
223            ConstructionError::IntegerOverflow("unit-disk grid size exceeds usize".into())
224        })?;
225        let mut positions = Vec::with_capacity(capacity);
226        for r in 0..rows {
227            for c in 0..cols {
228                let c = i64::try_from(c).map_err(|_| {
229                    ConstructionError::IntegerOverflow(
230                        "unit-disk grid column does not fit i64".into(),
231                    )
232                })?;
233                let r = i64::try_from(r).map_err(|_| {
234                    ConstructionError::IntegerOverflow("unit-disk grid row does not fit i64".into())
235                })?;
236                let x = i64_to_exact_f64(c)? * spacing;
237                let y = i64_to_exact_f64(r)? * spacing;
238                if !x.is_finite() || !y.is_finite() {
239                    return Err(ConstructionError::NonFiniteFloat(
240                        "computing unit-disk grid coordinates produced a non-finite value".into(),
241                    ));
242                }
243                positions.push((x, y));
244            }
245        }
246        Self::new(positions, radius)
247    }
248}
249
250impl<'de> Deserialize<'de> for UnitDiskGraph {
251    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
252    where
253        D: serde::Deserializer<'de>,
254    {
255        #[derive(Deserialize)]
256        struct Raw {
257            positions: Vec<(f64, f64)>,
258            radius: f64,
259            edges: Vec<(usize, usize)>,
260        }
261
262        let raw = Raw::deserialize(deserializer)?;
263        let graph = Self::new(raw.positions, raw.radius).map_err(serde::de::Error::custom)?;
264        if graph.edges != raw.edges {
265            return Err(serde::de::Error::custom(
266                "unit-disk edges do not match positions and radius",
267            ));
268        }
269        Ok(graph)
270    }
271}
272
273impl Graph for UnitDiskGraph {
274    const NAME: &'static str = "UnitDiskGraph";
275
276    fn num_vertices(&self) -> usize {
277        self.positions.len()
278    }
279
280    fn num_edges(&self) -> usize {
281        self.edges.len()
282    }
283
284    fn edges(&self) -> Vec<(usize, usize)> {
285        self.edges.clone()
286    }
287
288    fn has_edge(&self, u: usize, v: usize) -> bool {
289        let (u, v) = if u < v { (u, v) } else { (v, u) };
290        self.edges.contains(&(u, v))
291    }
292
293    fn neighbors(&self, v: usize) -> Vec<usize> {
294        self.edges
295            .iter()
296            .filter_map(|&(u1, u2)| {
297                if u1 == v {
298                    Some(u2)
299                } else if u2 == v {
300                    Some(u1)
301                } else {
302                    None
303                }
304            })
305            .collect()
306    }
307}
308
309use crate::impl_variant_param;
310impl_variant_param!(UnitDiskGraph, "graph");
311
312#[cfg(test)]
313#[path = "../unit_tests/topology/unit_disk_graph.rs"]
314mod tests;
problemreductions/topology/unit_disk_graph.rs

problemreductions/topology/
unit_disk_graph.rs
