Skip to main content

ruvector_delta_graph/
lib.rs

1//! # RuVector Delta Graph
2//!
3//! Delta operations for graph structures, supporting incremental updates
4//! to edges and node properties.
5//!
6//! ## Key Features
7//!
8//! - Edge delta operations (add, remove, update weight)
9//! - Node property deltas (including vector properties)
10//! - Delta-aware graph traversal
11//! - Efficient batch updates
12
13#![allow(missing_docs)]
14#![allow(clippy::all)]
15
16pub mod edge_delta;
17pub mod error;
18pub mod node_delta;
19pub mod traversal;
20
21use std::collections::{HashMap, HashSet};
22
23use ruvector_delta_core::{Delta, DeltaStream, VectorDelta};
24use smallvec::SmallVec;
25
26pub use edge_delta::{EdgeDelta, EdgeOp};
27pub use error::{GraphDeltaError, Result};
28pub use node_delta::{NodeDelta, PropertyDelta};
29pub use traversal::{DeltaAwareTraversal, TraversalMode};
30
31/// A node ID type
32pub type NodeId = String;
33
34/// An edge ID type
35pub type EdgeId = String;
36
37/// Property value types
38#[derive(Debug, Clone, PartialEq)]
39pub enum PropertyValue {
40    /// Null/missing value
41    Null,
42    /// Boolean
43    Bool(bool),
44    /// Integer
45    Int(i64),
46    /// Float
47    Float(f64),
48    /// String
49    String(String),
50    /// Vector (for embeddings)
51    Vector(Vec<f32>),
52    /// List of values
53    List(Vec<PropertyValue>),
54    /// Map of values
55    Map(HashMap<String, PropertyValue>),
56}
57
58impl Default for PropertyValue {
59    fn default() -> Self {
60        Self::Null
61    }
62}
63
64/// A graph delta representing changes to graph structure
65#[derive(Debug, Clone)]
66pub struct GraphDelta {
67    /// Node additions
68    pub node_adds: Vec<(NodeId, HashMap<String, PropertyValue>)>,
69    /// Node removals
70    pub node_removes: Vec<NodeId>,
71    /// Node property updates
72    pub node_updates: Vec<(NodeId, NodeDelta)>,
73    /// Edge additions
74    pub edge_adds: Vec<EdgeAddition>,
75    /// Edge removals
76    pub edge_removes: Vec<EdgeId>,
77    /// Edge updates
78    pub edge_updates: Vec<(EdgeId, EdgeDelta)>,
79}
80
81/// An edge addition
82#[derive(Debug, Clone)]
83pub struct EdgeAddition {
84    /// Edge ID
85    pub id: EdgeId,
86    /// Source node
87    pub source: NodeId,
88    /// Target node
89    pub target: NodeId,
90    /// Edge type/label
91    pub edge_type: String,
92    /// Edge properties
93    pub properties: HashMap<String, PropertyValue>,
94}
95
96impl GraphDelta {
97    /// Create an empty graph delta
98    pub fn new() -> Self {
99        Self {
100            node_adds: Vec::new(),
101            node_removes: Vec::new(),
102            node_updates: Vec::new(),
103            edge_adds: Vec::new(),
104            edge_removes: Vec::new(),
105            edge_updates: Vec::new(),
106        }
107    }
108
109    /// Check if delta is empty
110    pub fn is_empty(&self) -> bool {
111        self.node_adds.is_empty()
112            && self.node_removes.is_empty()
113            && self.node_updates.is_empty()
114            && self.edge_adds.is_empty()
115            && self.edge_removes.is_empty()
116            && self.edge_updates.is_empty()
117    }
118
119    /// Get total number of operations
120    pub fn operation_count(&self) -> usize {
121        self.node_adds.len()
122            + self.node_removes.len()
123            + self.node_updates.len()
124            + self.edge_adds.len()
125            + self.edge_removes.len()
126            + self.edge_updates.len()
127    }
128
129    /// Add a node addition
130    pub fn add_node(&mut self, id: NodeId, properties: HashMap<String, PropertyValue>) {
131        self.node_adds.push((id, properties));
132    }
133
134    /// Add a node removal
135    pub fn remove_node(&mut self, id: NodeId) {
136        self.node_removes.push(id);
137    }
138
139    /// Add a node update
140    pub fn update_node(&mut self, id: NodeId, delta: NodeDelta) {
141        self.node_updates.push((id, delta));
142    }
143
144    /// Add an edge
145    pub fn add_edge(&mut self, edge: EdgeAddition) {
146        self.edge_adds.push(edge);
147    }
148
149    /// Remove an edge
150    pub fn remove_edge(&mut self, id: EdgeId) {
151        self.edge_removes.push(id);
152    }
153
154    /// Update an edge
155    pub fn update_edge(&mut self, id: EdgeId, delta: EdgeDelta) {
156        self.edge_updates.push((id, delta));
157    }
158
159    /// Compose with another graph delta
160    pub fn compose(mut self, other: GraphDelta) -> Self {
161        // Handle conflicting operations
162        let removed_nodes: HashSet<_> = other.node_removes.iter().collect();
163        let removed_edges: HashSet<_> = other.edge_removes.iter().collect();
164
165        // Filter out adds that are removed
166        self.node_adds.retain(|(id, _)| !removed_nodes.contains(id));
167        self.edge_adds.retain(|e| !removed_edges.contains(&e.id));
168
169        // Merge adds
170        self.node_adds.extend(other.node_adds);
171        self.node_removes.extend(other.node_removes);
172        self.edge_adds.extend(other.edge_adds);
173        self.edge_removes.extend(other.edge_removes);
174
175        // Compose node updates
176        let mut node_update_map: HashMap<NodeId, NodeDelta> = HashMap::new();
177        for (id, delta) in self.node_updates {
178            node_update_map.insert(id, delta);
179        }
180        for (id, delta) in other.node_updates {
181            node_update_map
182                .entry(id)
183                .and_modify(|existing| *existing = existing.clone().compose(delta.clone()))
184                .or_insert(delta);
185        }
186        self.node_updates = node_update_map.into_iter().collect();
187
188        // Compose edge updates
189        let mut edge_update_map: HashMap<EdgeId, EdgeDelta> = HashMap::new();
190        for (id, delta) in self.edge_updates {
191            edge_update_map.insert(id, delta);
192        }
193        for (id, delta) in other.edge_updates {
194            edge_update_map
195                .entry(id)
196                .and_modify(|existing| *existing = existing.clone().compose(delta.clone()))
197                .or_insert(delta);
198        }
199        self.edge_updates = edge_update_map.into_iter().collect();
200
201        self
202    }
203
204    /// Compute inverse delta
205    pub fn inverse(&self) -> Self {
206        // Note: Full inverse requires knowing original state
207        // This is a partial inverse that works for simple cases
208        Self {
209            node_adds: Vec::new(), // Would need originals to undo removes
210            node_removes: self.node_adds.iter().map(|(id, _)| id.clone()).collect(),
211            node_updates: self
212                .node_updates
213                .iter()
214                .map(|(id, d)| (id.clone(), d.inverse()))
215                .collect(),
216            edge_adds: Vec::new(),
217            edge_removes: self.edge_adds.iter().map(|e| e.id.clone()).collect(),
218            edge_updates: self
219                .edge_updates
220                .iter()
221                .map(|(id, d)| (id.clone(), d.inverse()))
222                .collect(),
223        }
224    }
225
226    /// Get affected node IDs
227    pub fn affected_nodes(&self) -> HashSet<NodeId> {
228        let mut nodes = HashSet::new();
229
230        for (id, _) in &self.node_adds {
231            nodes.insert(id.clone());
232        }
233        for id in &self.node_removes {
234            nodes.insert(id.clone());
235        }
236        for (id, _) in &self.node_updates {
237            nodes.insert(id.clone());
238        }
239        for edge in &self.edge_adds {
240            nodes.insert(edge.source.clone());
241            nodes.insert(edge.target.clone());
242        }
243
244        nodes
245    }
246
247    /// Get affected edge IDs
248    pub fn affected_edges(&self) -> HashSet<EdgeId> {
249        let mut edges = HashSet::new();
250
251        for edge in &self.edge_adds {
252            edges.insert(edge.id.clone());
253        }
254        for id in &self.edge_removes {
255            edges.insert(id.clone());
256        }
257        for (id, _) in &self.edge_updates {
258            edges.insert(id.clone());
259        }
260
261        edges
262    }
263}
264
265impl Default for GraphDelta {
266    fn default() -> Self {
267        Self::new()
268    }
269}
270
271/// Builder for graph deltas
272pub struct GraphDeltaBuilder {
273    delta: GraphDelta,
274}
275
276impl GraphDeltaBuilder {
277    /// Create a new builder
278    pub fn new() -> Self {
279        Self {
280            delta: GraphDelta::new(),
281        }
282    }
283
284    /// Add a node
285    pub fn add_node(mut self, id: impl Into<NodeId>) -> Self {
286        self.delta.add_node(id.into(), HashMap::new());
287        self
288    }
289
290    /// Add a node with properties
291    pub fn add_node_with_props(
292        mut self,
293        id: impl Into<NodeId>,
294        props: HashMap<String, PropertyValue>,
295    ) -> Self {
296        self.delta.add_node(id.into(), props);
297        self
298    }
299
300    /// Remove a node
301    pub fn remove_node(mut self, id: impl Into<NodeId>) -> Self {
302        self.delta.remove_node(id.into());
303        self
304    }
305
306    /// Add an edge
307    pub fn add_edge(
308        mut self,
309        id: impl Into<EdgeId>,
310        source: impl Into<NodeId>,
311        target: impl Into<NodeId>,
312        edge_type: impl Into<String>,
313    ) -> Self {
314        self.delta.add_edge(EdgeAddition {
315            id: id.into(),
316            source: source.into(),
317            target: target.into(),
318            edge_type: edge_type.into(),
319            properties: HashMap::new(),
320        });
321        self
322    }
323
324    /// Remove an edge
325    pub fn remove_edge(mut self, id: impl Into<EdgeId>) -> Self {
326        self.delta.remove_edge(id.into());
327        self
328    }
329
330    /// Build the delta
331    pub fn build(self) -> GraphDelta {
332        self.delta
333    }
334}
335
336impl Default for GraphDeltaBuilder {
337    fn default() -> Self {
338        Self::new()
339    }
340}
341
342/// Stream of graph deltas for event sourcing
343pub struct GraphDeltaStream {
344    stream: DeltaStream<WrappedGraphDelta>,
345}
346
347// Wrapper to implement Delta trait
348#[derive(Clone)]
349struct WrappedGraphDelta(GraphDelta);
350
351impl Delta for WrappedGraphDelta {
352    type Base = GraphState;
353    type Error = GraphDeltaError;
354
355    fn compute(_old: &Self::Base, _new: &Self::Base) -> Self {
356        // Would diff two graph states
357        WrappedGraphDelta(GraphDelta::new())
358    }
359
360    fn apply(&self, base: &mut Self::Base) -> std::result::Result<(), Self::Error> {
361        base.apply_delta(&self.0)
362    }
363
364    fn compose(self, other: Self) -> Self {
365        WrappedGraphDelta(self.0.compose(other.0))
366    }
367
368    fn inverse(&self) -> Self {
369        WrappedGraphDelta(self.0.inverse())
370    }
371
372    fn is_identity(&self) -> bool {
373        self.0.is_empty()
374    }
375
376    fn byte_size(&self) -> usize {
377        // Approximate size
378        std::mem::size_of::<GraphDelta>() + self.0.operation_count() * 100
379    }
380}
381
382impl Default for WrappedGraphDelta {
383    fn default() -> Self {
384        Self(GraphDelta::new())
385    }
386}
387
388/// Simplified graph state for delta application
389#[derive(Debug, Clone, Default)]
390pub struct GraphState {
391    /// Nodes with properties
392    pub nodes: HashMap<NodeId, HashMap<String, PropertyValue>>,
393    /// Edges
394    pub edges: HashMap<EdgeId, (NodeId, NodeId, String, HashMap<String, PropertyValue>)>,
395}
396
397impl GraphState {
398    /// Create empty state
399    pub fn new() -> Self {
400        Self::default()
401    }
402
403    /// Apply a graph delta
404    pub fn apply_delta(&mut self, delta: &GraphDelta) -> Result<()> {
405        // Remove nodes
406        for id in &delta.node_removes {
407            self.nodes.remove(id);
408            // Also remove incident edges
409            self.edges.retain(|_, (s, t, _, _)| s != id && t != id);
410        }
411
412        // Remove edges
413        for id in &delta.edge_removes {
414            self.edges.remove(id);
415        }
416
417        // Add nodes
418        for (id, props) in &delta.node_adds {
419            self.nodes.insert(id.clone(), props.clone());
420        }
421
422        // Add edges
423        for edge in &delta.edge_adds {
424            self.edges.insert(
425                edge.id.clone(),
426                (
427                    edge.source.clone(),
428                    edge.target.clone(),
429                    edge.edge_type.clone(),
430                    edge.properties.clone(),
431                ),
432            );
433        }
434
435        // Update nodes
436        for (id, node_delta) in &delta.node_updates {
437            if let Some(props) = self.nodes.get_mut(id) {
438                for prop_delta in &node_delta.property_deltas {
439                    match &prop_delta.operation {
440                        PropertyOp::Set(value) => {
441                            props.insert(prop_delta.key.clone(), value.clone());
442                        }
443                        PropertyOp::Remove => {
444                            props.remove(&prop_delta.key);
445                        }
446                        PropertyOp::VectorDelta(vd) => {
447                            if let Some(PropertyValue::Vector(v)) = props.get_mut(&prop_delta.key) {
448                                vd.apply(v)
449                                    .map_err(|e| GraphDeltaError::DeltaError(format!("{:?}", e)))?;
450                            }
451                        }
452                    }
453                }
454            }
455        }
456
457        // Update edges
458        for (id, edge_delta) in &delta.edge_updates {
459            if let Some((_, _, _, props)) = self.edges.get_mut(id) {
460                for prop_delta in &edge_delta.property_deltas {
461                    match &prop_delta.operation {
462                        PropertyOp::Set(value) => {
463                            props.insert(prop_delta.key.clone(), value.clone());
464                        }
465                        PropertyOp::Remove => {
466                            props.remove(&prop_delta.key);
467                        }
468                        PropertyOp::VectorDelta(_) => {
469                            // Edges typically don't have vector properties
470                        }
471                    }
472                }
473            }
474        }
475
476        Ok(())
477    }
478
479    /// Get node count
480    pub fn node_count(&self) -> usize {
481        self.nodes.len()
482    }
483
484    /// Get edge count
485    pub fn edge_count(&self) -> usize {
486        self.edges.len()
487    }
488}
489
490/// Property operation types
491#[derive(Debug, Clone)]
492pub enum PropertyOp {
493    /// Set property value
494    Set(PropertyValue),
495    /// Remove property
496    Remove,
497    /// Apply vector delta to vector property
498    VectorDelta(VectorDelta),
499}
500
501#[cfg(test)]
502mod tests {
503    use super::*;
504
505    #[test]
506    fn test_graph_delta_builder() {
507        let delta = GraphDeltaBuilder::new()
508            .add_node("a")
509            .add_node("b")
510            .add_edge("e1", "a", "b", "KNOWS")
511            .build();
512
513        assert_eq!(delta.node_adds.len(), 2);
514        assert_eq!(delta.edge_adds.len(), 1);
515    }
516
517    #[test]
518    fn test_graph_state_apply() {
519        let mut state = GraphState::new();
520
521        let delta = GraphDeltaBuilder::new()
522            .add_node("a")
523            .add_node("b")
524            .add_edge("e1", "a", "b", "KNOWS")
525            .build();
526
527        state.apply_delta(&delta).unwrap();
528
529        assert_eq!(state.node_count(), 2);
530        assert_eq!(state.edge_count(), 1);
531    }
532
533    #[test]
534    fn test_delta_compose() {
535        let d1 = GraphDeltaBuilder::new().add_node("a").add_node("b").build();
536
537        let d2 = GraphDeltaBuilder::new()
538            .remove_node("b")
539            .add_node("c")
540            .build();
541
542        let composed = d1.compose(d2);
543
544        // "a" added, "b" removed, "c" added
545        assert_eq!(composed.node_adds.len(), 2); // a and c
546        assert_eq!(composed.node_removes.len(), 1); // b
547    }
548
549    #[test]
550    fn test_affected_nodes() {
551        let delta = GraphDeltaBuilder::new()
552            .add_node("a")
553            .add_edge("e1", "b", "c", "RELATES")
554            .build();
555
556        let affected = delta.affected_nodes();
557
558        assert!(affected.contains("a"));
559        assert!(affected.contains("b"));
560        assert!(affected.contains("c"));
561    }
562}