1use crate::{Error, Result};
2
3pub type ExternalId = u32;
9
10pub type NodeIndex = u32;
15
16#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub struct NodeMeta {
19 pub external_id: ExternalId,
21 pub level: u8,
24 pub vector_offset: u32,
28}
29
30#[derive(Clone, Debug, Default)]
42pub struct Graph {
43 pub(crate) node_data: Vec<NodeMeta>,
44 construction_layers: Vec<Vec<Vec<NodeIndex>>>,
45 #[cfg(test)]
46 fail_add_edge_from: Option<NodeIndex>,
47}
48
49#[cfg(test)]
50impl Graph {
51 pub(crate) fn fail_next_add_edge_from(&mut self, source: NodeIndex) {
52 self.fail_add_edge_from = Some(source);
53 }
54}
55
56impl Graph {
57 #[must_use]
59 pub fn new() -> Self {
60 Self::default()
61 }
62
63 #[must_use]
70 pub(crate) fn node_index_from_len(len: usize) -> NodeIndex {
71 u32::try_from(len).unwrap_or(u32::MAX)
72 }
73
74 #[must_use]
83 pub(crate) fn node_len_at_u32_cap(len: usize) -> bool {
84 len >= u32::MAX as usize
85 }
86
87 fn check_insert_node(len: usize, node_index: NodeIndex) -> Result<()> {
88 if Self::node_len_at_u32_cap(len) {
89 return Err(Error::CapacityExceeded("node count"));
90 }
91 if node_index != Self::node_index_from_len(len) {
92 return Err(Error::InvalidNode(node_index));
93 }
94 Ok(())
95 }
96
97 pub(crate) fn insert_node(
98 &mut self,
99 node_index: NodeIndex,
100 external_id: ExternalId,
101 level: u8,
102 vector_offset: u32,
103 ) -> Result<()> {
104 Self::check_insert_node(self.node_data.len(), node_index)?;
105
106 let old_node_count = self.node_data.len();
107 while self.construction_layers.len() <= usize::from(level) {
108 self.construction_layers
109 .push(vec![Vec::new(); old_node_count]);
110 }
111 for layer in &mut self.construction_layers {
112 layer.push(Vec::new());
113 }
114 self.node_data.push(NodeMeta {
115 external_id,
116 level,
117 vector_offset,
118 });
119 Ok(())
120 }
121
122 #[must_use]
129 pub fn edges(&self, level: u8, node_index: NodeIndex) -> &[NodeIndex] {
130 let Some(node) = self.node(node_index) else {
131 return &[];
132 };
133 if node.level < level {
134 return &[];
135 }
136 self.construction_layers
137 .get(usize::from(level))
138 .and_then(|layer| layer.get(node_index as usize))
139 .map_or(&[], Vec::as_slice)
140 }
141
142 pub(crate) fn add_edge(
143 &mut self,
144 level: u8,
145 source: NodeIndex,
146 destination: NodeIndex,
147 ) -> Result<bool> {
148 let Some(source_meta) = self.node(source) else {
149 return Err(Error::InvalidNode(source));
150 };
151 let Some(destination_meta) = self.node(destination) else {
152 return Err(Error::InvalidNode(destination));
153 };
154 if source_meta.level < level || destination_meta.level < level {
155 return Err(Error::InvalidLayer(level));
156 }
157 let Some(layer) = self.construction_layers.get_mut(usize::from(level)) else {
158 return Err(Error::InvalidLayer(level));
159 };
160 #[cfg(test)]
161 if self.fail_add_edge_from == Some(source) {
162 self.fail_add_edge_from = None;
163 return Err(Error::InvalidNode(source));
164 }
165 let edges = &mut layer[source as usize];
166 Ok(match edges.binary_search(&destination) {
167 Ok(_) => false,
168 Err(position) => {
169 edges.insert(position, destination);
170 true
171 }
172 })
173 }
174
175 pub(crate) fn remove_edge(&mut self, level: u8, source: NodeIndex, destination: NodeIndex) {
176 let Some(layer) = self.construction_layers.get_mut(usize::from(level)) else {
177 return;
178 };
179 let Some(edges) = layer.get_mut(source as usize) else {
180 return;
181 };
182 if let Ok(position) = edges.binary_search(&destination) {
183 edges.remove(position);
184 }
185 }
186
187 pub(crate) fn add_bidirectional_edge(
189 &mut self,
190 level: u8,
191 left: NodeIndex,
192 right: NodeIndex,
193 ) -> Result<()> {
194 let added_forward = self.add_edge(level, left, right)?;
195 match self.add_edge(level, right, left) {
196 Ok(_) => Ok(()),
197 Err(error) => {
198 if added_forward {
199 self.remove_edge(level, left, right);
200 }
201 Err(error)
202 }
203 }
204 }
205
206 pub(crate) fn replace_edges(&mut self, level: u8, source: NodeIndex, edges: Vec<NodeIndex>) {
211 let Some(layer) = self.construction_layers.get_mut(usize::from(level)) else {
212 return;
213 };
214 let Some(slot) = layer.get_mut(source as usize) else {
215 return;
216 };
217 *slot = edges;
218 }
219
220 pub(crate) fn pop_last_node(&mut self, previous_layer_count: u8) {
222 let _ = self.node_data.pop();
223 for layer in &mut self.construction_layers {
224 let _ = layer.pop();
225 }
226 self.construction_layers
227 .truncate(usize::from(previous_layer_count));
228 }
229
230 pub(crate) fn set_edges(
231 &mut self,
232 level: u8,
233 source: NodeIndex,
234 neighbors: impl IntoIterator<Item = NodeIndex>,
235 ) -> Result<()> {
236 let Some(source_meta) = self.node(source) else {
237 return Err(Error::InvalidNode(source));
238 };
239 if source_meta.level < level {
240 return Err(Error::InvalidLayer(level));
241 }
242 if usize::from(level) >= self.construction_layers.len() {
243 return Err(Error::InvalidLayer(level));
244 }
245
246 let mut edges = neighbors.into_iter().collect::<Vec<_>>();
247 edges.sort_unstable();
248 edges.dedup();
249 for &destination in &edges {
250 let Some(destination_meta) = self.node(destination) else {
251 return Err(Error::InvalidNode(destination));
252 };
253 if destination_meta.level < level {
254 return Err(Error::InvalidLayer(level));
255 }
256 }
257 self.construction_layers[usize::from(level)][source as usize] = edges;
258 Ok(())
259 }
260
261 #[must_use]
267 pub fn node_count(&self) -> NodeIndex {
268 Self::node_index_from_len(self.node_data.len())
269 }
270
271 #[must_use]
275 pub fn layer_count(&self) -> u8 {
276 u8::try_from(self.construction_layers.len())
277 .expect("layer count cannot exceed the u8 node level range")
278 }
279
280 #[must_use]
282 pub fn node(&self, node_index: NodeIndex) -> Option<NodeMeta> {
283 self.node_data.get(node_index as usize).copied()
284 }
285
286 #[must_use]
291 pub fn has_edge(&self, level: u8, source: NodeIndex, destination: NodeIndex) -> bool {
292 self.edges(level, source)
293 .binary_search(&destination)
294 .is_ok()
295 }
296}
297
298#[cfg(test)]
299mod tests {
300 use super::*;
301
302 #[test]
303 fn inserts_dense_nodes_and_allocates_layers() {
304 let mut graph = Graph::new();
305 graph.insert_node(0, 100, 3, 0).unwrap();
306 graph.insert_node(1, 200, 2, 100).unwrap();
307 assert_eq!(graph.node_count(), 2);
308 assert_eq!(graph.layer_count(), 4);
309 assert_eq!(graph.node(0).unwrap().external_id, 100);
310 }
311
312 #[test]
313 fn adjacency_is_sorted_duplicate_free_and_per_layer() {
314 let mut graph = Graph::new();
315 for node in 0..3 {
316 graph.insert_node(node, node + 10, 1, node).unwrap();
317 }
318 graph.add_edge(0, 0, 2).unwrap();
319 graph.add_edge(0, 0, 1).unwrap();
320 graph.add_edge(0, 0, 2).unwrap();
321 graph.add_edge(1, 0, 2).unwrap();
322 assert_eq!(graph.edges(0, 0), &[1, 2]);
323 assert_eq!(graph.edges(1, 0), &[2]);
324 }
325
326 #[test]
327 fn rejects_edges_above_either_node_level() {
328 let mut graph = Graph::new();
329 graph.insert_node(0, 10, 1, 0).unwrap();
330 graph.insert_node(1, 11, 0, 1).unwrap();
331 assert!(matches!(
332 graph.add_edge(1, 0, 1),
333 Err(Error::InvalidLayer(1))
334 ));
335 assert!(graph.edges(1, 1).is_empty());
336 }
337
338 #[test]
339 fn bidirectional_edges_are_visible_from_both_nodes() {
340 let mut graph = Graph::new();
341 graph.insert_node(0, 10, 0, 0).unwrap();
342 graph.insert_node(1, 11, 0, 1).unwrap();
343 graph.add_bidirectional_edge(0, 0, 1).unwrap();
344 assert!(graph.has_edge(0, 0, 1));
345 assert!(graph.has_edge(0, 1, 0));
346 }
347
348 #[test]
349 fn set_edges_replaces_with_sorted_unique_neighbors() {
350 let mut graph = Graph::new();
351 for node in 0..4 {
352 graph.insert_node(node, node + 10, 0, node).unwrap();
353 }
354 graph.add_edge(0, 0, 1).unwrap();
355 graph.add_edge(0, 0, 2).unwrap();
356 graph.add_edge(0, 0, 3).unwrap();
357 graph.set_edges(0, 0, [3, 1, 3]).unwrap();
358 assert_eq!(graph.edges(0, 0), &[1, 3]);
359 assert!(matches!(
360 graph.set_edges(0, 0, [5]),
361 Err(Error::InvalidNode(5))
362 ));
363 }
364
365 #[test]
366 fn bidirectional_edge_is_atomic_when_reverse_fails() {
367 let mut graph = Graph::new();
368 graph.insert_node(0, 10, 0, 0).unwrap();
369 graph.insert_node(1, 11, 0, 1).unwrap();
370 graph.fail_add_edge_from = Some(1);
371 assert!(matches!(
372 graph.add_bidirectional_edge(0, 0, 1),
373 Err(Error::InvalidNode(1))
374 ));
375 assert!(!graph.has_edge(0, 0, 1));
376 assert!(!graph.has_edge(0, 1, 0));
377 assert_eq!(graph.fail_add_edge_from, None);
378
379 graph.add_edge(0, 0, 1).unwrap();
380 graph.fail_add_edge_from = Some(1);
381 assert!(matches!(
382 graph.add_bidirectional_edge(0, 0, 1),
383 Err(Error::InvalidNode(1))
384 ));
385 assert!(
386 graph.has_edge(0, 0, 1),
387 "pre-existing forward edge must survive undo"
388 );
389 assert!(!graph.has_edge(0, 1, 0));
390 }
391
392 #[test]
393 fn node_index_from_len_saturates_above_u32_max() {
394 assert_eq!(Graph::node_index_from_len(0), 0);
395 assert_eq!(Graph::node_index_from_len(1), 1);
396 assert_eq!(Graph::node_index_from_len(u32::MAX as usize), u32::MAX);
397 if let Some(over) = (u32::MAX as usize).checked_add(1) {
398 assert_eq!(Graph::node_index_from_len(over), u32::MAX);
399 }
400 }
401
402 #[test]
403 fn insert_node_rejects_u32_capacity_without_allocating() {
404 assert!(!Graph::node_len_at_u32_cap(0));
405 assert!(!Graph::node_len_at_u32_cap(u32::MAX as usize - 1));
406 assert!(Graph::node_len_at_u32_cap(u32::MAX as usize));
407 if let Some(over) = (u32::MAX as usize).checked_add(1) {
408 assert!(Graph::node_len_at_u32_cap(over));
409 }
410
411 assert_eq!(
415 Graph::node_index_from_len(u32::MAX as usize - 1),
416 u32::MAX - 1
417 );
418 Graph::check_insert_node(u32::MAX as usize - 1, u32::MAX - 1).unwrap();
419 assert!(matches!(
420 Graph::check_insert_node(u32::MAX as usize, u32::MAX),
421 Err(Error::CapacityExceeded("node count"))
422 ));
423 assert!(matches!(
424 Graph::check_insert_node(u32::MAX as usize, 0),
425 Err(Error::CapacityExceeded("node count"))
426 ));
427 if let Some(over) = (u32::MAX as usize).checked_add(1) {
428 assert!(matches!(
429 Graph::check_insert_node(over, u32::MAX),
430 Err(Error::CapacityExceeded("node count"))
431 ));
432 }
433 assert!(matches!(
434 Graph::check_insert_node(2, 3),
435 Err(Error::InvalidNode(3))
436 ));
437 Graph::check_insert_node(2, 2).unwrap();
438 }
439
440 #[test]
441 fn pop_last_node_restores_layer_count() {
442 let mut graph = Graph::new();
443 graph.insert_node(0, 10, 0, 0).unwrap();
444 graph.insert_node(1, 11, 3, 1).unwrap();
445 assert_eq!(graph.layer_count(), 4);
446 graph.pop_last_node(1);
447 assert_eq!(graph.node_count(), 1);
448 assert_eq!(graph.layer_count(), 1);
449 assert_eq!(graph.node(0).unwrap().external_id, 10);
450 assert!(graph.node(1).is_none());
451 }
452}