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 serde::{Deserialize, Serialize};
8
9/// A unit disk graph with vertices at 2D positions.
10///
11/// Two vertices are connected by an edge if their Euclidean distance
12/// is at most the specified radius.
13///
14/// # Example
15///
16/// ```
17/// use problemreductions::topology::UnitDiskGraph;
18///
19/// // Create a UDG with 3 vertices at positions (0,0), (1,0), (3,0)
20/// // with unit radius (distance <= 1.0 creates an edge)
21/// let udg = UnitDiskGraph::new(
22///     vec![(0.0, 0.0), (1.0, 0.0), (3.0, 0.0)],
23///     1.0,
24/// );
25///
26/// // Vertices 0 and 1 are connected (distance = 1.0)
27/// // Vertex 2 is isolated (distance > 1.0 from both)
28/// assert!(udg.has_edge(0, 1));
29/// assert!(!udg.has_edge(0, 2));
30/// assert!(!udg.has_edge(1, 2));
31/// ```
32#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
33pub struct UnitDiskGraph {
34    /// Positions of vertices as (x, y) coordinates.
35    positions: Vec<(f64, f64)>,
36    /// Radius threshold for edge creation.
37    radius: f64,
38    /// Precomputed edges.
39    edges: Vec<(usize, usize)>,
40}
41
42impl UnitDiskGraph {
43    /// Create a new unit disk graph.
44    ///
45    /// # Arguments
46    ///
47    /// * `positions` - 2D coordinates for each vertex
48    /// * `radius` - Maximum distance for an edge to exist
49    pub fn new(positions: Vec<(f64, f64)>, radius: f64) -> Self {
50        let n = positions.len();
51        let mut edges = Vec::new();
52
53        // Compute all edges based on distance
54        for i in 0..n {
55            for j in (i + 1)..n {
56                if Self::distance(&positions[i], &positions[j]) <= radius {
57                    edges.push((i, j));
58                }
59            }
60        }
61
62        Self {
63            positions,
64            radius,
65            edges,
66        }
67    }
68
69    /// Create a unit disk graph with radius 1.0.
70    pub fn unit(positions: Vec<(f64, f64)>) -> Self {
71        Self::new(positions, 1.0)
72    }
73
74    /// Compute Euclidean distance between two points.
75    fn distance(p1: &(f64, f64), p2: &(f64, f64)) -> f64 {
76        let dx = p1.0 - p2.0;
77        let dy = p1.1 - p2.1;
78        (dx * dx + dy * dy).sqrt()
79    }
80
81    /// Get the number of vertices.
82    pub fn num_vertices(&self) -> usize {
83        self.positions.len()
84    }
85
86    /// Get the number of edges.
87    pub fn num_edges(&self) -> usize {
88        self.edges.len()
89    }
90
91    /// Get the radius threshold.
92    pub fn radius(&self) -> f64 {
93        self.radius
94    }
95
96    /// Get the position of a vertex.
97    pub fn position(&self, v: usize) -> Option<(f64, f64)> {
98        self.positions.get(v).copied()
99    }
100
101    /// Get all positions.
102    pub fn positions(&self) -> &[(f64, f64)] {
103        &self.positions
104    }
105
106    /// Get all edges.
107    pub fn edges(&self) -> &[(usize, usize)] {
108        &self.edges
109    }
110
111    /// Check if an edge exists between two vertices.
112    pub fn has_edge(&self, u: usize, v: usize) -> bool {
113        let (u, v) = if u < v { (u, v) } else { (v, u) };
114        self.edges.contains(&(u, v))
115    }
116
117    /// Get the distance between two vertices.
118    pub fn vertex_distance(&self, u: usize, v: usize) -> Option<f64> {
119        match (self.positions.get(u), self.positions.get(v)) {
120            (Some(p1), Some(p2)) => Some(Self::distance(p1, p2)),
121            _ => None,
122        }
123    }
124
125    /// Get all neighbors of a vertex.
126    pub fn neighbors(&self, v: usize) -> Vec<usize> {
127        self.edges
128            .iter()
129            .filter_map(|&(u1, u2)| {
130                if u1 == v {
131                    Some(u2)
132                } else if u2 == v {
133                    Some(u1)
134                } else {
135                    None
136                }
137            })
138            .collect()
139    }
140
141    /// Get the degree of a vertex.
142    pub fn degree(&self, v: usize) -> usize {
143        self.neighbors(v).len()
144    }
145
146    /// Get the bounding box of all positions.
147    pub fn bounding_box(&self) -> Option<((f64, f64), (f64, f64))> {
148        if self.positions.is_empty() {
149            return None;
150        }
151
152        let min_x = self
153            .positions
154            .iter()
155            .map(|p| p.0)
156            .fold(f64::INFINITY, f64::min);
157        let max_x = self
158            .positions
159            .iter()
160            .map(|p| p.0)
161            .fold(f64::NEG_INFINITY, f64::max);
162        let min_y = self
163            .positions
164            .iter()
165            .map(|p| p.1)
166            .fold(f64::INFINITY, f64::min);
167        let max_y = self
168            .positions
169            .iter()
170            .map(|p| p.1)
171            .fold(f64::NEG_INFINITY, f64::max);
172
173        Some(((min_x, min_y), (max_x, max_y)))
174    }
175
176    /// Create a unit disk graph on a regular grid.
177    ///
178    /// # Arguments
179    ///
180    /// * `rows` - Number of rows
181    /// * `cols` - Number of columns
182    /// * `spacing` - Distance between adjacent grid points
183    /// * `radius` - Edge creation threshold
184    pub fn grid(rows: usize, cols: usize, spacing: f64, radius: f64) -> Self {
185        let mut positions = Vec::with_capacity(rows * cols);
186        for r in 0..rows {
187            for c in 0..cols {
188                positions.push((c as f64 * spacing, r as f64 * spacing));
189            }
190        }
191        Self::new(positions, radius)
192    }
193}
194
195impl Graph for UnitDiskGraph {
196    const NAME: &'static str = "UnitDiskGraph";
197
198    fn num_vertices(&self) -> usize {
199        self.positions.len()
200    }
201
202    fn num_edges(&self) -> usize {
203        self.edges.len()
204    }
205
206    fn edges(&self) -> Vec<(usize, usize)> {
207        self.edges.clone()
208    }
209
210    fn has_edge(&self, u: usize, v: usize) -> bool {
211        let (u, v) = if u < v { (u, v) } else { (v, u) };
212        self.edges.contains(&(u, v))
213    }
214
215    fn neighbors(&self, v: usize) -> Vec<usize> {
216        self.edges
217            .iter()
218            .filter_map(|&(u1, u2)| {
219                if u1 == v {
220                    Some(u2)
221                } else if u2 == v {
222                    Some(u1)
223                } else {
224                    None
225                }
226            })
227            .collect()
228    }
229}
230
231use super::graph::SimpleGraph;
232use crate::impl_variant_param;
233impl_variant_param!(UnitDiskGraph, "graph", parent: SimpleGraph,
234    cast: |g| SimpleGraph::new(g.num_vertices(), Graph::edges(g)));
235
236#[cfg(test)]
237#[path = "../unit_tests/topology/unit_disk_graph.rs"]
238mod tests;
problemreductions/topology/unit_disk_graph.rs

problemreductions/topology/
unit_disk_graph.rs
