1#![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
31pub type NodeId = String;
33
34pub type EdgeId = String;
36
37#[derive(Debug, Clone, PartialEq)]
39pub enum PropertyValue {
40 Null,
42 Bool(bool),
44 Int(i64),
46 Float(f64),
48 String(String),
50 Vector(Vec<f32>),
52 List(Vec<PropertyValue>),
54 Map(HashMap<String, PropertyValue>),
56}
57
58impl Default for PropertyValue {
59 fn default() -> Self {
60 Self::Null
61 }
62}
63
64#[derive(Debug, Clone)]
66pub struct GraphDelta {
67 pub node_adds: Vec<(NodeId, HashMap<String, PropertyValue>)>,
69 pub node_removes: Vec<NodeId>,
71 pub node_updates: Vec<(NodeId, NodeDelta)>,
73 pub edge_adds: Vec<EdgeAddition>,
75 pub edge_removes: Vec<EdgeId>,
77 pub edge_updates: Vec<(EdgeId, EdgeDelta)>,
79}
80
81#[derive(Debug, Clone)]
83pub struct EdgeAddition {
84 pub id: EdgeId,
86 pub source: NodeId,
88 pub target: NodeId,
90 pub edge_type: String,
92 pub properties: HashMap<String, PropertyValue>,
94}
95
96impl GraphDelta {
97 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 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 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 pub fn add_node(&mut self, id: NodeId, properties: HashMap<String, PropertyValue>) {
131 self.node_adds.push((id, properties));
132 }
133
134 pub fn remove_node(&mut self, id: NodeId) {
136 self.node_removes.push(id);
137 }
138
139 pub fn update_node(&mut self, id: NodeId, delta: NodeDelta) {
141 self.node_updates.push((id, delta));
142 }
143
144 pub fn add_edge(&mut self, edge: EdgeAddition) {
146 self.edge_adds.push(edge);
147 }
148
149 pub fn remove_edge(&mut self, id: EdgeId) {
151 self.edge_removes.push(id);
152 }
153
154 pub fn update_edge(&mut self, id: EdgeId, delta: EdgeDelta) {
156 self.edge_updates.push((id, delta));
157 }
158
159 pub fn compose(mut self, other: GraphDelta) -> Self {
161 let removed_nodes: HashSet<_> = other.node_removes.iter().collect();
163 let removed_edges: HashSet<_> = other.edge_removes.iter().collect();
164
165 self.node_adds.retain(|(id, _)| !removed_nodes.contains(id));
167 self.edge_adds.retain(|e| !removed_edges.contains(&e.id));
168
169 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 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 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 pub fn inverse(&self) -> Self {
206 Self {
209 node_adds: Vec::new(), 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 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 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
271pub struct GraphDeltaBuilder {
273 delta: GraphDelta,
274}
275
276impl GraphDeltaBuilder {
277 pub fn new() -> Self {
279 Self {
280 delta: GraphDelta::new(),
281 }
282 }
283
284 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 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 pub fn remove_node(mut self, id: impl Into<NodeId>) -> Self {
302 self.delta.remove_node(id.into());
303 self
304 }
305
306 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 pub fn remove_edge(mut self, id: impl Into<EdgeId>) -> Self {
326 self.delta.remove_edge(id.into());
327 self
328 }
329
330 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
342pub struct GraphDeltaStream {
344 stream: DeltaStream<WrappedGraphDelta>,
345}
346
347#[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 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 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#[derive(Debug, Clone, Default)]
390pub struct GraphState {
391 pub nodes: HashMap<NodeId, HashMap<String, PropertyValue>>,
393 pub edges: HashMap<EdgeId, (NodeId, NodeId, String, HashMap<String, PropertyValue>)>,
395}
396
397impl GraphState {
398 pub fn new() -> Self {
400 Self::default()
401 }
402
403 pub fn apply_delta(&mut self, delta: &GraphDelta) -> Result<()> {
405 for id in &delta.node_removes {
407 self.nodes.remove(id);
408 self.edges.retain(|_, (s, t, _, _)| s != id && t != id);
410 }
411
412 for id in &delta.edge_removes {
414 self.edges.remove(id);
415 }
416
417 for (id, props) in &delta.node_adds {
419 self.nodes.insert(id.clone(), props.clone());
420 }
421
422 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 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 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 }
471 }
472 }
473 }
474 }
475
476 Ok(())
477 }
478
479 pub fn node_count(&self) -> usize {
481 self.nodes.len()
482 }
483
484 pub fn edge_count(&self) -> usize {
486 self.edges.len()
487 }
488}
489
490#[derive(Debug, Clone)]
492pub enum PropertyOp {
493 Set(PropertyValue),
495 Remove,
497 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 assert_eq!(composed.node_adds.len(), 2); assert_eq!(composed.node_removes.len(), 1); }
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}