leptos_sync_core/crdt/graph/
add_wins.rs

1//! Add-Wins Graph CRDT implementation
2//! 
3//! This implementation ensures that vertices and edges are never completely lost.
4//! Deleted elements are marked as deleted but preserved for potential recovery.
5
6use super::vertex::{Vertex, VertexId, GraphError};
7use super::edge::{Edge, EdgeId};
8use super::super::{CRDT, Mergeable, ReplicaId};
9use serde::{Deserialize, Serialize};
10use std::collections::{HashMap, HashSet, VecDeque};
11
12/// Configuration for graph CRDTs
13#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
14pub struct GraphConfig {
15    /// Whether to preserve deleted vertices and edges in metadata
16    pub preserve_deleted: bool,
17    /// Maximum number of vertices
18    pub max_vertices: Option<usize>,
19    /// Maximum number of edges
20    pub max_edges: Option<usize>,
21    /// Whether to allow self-loops
22    pub allow_self_loops: bool,
23    /// Whether to allow multiple edges between the same vertices
24    pub allow_multiple_edges: bool,
25}
26
27impl Default for GraphConfig {
28    fn default() -> Self {
29        Self {
30            preserve_deleted: true,
31            max_vertices: None,
32            max_edges: None,
33            allow_self_loops: false,
34            allow_multiple_edges: false,
35        }
36    }
37}
38
39/// Add-Wins Graph CRDT implementation
40#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
41pub struct AddWinsGraph<T> {
42    /// Configuration
43    pub config: GraphConfig,
44    /// Vertices in the graph
45    vertices: HashMap<VertexId, Vertex<T>>,
46    /// Edges in the graph
47    edges: HashMap<EdgeId, Edge>,
48    /// Replica ID for this instance
49    replica: ReplicaId,
50}
51
52impl<T: Clone + PartialEq + Eq + Send + Sync> AddWinsGraph<T> {
53    /// Create a new Add-Wins graph
54    pub fn new(replica: ReplicaId) -> Self {
55        Self {
56            config: GraphConfig::default(),
57            vertices: HashMap::new(),
58            edges: HashMap::new(),
59            replica,
60        }
61    }
62
63    /// Create with custom configuration
64    pub fn with_config(replica: ReplicaId, config: GraphConfig) -> Self {
65        Self {
66            config,
67            vertices: HashMap::new(),
68            edges: HashMap::new(),
69            replica,
70        }
71    }
72
73    /// Add a vertex to the graph
74    pub fn add_vertex(&mut self, value: T, timestamp: u64) -> VertexId {
75        let vertex = Vertex::new(value, self.replica, timestamp);
76        let id = vertex.id.clone();
77        self.vertices.insert(id.clone(), vertex);
78        id
79    }
80
81    /// Add an edge between two vertices
82    pub fn add_edge(&mut self, source: &VertexId, target: &VertexId, timestamp: u64, weight: Option<f64>) -> Result<EdgeId, GraphError> {
83        // Check if vertices exist
84        if !self.vertices.contains_key(source) || !self.vertices.contains_key(target) {
85            return Err(GraphError::new("Source or target vertex not found".to_string()));
86        }
87
88        // Check for self-loops
89        if !self.config.allow_self_loops && source == target {
90            return Err(GraphError::new("Self-loops are not allowed".to_string()));
91        }
92
93        // Check for multiple edges if not allowed
94        if !self.config.allow_multiple_edges {
95            for edge in self.edges.values() {
96                if !edge.metadata.deleted && edge.source == *source && edge.target == *target {
97                    return Err(GraphError::new("Multiple edges between same vertices not allowed".to_string()));
98                }
99            }
100        }
101
102        let edge = if let Some(w) = weight {
103            Edge::with_weight(source.clone(), target.clone(), w, self.replica, timestamp)
104        } else {
105            Edge::new(source.clone(), target.clone(), self.replica, timestamp)
106        };
107        
108        let id = edge.id.clone();
109        self.edges.insert(id.clone(), edge);
110        Ok(id)
111    }
112
113    /// Update an existing vertex
114    pub fn update_vertex(&mut self, id: &VertexId, value: T, timestamp: u64) -> Result<(), GraphError> {
115        if let Some(vertex) = self.vertices.get_mut(id) {
116            vertex.value = value;
117            vertex.mark_modified(self.replica, timestamp);
118            Ok(())
119        } else {
120            Err(GraphError::new("Vertex not found".to_string()))
121        }
122    }
123
124    /// Update an existing edge
125    pub fn update_edge(&mut self, id: &EdgeId, weight: f64, timestamp: u64) -> Result<(), GraphError> {
126        if let Some(edge) = self.edges.get_mut(id) {
127            edge.weight = Some(weight);
128            edge.mark_modified(self.replica, timestamp);
129            Ok(())
130        } else {
131            Err(GraphError::new("Edge not found".to_string()))
132        }
133    }
134
135    /// Mark a vertex as deleted
136    pub fn remove_vertex(&mut self, id: &VertexId, timestamp: u64) -> Result<(), GraphError> {
137        if let Some(vertex) = self.vertices.get_mut(id) {
138            vertex.mark_deleted(self.replica, timestamp);
139            
140            // Mark all incident edges as deleted
141            for edge in self.edges.values_mut() {
142                if !edge.metadata.deleted && (edge.source == *id || edge.target == *id) {
143                    edge.mark_deleted(self.replica, timestamp);
144                }
145            }
146            Ok(())
147        } else {
148            Err(GraphError::new("Vertex not found".to_string()))
149        }
150    }
151
152    /// Mark an edge as deleted
153    pub fn remove_edge(&mut self, id: &EdgeId, timestamp: u64) -> Result<(), GraphError> {
154        if let Some(edge) = self.edges.get_mut(id) {
155            edge.mark_deleted(self.replica, timestamp);
156            Ok(())
157        } else {
158            Err(GraphError::new("Edge not found".to_string()))
159        }
160    }
161
162    /// Get a vertex by ID
163    pub fn get_vertex(&self, id: &VertexId) -> Option<&Vertex<T>> {
164        self.vertices.get(id)
165    }
166
167    /// Get an edge by ID
168    pub fn get_edge(&self, id: &EdgeId) -> Option<&Edge> {
169        self.edges.get(id)
170    }
171
172    /// Get all visible vertices (not deleted)
173    pub fn visible_vertices(&self) -> Vec<&Vertex<T>> {
174        self.vertices
175            .values()
176            .filter(|v| !v.metadata.deleted)
177            .collect()
178    }
179
180    /// Get all visible edges (not deleted)
181    pub fn visible_edges(&self) -> Vec<&Edge> {
182        self.edges
183            .values()
184            .filter(|e| !e.metadata.deleted)
185            .collect()
186    }
187
188    /// Get all vertices including deleted ones
189    pub fn all_vertices(&self) -> Vec<&Vertex<T>> {
190        self.vertices.values().collect()
191    }
192
193    /// Get all edges including deleted ones
194    pub fn all_edges(&self) -> Vec<&Edge> {
195        self.edges.values().collect()
196    }
197
198    /// Get neighbors of a vertex
199    pub fn neighbors(&self, id: &VertexId) -> Vec<&Vertex<T>> {
200        let mut neighbors = Vec::new();
201        
202        for edge in self.edges.values() {
203            if !edge.metadata.deleted {
204                if edge.source == *id {
205                    if let Some(target) = self.vertices.get(&edge.target) {
206                        if !target.metadata.deleted {
207                            neighbors.push(target);
208                        }
209                    }
210                } else if edge.target == *id {
211                    if let Some(source) = self.vertices.get(&edge.source) {
212                        if !source.metadata.deleted {
213                            neighbors.push(source);
214                        }
215                    }
216                }
217            }
218        }
219        
220        neighbors
221    }
222
223    /// Get incoming edges to a vertex
224    pub fn incoming_edges(&self, id: &VertexId) -> Vec<&Edge> {
225        self.edges
226            .values()
227            .filter(|e| !e.metadata.deleted && e.target == *id)
228            .collect()
229    }
230
231    /// Get outgoing edges from a vertex
232    pub fn outgoing_edges(&self, id: &VertexId) -> Vec<&Edge> {
233        self.edges
234            .values()
235            .filter(|e| !e.metadata.deleted && e.source == *id)
236            .collect()
237    }
238
239    /// Find shortest path between two vertices using BFS
240    pub fn shortest_path(&self, source: &VertexId, target: &VertexId) -> Option<Vec<VertexId>> {
241        if !self.vertices.contains_key(source) || !self.vertices.contains_key(target) {
242            return None;
243        }
244
245        let mut visited = HashSet::new();
246        let mut queue = VecDeque::new();
247        let mut parent: HashMap<VertexId, VertexId> = HashMap::new();
248        
249        queue.push_back(source.clone());
250        visited.insert(source.clone());
251        
252        while let Some(current) = queue.pop_front() {
253            if current == *target {
254                // Reconstruct path
255                let mut path = Vec::new();
256                let mut current_id = current;
257                
258                while current_id != *source {
259                    path.push(current_id.clone());
260                    current_id = parent[&current_id].clone();
261                }
262                path.push(source.clone());
263                path.reverse();
264                return Some(path);
265            }
266            
267            for neighbor in self.neighbors(&current) {
268                if !visited.contains(&neighbor.id) {
269                    visited.insert(neighbor.id.clone());
270                    parent.insert(neighbor.id.clone(), current.clone());
271                    queue.push_back(neighbor.id.clone());
272                }
273            }
274        }
275        
276        None
277    }
278
279    /// Check if the graph contains a vertex
280    pub fn contains_vertex(&self, id: &VertexId) -> bool {
281        self.vertices.contains_key(id)
282    }
283
284    /// Check if the graph contains an edge
285    pub fn contains_edge(&self, id: &EdgeId) -> bool {
286        self.edges.contains_key(id)
287    }
288
289    /// Get the number of visible vertices
290    pub fn vertex_count(&self) -> usize {
291        self.visible_vertices().len()
292    }
293
294    /// Get the number of visible edges
295    pub fn edge_count(&self) -> usize {
296        self.visible_edges().len()
297    }
298
299    /// Check if the graph is empty
300    pub fn is_empty(&self) -> bool {
301        self.vertex_count() == 0
302    }
303
304    /// Clear all vertices and edges
305    pub fn clear(&mut self) {
306        self.vertices.clear();
307        self.edges.clear();
308    }
309}
310
311impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for AddWinsGraph<T> {
312    fn replica_id(&self) -> &ReplicaId {
313        &self.replica
314    }
315}
316
317impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for AddWinsGraph<T> {
318    type Error = GraphError;
319
320    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
321        // Merge vertices
322        for (id, vertex) in &other.vertices {
323            match self.vertices.get(id) {
324                Some(existing) => {
325                    // Conflict resolution: later timestamp wins
326                    if vertex.metadata.modified_at > existing.metadata.modified_at {
327                        self.vertices.insert(id.clone(), vertex.clone());
328                    }
329                }
330                None => {
331                    // New vertex, add it
332                    self.vertices.insert(id.clone(), vertex.clone());
333                }
334            }
335        }
336
337        // Merge edges
338        for (id, edge) in &other.edges {
339            match self.edges.get(id) {
340                Some(existing) => {
341                    // Conflict resolution: later timestamp wins
342                    if edge.metadata.modified_at > existing.metadata.modified_at {
343                        self.edges.insert(id.clone(), edge.clone());
344                    }
345                }
346                None => {
347                    // New edge, add it
348                    self.edges.insert(id.clone(), edge.clone());
349                }
350            }
351        }
352        
353        Ok(())
354    }
355
356    fn has_conflict(&self, other: &Self) -> bool {
357        // Check for conflicts in overlapping vertices
358        for (id, vertex) in &other.vertices {
359            if let Some(existing) = self.vertices.get(id) {
360                if vertex.metadata.modified_at == existing.metadata.modified_at
361                    && vertex.metadata.last_modified_by != existing.metadata.last_modified_by
362                {
363                    return true;
364                }
365            }
366        }
367
368        // Check for conflicts in overlapping edges
369        for (id, edge) in &other.edges {
370            if let Some(existing) = self.edges.get(id) {
371                if edge.metadata.modified_at == existing.metadata.modified_at
372                    && edge.metadata.last_modified_by != existing.metadata.last_modified_by
373                {
374                    return true;
375                }
376            }
377        }
378        false
379    }
380}
381
382#[cfg(test)]
383mod tests {
384    use super::*;
385    use super::super::super::ReplicaId;
386    use uuid::Uuid;
387
388    fn create_replica(id: u64) -> ReplicaId {
389        ReplicaId::from(Uuid::from_u64_pair(0, id))
390    }
391
392    #[test]
393    fn test_add_wins_graph_basic_operations() {
394        let replica = create_replica(1);
395        let mut graph = AddWinsGraph::new(replica);
396        
397        // Add vertices
398        let v1_id = graph.add_vertex("vertex1", 1000);
399        let v2_id = graph.add_vertex("vertex2", 2000);
400        
401        assert_eq!(graph.vertex_count(), 2);
402        assert!(graph.contains_vertex(&v1_id));
403        assert!(graph.contains_vertex(&v2_id));
404        
405        // Add edge
406        let edge_id = graph.add_edge(&v1_id, &v2_id, 3000, None).unwrap();
407        assert_eq!(graph.edge_count(), 1);
408        assert!(graph.contains_edge(&edge_id));
409        
410        // Update vertex
411        graph.update_vertex(&v1_id, "updated_vertex1", 4000).unwrap();
412        assert_eq!(graph.get_vertex(&v1_id).unwrap().value, "updated_vertex1");
413    }
414
415    #[test]
416    fn test_graph_neighbors() {
417        let replica = create_replica(1);
418        let mut graph = AddWinsGraph::new(replica);
419        
420        // Create triangle: v1 -> v2 -> v3 -> v1
421        let v1_id = graph.add_vertex("vertex1", 1000);
422        let v2_id = graph.add_vertex("vertex2", 2000);
423        let v3_id = graph.add_vertex("vertex3", 3000);
424        
425        graph.add_edge(&v1_id, &v2_id, 4000, None).unwrap();
426        graph.add_edge(&v2_id, &v3_id, 5000, None).unwrap();
427        graph.add_edge(&v3_id, &v1_id, 6000, None).unwrap();
428        
429        // Check neighbors
430        let v1_neighbors = graph.neighbors(&v1_id);
431        assert_eq!(v1_neighbors.len(), 2); // v2 and v3
432        
433        let v2_neighbors = graph.neighbors(&v2_id);
434        assert_eq!(v2_neighbors.len(), 2); // v1 and v3
435        
436        let v3_neighbors = graph.neighbors(&v3_id);
437        assert_eq!(v3_neighbors.len(), 2); // v1 and v2
438    }
439
440    #[test]
441    fn test_graph_shortest_path() {
442        let replica = create_replica(1);
443        let mut graph = AddWinsGraph::new(replica);
444        
445        // Create path: v1 -> v2 -> v3 -> v4
446        let v1_id = graph.add_vertex("vertex1", 1000);
447        let v2_id = graph.add_vertex("vertex2", 2000);
448        let v3_id = graph.add_vertex("vertex3", 3000);
449        let v4_id = graph.add_vertex("vertex4", 4000);
450        
451        graph.add_edge(&v1_id, &v2_id, 5000, None).unwrap();
452        graph.add_edge(&v2_id, &v3_id, 6000, None).unwrap();
453        graph.add_edge(&v3_id, &v4_id, 7000, None).unwrap();
454        
455        // Find shortest path
456        let path = graph.shortest_path(&v1_id, &v4_id).unwrap();
457        assert_eq!(path.len(), 4);
458        assert_eq!(path[0], v1_id);
459        assert_eq!(path[1], v2_id);
460        assert_eq!(path[2], v3_id);
461        assert_eq!(path[3], v4_id);
462    }
463
464    #[test]
465    fn test_graph_merge() {
466        let replica1 = create_replica(1);
467        let replica2 = create_replica(2);
468        
469        let mut graph1 = AddWinsGraph::new(replica1);
470        let mut graph2 = AddWinsGraph::new(replica2);
471        
472        // Add vertices to both graphs
473        let v1_id = graph1.add_vertex("vertex1", 1000);
474        let v2_id = graph2.add_vertex("vertex2", 2000);
475        
476        // Merge graph2 into graph1
477        graph1.merge(&graph2).unwrap();
478        
479        // Both vertices should be present
480        assert_eq!(graph1.vertex_count(), 2);
481        assert!(graph1.contains_vertex(&v1_id));
482        assert!(graph1.contains_vertex(&v2_id));
483    }
484
485    #[test]
486    fn test_graph_configuration() {
487        let replica = create_replica(1);
488        let config = GraphConfig {
489            preserve_deleted: false,
490            max_vertices: Some(100),
491            max_edges: Some(200),
492            allow_self_loops: true,
493            allow_multiple_edges: true,
494        };
495        
496        let graph: AddWinsGraph<String> = AddWinsGraph::with_config(replica, config);
497        assert_eq!(graph.config.max_vertices, Some(100));
498        assert_eq!(graph.config.allow_self_loops, true);
499        assert_eq!(graph.config.allow_multiple_edges, true);
500    }
501
502    #[test]
503    fn test_graph_validation() {
504        let replica = create_replica(1);
505        let mut graph = AddWinsGraph::new(replica);
506        
507        // Add vertices
508        let v1_id = graph.add_vertex("vertex1", 1000);
509        let v2_id = graph.add_vertex("vertex2", 2000);
510        
511        // Try to add edge with non-existent vertex
512        let fake_id = VertexId::new(create_replica(999));
513        let result = graph.add_edge(&v1_id, &fake_id, 3000, None);
514        assert!(result.is_err());
515        
516        // Try to add edge to itself (self-loop not allowed by default)
517        let result = graph.add_edge(&v1_id, &v1_id, 3000, None);
518        assert!(result.is_err());
519    }
520}
521
leptos_sync_core/crdt/graph/add_wins.rs

leptos_sync_core/crdt/graph/
add_wins.rs
