Skip to main content

bifrost/
graph.rs

1use crate::{Error, Result};
2
3/// Caller-facing identifier stored with each vector.
4///
5/// Chosen by [`crate::HnswIndex::insert`]. [`crate::HnswIndex::build`] assigns
6/// dense values `0..n-1`. IDs stay unique for the life of the index; there is
7/// no delete API that would free one.
8pub type ExternalId = u32;
9
10/// Dense internal node index, assigned in insertion order (`0..n-1`).
11///
12/// Used by [`Graph`] accessors and [`crate::HnswIndex::entry_point`]. Distinct
13/// from [`ExternalId`].
14pub type NodeIndex = u32;
15
16/// Per-node metadata stored in the construction graph and on disk.
17#[derive(Clone, Copy, Debug, PartialEq, Eq)]
18pub struct NodeMeta {
19    /// Caller-facing ID for this node.
20    pub external_id: ExternalId,
21    /// Highest layer this node occupies. The node has adjacency slots on
22    /// layers `0..=level`.
23    pub level: u8,
24    /// Start of the node's vector in the packed `f32` store, as an element
25    /// index (not a byte offset). The on-disk layout uses the same unit:
26    /// multiply by 4 to reach the vector section.
27    pub vector_offset: u32,
28}
29
30/// Per-layer graph used while constructing an index.
31///
32/// Inspect a live index through [`crate::HnswIndex::graph`] or the index's
33/// read-only accessors. The graph stored on an index cannot be replaced, and
34/// mutation methods here are crate-private so external callers cannot desync
35/// adjacency from vectors.
36///
37/// Adjacency lists are directed. Insertion adds both directed edges atomically
38/// (a reverse-edge failure undoes the forward write), then reverse links are
39/// pruned on the neighbor only, so a dropped `A → B` edge can leave `B → A`
40/// in place.
41#[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    /// Empty construction graph: no nodes and no layers.
58    #[must_use]
59    pub fn new() -> Self {
60        Self::default()
61    }
62
63    /// Converts a node-list length to [`NodeIndex`] without panicking.
64    ///
65    /// Insertion rejects a further node when `len` is already [`u32::MAX`], so
66    /// a well-formed graph has at most that many nodes (`0..=u32::MAX - 1`)
67    /// and [`Graph::node_count`] stays exact. If that cap is bypassed, the
68    /// count saturates instead of panicking on the public accessor.
69    #[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    /// `true` when another insert cannot keep the node count in [`u32`].
75    ///
76    /// `len` is the next [`NodeIndex`]. `len == u32::MAX` already holds
77    /// indices `0..=u32::MAX - 1`; that further insert is rejected. Index
78    /// [`u32::MAX`] is unused because the resulting count would be `2^32`,
79    /// which does not fit in [`Graph::node_count`] or the on-disk header,
80    /// and search sizes the visited list from that count so the extra node
81    /// would be skipped.
82    #[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    /// Outgoing neighbors of `node_index` at `level`.
123    ///
124    /// Empty when the node is missing or `node.level < level`. The slice is
125    /// sorted and unique. Adjacency is directed: reverse-link prune drops an
126    /// outgoing edge on one node and leaves the peer's reverse edge in place,
127    /// so `edges(level, a)` containing `b` does not imply the reverse.
128    #[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    /// Adds both directed edges, or neither if the reverse write fails.
188    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    /// Replaces an adjacency list without re-validating neighbors.
207    ///
208    /// Used to restore a snapshot taken before insert mutations. `edges` must
209    /// already be sorted and unique.
210    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    /// Drops the most recently inserted node and any layers allocated for it.
221    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    /// Number of nodes in the construction graph.
262    ///
263    /// After a successful insert the value is exact and at most [`u32::MAX`]
264    /// (indices `0..=u32::MAX - 1`). If the `u32` cap is bypassed, this
265    /// saturates at [`u32::MAX`] instead of panicking.
266    #[must_use]
267    pub fn node_count(&self) -> NodeIndex {
268        Self::node_index_from_len(self.node_data.len())
269    }
270
271    /// Number of allocated layers (highest assigned node level plus one).
272    ///
273    /// `0` on an empty graph.
274    #[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    /// Metadata for a dense internal node, if `node_index` exists.
281    #[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    /// Whether a directed edge exists from `source` to `destination` at `level`.
287    ///
288    /// This is a membership test on [`Graph::edges`]. A dropped reverse link
289    /// can make the relation one-sided.
290    #[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        // Last legal NodeIndex (`u32::MAX - 1`) is usable: `len == u32::MAX`
412        // is a full graph (`0..=u32::MAX - 1`). Index `u32::MAX` is unused
413        // so the u32 count stays exact (see `node_len_at_u32_cap`).
414        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}