nodedb_vector/vamana/
graph.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Vamana graph structure — adjacency-only, no vector data stored here.
4//!
5//! Vectors are held in the codec layer (RAM, compressed) and on SSD
6//! (full-precision). The graph holds only the degree-bounded adjacency list
7//! and the external ID mapping.
8
9/// A single node in the Vamana graph.
10///
11/// The graph index (`usize`) is the node's position in `VamanaGraph::nodes`.
12/// `id` is the caller-supplied external identifier (e.g. row ID).
13/// `neighbors` is capped at `VamanaGraph::r` entries.
14pub struct VamanaNode {
15    /// External identifier supplied by the caller.
16    pub id: u64,
17    /// Adjacency list — indices into `VamanaGraph::nodes`, length ≤ `r`.
18    pub neighbors: Vec<u32>,
19}
20
21/// Vamana graph index.
22///
23/// Holds only adjacency data; vector values are not stored here.
24/// Use `build::build_vamana` to populate from a vector slice.
25pub struct VamanaGraph {
26    /// Vector dimensionality (informational; not enforced here).
27    pub dim: usize,
28    /// Maximum out-degree per node (typical: 64).
29    pub r: usize,
30    /// α-pruning factor (typical: 1.2). Stored for reference; pruning logic
31    /// lives in `prune::alpha_prune`.
32    pub alpha: f32,
33    /// Index of the entry-point node (typically the medoid).
34    pub entry: usize,
35    /// Dense node storage indexed by insertion order.
36    nodes: Vec<VamanaNode>,
37}
38
39impl VamanaGraph {
40    /// Create an empty graph with the given parameters.
41    pub fn new(dim: usize, r: usize, alpha: f32) -> Self {
42        Self {
43            dim,
44            r,
45            alpha,
46            entry: 0,
47            nodes: Vec::new(),
48        }
49    }
50
51    /// Number of nodes in the graph.
52    pub fn len(&self) -> usize {
53        self.nodes.len()
54    }
55
56    /// Returns `true` if the graph has no nodes.
57    pub fn is_empty(&self) -> bool {
58        self.nodes.is_empty()
59    }
60
61    /// Add a node with the given external ID; returns its internal index.
62    pub fn add_node(&mut self, id: u64) -> usize {
63        let idx = self.nodes.len();
64        self.nodes.push(VamanaNode {
65            id,
66            neighbors: Vec::new(),
67        });
68        idx
69    }
70
71    /// Replace the adjacency list for the node at `idx`.
72    ///
73    /// Truncates `neighbors` to at most `self.r` entries.
74    pub fn set_neighbors(&mut self, idx: usize, mut neighbors: Vec<u32>) {
75        neighbors.truncate(self.r);
76        self.nodes[idx].neighbors = neighbors;
77    }
78
79    /// Immutable view of the adjacency list for the node at `idx`.
80    pub fn neighbors(&self, idx: usize) -> &[u32] {
81        &self.nodes[idx].neighbors
82    }
83
84    /// External ID of the node at `idx`.
85    pub fn external_id(&self, idx: usize) -> u64 {
86        self.nodes[idx].id
87    }
88
89    /// Iterate over all nodes as `(internal_index, &VamanaNode)`.
90    pub fn iter(&self) -> impl Iterator<Item = (usize, &VamanaNode)> {
91        self.nodes.iter().enumerate()
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn add_nodes_len_matches() {
101        let mut g = VamanaGraph::new(8, 4, 1.2);
102        assert_eq!(g.len(), 0);
103        assert!(g.is_empty());
104
105        let i0 = g.add_node(100);
106        let i1 = g.add_node(200);
107        let i2 = g.add_node(300);
108
109        assert_eq!(g.len(), 3);
110        assert!(!g.is_empty());
111        assert_eq!(i0, 0);
112        assert_eq!(i1, 1);
113        assert_eq!(i2, 2);
114    }
115
116    #[test]
117    fn set_and_get_neighbors() {
118        let mut g = VamanaGraph::new(8, 4, 1.2);
119        g.add_node(10);
120        g.add_node(20);
121        g.add_node(30);
122
123        g.set_neighbors(0, vec![1, 2]);
124        assert_eq!(g.neighbors(0), &[1, 2]);
125        assert_eq!(g.neighbors(1), &[] as &[u32]);
126    }
127
128    #[test]
129    fn set_neighbors_respects_degree_bound() {
130        let r = 3;
131        let mut g = VamanaGraph::new(4, r, 1.2);
132        for id in 0..10 {
133            g.add_node(id);
134        }
135        // Provide more neighbors than R; they should be truncated.
136        g.set_neighbors(0, vec![1, 2, 3, 4, 5]);
137        assert_eq!(g.neighbors(0).len(), r);
138    }
139
140    #[test]
141    fn external_id_roundtrip() {
142        let mut g = VamanaGraph::new(4, 8, 1.2);
143        g.add_node(9999);
144        assert_eq!(g.external_id(0), 9999);
145    }
146}
nodedb_vector/vamana/graph.rs

nodedb_vector/vamana/
graph.rs
