uqa_graph/
delta.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Graph deltas: a sequence of add/remove vertex/edge operations
8//! applied atomically to a [`GraphStore`]. Deltas drive the
9//! [`crate::VersionedGraphStore`] versioning model and feed targeted
10//! path-index invalidation by exposing affected vertex ids and edge
11//! labels.
12
13use std::collections::BTreeSet;
14
15use uqa_core::{Edge, EdgeId, Vertex, VertexId};
16
17/// A single mutation operation in a [`GraphDelta`].
18#[derive(Debug, Clone)]
19pub enum DeltaOp {
20    AddVertex(Vertex),
21    RemoveVertex(VertexId),
22    AddEdge(Edge),
23    RemoveEdge(EdgeId),
24}
25
26/// Records add / remove vertex / edge operations (Section 9.3, Paper 2).
27#[derive(Debug, Clone, Default)]
28pub struct GraphDelta {
29    ops: Vec<DeltaOp>,
30}
31
32impl GraphDelta {
33    pub fn new() -> Self {
34        Self::default()
35    }
36
37    pub fn add_vertex(&mut self, vertex: Vertex) {
38        self.ops.push(DeltaOp::AddVertex(vertex));
39    }
40
41    pub fn remove_vertex(&mut self, vertex_id: VertexId) {
42        self.ops.push(DeltaOp::RemoveVertex(vertex_id));
43    }
44
45    pub fn add_edge(&mut self, edge: Edge) {
46        self.ops.push(DeltaOp::AddEdge(edge));
47    }
48
49    pub fn remove_edge(&mut self, edge_id: EdgeId) {
50        self.ops.push(DeltaOp::RemoveEdge(edge_id));
51    }
52
53    pub fn ops(&self) -> &[DeltaOp] {
54        &self.ops
55    }
56
57    pub fn is_empty(&self) -> bool {
58        self.ops.is_empty()
59    }
60
61    pub fn len(&self) -> usize {
62        self.ops.len()
63    }
64
65    /// Set of vertex ids touched by any op (vertices added / removed,
66    /// plus the source / target of added edges). Edge removal does not
67    /// resurrect a vertex id since the operation only stores the edge
68    /// id.
69    pub fn affected_vertex_ids(&self) -> BTreeSet<VertexId> {
70        let mut ids = BTreeSet::new();
71        for op in &self.ops {
72            match op {
73                DeltaOp::AddVertex(v) => {
74                    ids.insert(v.vertex_id);
75                }
76                DeltaOp::RemoveVertex(v) => {
77                    ids.insert(*v);
78                }
79                DeltaOp::AddEdge(e) => {
80                    ids.insert(e.source_id);
81                    ids.insert(e.target_id);
82                }
83                DeltaOp::RemoveEdge(_) => {}
84            }
85        }
86        ids
87    }
88
89    /// Set of edge labels touched by `AddEdge` ops. Used by the
90    /// versioned store to invalidate path indexes that depend on a
91    /// label.
92    pub fn affected_edge_labels(&self) -> BTreeSet<String> {
93        let mut labels = BTreeSet::new();
94        for op in &self.ops {
95            if let DeltaOp::AddEdge(edge) = op {
96                labels.insert(edge.label.clone());
97            }
98        }
99        labels
100    }
101}
uqa_graph/delta.rs

uqa_graph/
delta.rs
