ruvector_graph/
index.rs

1//! Index structures for fast node and edge lookups
2//!
3//! Provides label indexes, property indexes, and edge type indexes for efficient querying
4
5use crate::edge::Edge;
6use crate::hyperedge::{Hyperedge, HyperedgeId};
7use crate::node::Node;
8use crate::types::{EdgeId, NodeId, PropertyValue};
9use dashmap::DashMap;
10use std::collections::HashSet;
11use std::sync::Arc;
12
13/// Label index for nodes (maps labels to node IDs)
14#[derive(Debug, Clone)]
15pub struct LabelIndex {
16    /// Label -> Set of node IDs
17    index: Arc<DashMap<String, HashSet<NodeId>>>,
18}
19
20impl LabelIndex {
21    /// Create a new label index
22    pub fn new() -> Self {
23        Self {
24            index: Arc::new(DashMap::new()),
25        }
26    }
27
28    /// Add a node to the index
29    pub fn add_node(&self, node: &Node) {
30        for label in &node.labels {
31            self.index
32                .entry(label.name.clone())
33                .or_insert_with(HashSet::new)
34                .insert(node.id.clone());
35        }
36    }
37
38    /// Remove a node from the index
39    pub fn remove_node(&self, node: &Node) {
40        for label in &node.labels {
41            if let Some(mut set) = self.index.get_mut(&label.name) {
42                set.remove(&node.id);
43            }
44        }
45    }
46
47    /// Get all nodes with a specific label
48    pub fn get_nodes_by_label(&self, label: &str) -> Vec<NodeId> {
49        self.index
50            .get(label)
51            .map(|set| set.iter().cloned().collect())
52            .unwrap_or_default()
53    }
54
55    /// Get all labels in the index
56    pub fn all_labels(&self) -> Vec<String> {
57        self.index.iter().map(|entry| entry.key().clone()).collect()
58    }
59
60    /// Count nodes with a specific label
61    pub fn count_by_label(&self, label: &str) -> usize {
62        self.index.get(label).map(|set| set.len()).unwrap_or(0)
63    }
64
65    /// Clear the index
66    pub fn clear(&self) {
67        self.index.clear();
68    }
69}
70
71impl Default for LabelIndex {
72    fn default() -> Self {
73        Self::new()
74    }
75}
76
77/// Property index for nodes (maps property keys to values to node IDs)
78#[derive(Debug, Clone)]
79pub struct PropertyIndex {
80    /// Property key -> Property value -> Set of node IDs
81    index: Arc<DashMap<String, DashMap<String, HashSet<NodeId>>>>,
82}
83
84impl PropertyIndex {
85    /// Create a new property index
86    pub fn new() -> Self {
87        Self {
88            index: Arc::new(DashMap::new()),
89        }
90    }
91
92    /// Add a node to the index
93    pub fn add_node(&self, node: &Node) {
94        for (key, value) in &node.properties {
95            let value_str = self.property_value_to_string(value);
96            self.index
97                .entry(key.clone())
98                .or_insert_with(DashMap::new)
99                .entry(value_str)
100                .or_insert_with(HashSet::new)
101                .insert(node.id.clone());
102        }
103    }
104
105    /// Remove a node from the index
106    pub fn remove_node(&self, node: &Node) {
107        for (key, value) in &node.properties {
108            let value_str = self.property_value_to_string(value);
109            if let Some(value_map) = self.index.get(key) {
110                if let Some(mut set) = value_map.get_mut(&value_str) {
111                    set.remove(&node.id);
112                }
113            }
114        }
115    }
116
117    /// Get nodes by property key-value pair
118    pub fn get_nodes_by_property(&self, key: &str, value: &PropertyValue) -> Vec<NodeId> {
119        let value_str = self.property_value_to_string(value);
120        self.index
121            .get(key)
122            .and_then(|value_map| {
123                value_map
124                    .get(&value_str)
125                    .map(|set| set.iter().cloned().collect())
126            })
127            .unwrap_or_default()
128    }
129
130    /// Get all nodes that have a specific property key (regardless of value)
131    pub fn get_nodes_with_property(&self, key: &str) -> Vec<NodeId> {
132        self.index
133            .get(key)
134            .map(|value_map| {
135                let mut result = HashSet::new();
136                for entry in value_map.iter() {
137                    for id in entry.value().iter() {
138                        result.insert(id.clone());
139                    }
140                }
141                result.into_iter().collect()
142            })
143            .unwrap_or_default()
144    }
145
146    /// Get all property keys in the index
147    pub fn all_property_keys(&self) -> Vec<String> {
148        self.index.iter().map(|entry| entry.key().clone()).collect()
149    }
150
151    /// Clear the index
152    pub fn clear(&self) {
153        self.index.clear();
154    }
155
156    /// Convert property value to string for indexing
157    fn property_value_to_string(&self, value: &PropertyValue) -> String {
158        match value {
159            PropertyValue::Null => "null".to_string(),
160            PropertyValue::Boolean(b) => b.to_string(),
161            PropertyValue::Integer(i) => i.to_string(),
162            PropertyValue::Float(f) => f.to_string(),
163            PropertyValue::String(s) => s.clone(),
164            PropertyValue::Array(_) | PropertyValue::List(_) => format!("{:?}", value),
165            PropertyValue::Map(_) => format!("{:?}", value),
166        }
167    }
168}
169
170impl Default for PropertyIndex {
171    fn default() -> Self {
172        Self::new()
173    }
174}
175
176/// Edge type index (maps edge types to edge IDs)
177#[derive(Debug, Clone)]
178pub struct EdgeTypeIndex {
179    /// Edge type -> Set of edge IDs
180    index: Arc<DashMap<String, HashSet<EdgeId>>>,
181}
182
183impl EdgeTypeIndex {
184    /// Create a new edge type index
185    pub fn new() -> Self {
186        Self {
187            index: Arc::new(DashMap::new()),
188        }
189    }
190
191    /// Add an edge to the index
192    pub fn add_edge(&self, edge: &Edge) {
193        self.index
194            .entry(edge.edge_type.clone())
195            .or_insert_with(HashSet::new)
196            .insert(edge.id.clone());
197    }
198
199    /// Remove an edge from the index
200    pub fn remove_edge(&self, edge: &Edge) {
201        if let Some(mut set) = self.index.get_mut(&edge.edge_type) {
202            set.remove(&edge.id);
203        }
204    }
205
206    /// Get all edges of a specific type
207    pub fn get_edges_by_type(&self, edge_type: &str) -> Vec<EdgeId> {
208        self.index
209            .get(edge_type)
210            .map(|set| set.iter().cloned().collect())
211            .unwrap_or_default()
212    }
213
214    /// Get all edge types
215    pub fn all_edge_types(&self) -> Vec<String> {
216        self.index.iter().map(|entry| entry.key().clone()).collect()
217    }
218
219    /// Count edges of a specific type
220    pub fn count_by_type(&self, edge_type: &str) -> usize {
221        self.index.get(edge_type).map(|set| set.len()).unwrap_or(0)
222    }
223
224    /// Clear the index
225    pub fn clear(&self) {
226        self.index.clear();
227    }
228}
229
230impl Default for EdgeTypeIndex {
231    fn default() -> Self {
232        Self::new()
233    }
234}
235
236/// Adjacency index for fast neighbor lookups
237#[derive(Debug, Clone)]
238pub struct AdjacencyIndex {
239    /// Node ID -> Set of outgoing edge IDs
240    outgoing: Arc<DashMap<NodeId, HashSet<EdgeId>>>,
241    /// Node ID -> Set of incoming edge IDs
242    incoming: Arc<DashMap<NodeId, HashSet<EdgeId>>>,
243}
244
245impl AdjacencyIndex {
246    /// Create a new adjacency index
247    pub fn new() -> Self {
248        Self {
249            outgoing: Arc::new(DashMap::new()),
250            incoming: Arc::new(DashMap::new()),
251        }
252    }
253
254    /// Add an edge to the index
255    pub fn add_edge(&self, edge: &Edge) {
256        self.outgoing
257            .entry(edge.from.clone())
258            .or_insert_with(HashSet::new)
259            .insert(edge.id.clone());
260
261        self.incoming
262            .entry(edge.to.clone())
263            .or_insert_with(HashSet::new)
264            .insert(edge.id.clone());
265    }
266
267    /// Remove an edge from the index
268    pub fn remove_edge(&self, edge: &Edge) {
269        if let Some(mut set) = self.outgoing.get_mut(&edge.from) {
270            set.remove(&edge.id);
271        }
272        if let Some(mut set) = self.incoming.get_mut(&edge.to) {
273            set.remove(&edge.id);
274        }
275    }
276
277    /// Get all outgoing edges from a node
278    pub fn get_outgoing_edges(&self, node_id: &NodeId) -> Vec<EdgeId> {
279        self.outgoing
280            .get(node_id)
281            .map(|set| set.iter().cloned().collect())
282            .unwrap_or_default()
283    }
284
285    /// Get all incoming edges to a node
286    pub fn get_incoming_edges(&self, node_id: &NodeId) -> Vec<EdgeId> {
287        self.incoming
288            .get(node_id)
289            .map(|set| set.iter().cloned().collect())
290            .unwrap_or_default()
291    }
292
293    /// Get all edges connected to a node (both incoming and outgoing)
294    pub fn get_all_edges(&self, node_id: &NodeId) -> Vec<EdgeId> {
295        let mut edges = self.get_outgoing_edges(node_id);
296        edges.extend(self.get_incoming_edges(node_id));
297        edges
298    }
299
300    /// Get degree (number of outgoing edges)
301    pub fn out_degree(&self, node_id: &NodeId) -> usize {
302        self.outgoing.get(node_id).map(|set| set.len()).unwrap_or(0)
303    }
304
305    /// Get in-degree (number of incoming edges)
306    pub fn in_degree(&self, node_id: &NodeId) -> usize {
307        self.incoming.get(node_id).map(|set| set.len()).unwrap_or(0)
308    }
309
310    /// Clear the index
311    pub fn clear(&self) {
312        self.outgoing.clear();
313        self.incoming.clear();
314    }
315}
316
317impl Default for AdjacencyIndex {
318    fn default() -> Self {
319        Self::new()
320    }
321}
322
323/// Hyperedge node index (maps nodes to hyperedges they participate in)
324#[derive(Debug, Clone)]
325pub struct HyperedgeNodeIndex {
326    /// Node ID -> Set of hyperedge IDs
327    index: Arc<DashMap<NodeId, HashSet<HyperedgeId>>>,
328}
329
330impl HyperedgeNodeIndex {
331    /// Create a new hyperedge node index
332    pub fn new() -> Self {
333        Self {
334            index: Arc::new(DashMap::new()),
335        }
336    }
337
338    /// Add a hyperedge to the index
339    pub fn add_hyperedge(&self, hyperedge: &Hyperedge) {
340        for node_id in &hyperedge.nodes {
341            self.index
342                .entry(node_id.clone())
343                .or_insert_with(HashSet::new)
344                .insert(hyperedge.id.clone());
345        }
346    }
347
348    /// Remove a hyperedge from the index
349    pub fn remove_hyperedge(&self, hyperedge: &Hyperedge) {
350        for node_id in &hyperedge.nodes {
351            if let Some(mut set) = self.index.get_mut(node_id) {
352                set.remove(&hyperedge.id);
353            }
354        }
355    }
356
357    /// Get all hyperedges containing a node
358    pub fn get_hyperedges_by_node(&self, node_id: &NodeId) -> Vec<HyperedgeId> {
359        self.index
360            .get(node_id)
361            .map(|set| set.iter().cloned().collect())
362            .unwrap_or_default()
363    }
364
365    /// Clear the index
366    pub fn clear(&self) {
367        self.index.clear();
368    }
369}
370
371impl Default for HyperedgeNodeIndex {
372    fn default() -> Self {
373        Self::new()
374    }
375}
376
377#[cfg(test)]
378mod tests {
379    use super::*;
380    use crate::node::NodeBuilder;
381
382    #[test]
383    fn test_label_index() {
384        let index = LabelIndex::new();
385
386        let node1 = NodeBuilder::new().label("Person").label("User").build();
387
388        let node2 = NodeBuilder::new().label("Person").build();
389
390        index.add_node(&node1);
391        index.add_node(&node2);
392
393        let people = index.get_nodes_by_label("Person");
394        assert_eq!(people.len(), 2);
395
396        let users = index.get_nodes_by_label("User");
397        assert_eq!(users.len(), 1);
398
399        assert_eq!(index.count_by_label("Person"), 2);
400    }
401
402    #[test]
403    fn test_property_index() {
404        let index = PropertyIndex::new();
405
406        let node1 = NodeBuilder::new()
407            .property("name", "Alice")
408            .property("age", 30i64)
409            .build();
410
411        let node2 = NodeBuilder::new()
412            .property("name", "Bob")
413            .property("age", 30i64)
414            .build();
415
416        index.add_node(&node1);
417        index.add_node(&node2);
418
419        let alice =
420            index.get_nodes_by_property("name", &PropertyValue::String("Alice".to_string()));
421        assert_eq!(alice.len(), 1);
422
423        let age_30 = index.get_nodes_by_property("age", &PropertyValue::Integer(30));
424        assert_eq!(age_30.len(), 2);
425
426        let with_age = index.get_nodes_with_property("age");
427        assert_eq!(with_age.len(), 2);
428    }
429
430    #[test]
431    fn test_edge_type_index() {
432        let index = EdgeTypeIndex::new();
433
434        let edge1 = Edge::create("n1".to_string(), "n2".to_string(), "KNOWS");
435        let edge2 = Edge::create("n2".to_string(), "n3".to_string(), "KNOWS");
436        let edge3 = Edge::create("n1".to_string(), "n3".to_string(), "WORKS_WITH");
437
438        index.add_edge(&edge1);
439        index.add_edge(&edge2);
440        index.add_edge(&edge3);
441
442        let knows_edges = index.get_edges_by_type("KNOWS");
443        assert_eq!(knows_edges.len(), 2);
444
445        let works_with_edges = index.get_edges_by_type("WORKS_WITH");
446        assert_eq!(works_with_edges.len(), 1);
447
448        assert_eq!(index.all_edge_types().len(), 2);
449    }
450
451    #[test]
452    fn test_adjacency_index() {
453        let index = AdjacencyIndex::new();
454
455        let edge1 = Edge::create("n1".to_string(), "n2".to_string(), "KNOWS");
456        let edge2 = Edge::create("n1".to_string(), "n3".to_string(), "KNOWS");
457        let edge3 = Edge::create("n2".to_string(), "n1".to_string(), "KNOWS");
458
459        index.add_edge(&edge1);
460        index.add_edge(&edge2);
461        index.add_edge(&edge3);
462
463        assert_eq!(index.out_degree(&"n1".to_string()), 2);
464        assert_eq!(index.in_degree(&"n1".to_string()), 1);
465
466        let outgoing = index.get_outgoing_edges(&"n1".to_string());
467        assert_eq!(outgoing.len(), 2);
468
469        let incoming = index.get_incoming_edges(&"n1".to_string());
470        assert_eq!(incoming.len(), 1);
471    }
472}
ruvector_graph/index.rs

ruvector_graph/
index.rs
