leptos_sync_core/crdt/graph/
remove_wins.rs

1//! Remove-Wins Graph CRDT implementation
2//!
3//! This implementation completely removes deleted vertices and edges.
4//! It's more memory-efficient but elements cannot be recovered.
5
6use super::super::{CRDT, Mergeable, ReplicaId};
7use super::add_wins::GraphConfig;
8use super::edge::{Edge, EdgeId};
9use super::vertex::{GraphError, Vertex, VertexId};
10use serde::{Deserialize, Serialize};
11use std::collections::{HashMap, HashSet, VecDeque};
12
13/// Remove-Wins Graph CRDT implementation
14#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
15pub struct RemoveWinsGraph<T> {
16    /// Configuration
17    config: GraphConfig,
18    /// Vertices in the graph
19    vertices: HashMap<VertexId, Vertex<T>>,
20    /// Edges in the graph
21    edges: HashMap<EdgeId, Edge>,
22    /// Replica ID for this instance
23    replica: ReplicaId,
24}
25
26impl<T: Clone + PartialEq + Eq + Send + Sync> RemoveWinsGraph<T> {
27    /// Create a new Remove-Wins graph
28    pub fn new(replica: ReplicaId) -> Self {
29        Self {
30            config: GraphConfig {
31                preserve_deleted: false,
32                max_vertices: None,
33                max_edges: None,
34                allow_self_loops: false,
35                allow_multiple_edges: false,
36            },
37            vertices: HashMap::new(),
38            edges: HashMap::new(),
39            replica,
40        }
41    }
42
43    /// Create with custom configuration
44    pub fn with_config(replica: ReplicaId, config: GraphConfig) -> Self {
45        Self {
46            config,
47            vertices: HashMap::new(),
48            edges: HashMap::new(),
49            replica,
50        }
51    }
52
53    /// Add a vertex to the graph
54    pub fn add_vertex(&mut self, value: T, timestamp: u64) -> VertexId {
55        let vertex = Vertex::new(value, self.replica, timestamp);
56        let id = vertex.id.clone();
57        self.vertices.insert(id.clone(), vertex);
58        id
59    }
60
61    /// Add an edge between two vertices
62    pub fn add_edge(
63        &mut self,
64        source: &VertexId,
65        target: &VertexId,
66        timestamp: u64,
67        weight: Option<f64>,
68    ) -> Result<EdgeId, GraphError> {
69        // Check if vertices exist
70        if !self.vertices.contains_key(source) || !self.vertices.contains_key(target) {
71            return Err(GraphError::new(
72                "Source or target vertex not found".to_string(),
73            ));
74        }
75
76        // Check for self-loops
77        if !self.config.allow_self_loops && source == target {
78            return Err(GraphError::new("Self-loops are not allowed".to_string()));
79        }
80
81        // Check for multiple edges if not allowed
82        if !self.config.allow_multiple_edges {
83            for edge in self.edges.values() {
84                if edge.source == *source && edge.target == *target {
85                    return Err(GraphError::new(
86                        "Multiple edges between same vertices not allowed".to_string(),
87                    ));
88                }
89            }
90        }
91
92        let edge = if let Some(w) = weight {
93            Edge::with_weight(source.clone(), target.clone(), w, self.replica, timestamp)
94        } else {
95            Edge::new(source.clone(), target.clone(), self.replica, timestamp)
96        };
97
98        let id = edge.id.clone();
99        self.edges.insert(id.clone(), edge);
100        Ok(id)
101    }
102
103    /// Update an existing vertex
104    pub fn update_vertex(
105        &mut self,
106        id: &VertexId,
107        value: T,
108        timestamp: u64,
109    ) -> Result<(), GraphError> {
110        if let Some(vertex) = self.vertices.get_mut(id) {
111            vertex.value = value;
112            vertex.mark_modified(self.replica, timestamp);
113            Ok(())
114        } else {
115            Err(GraphError::new("Vertex not found".to_string()))
116        }
117    }
118
119    /// Update an existing edge
120    pub fn update_edge(
121        &mut self,
122        id: &EdgeId,
123        weight: f64,
124        timestamp: u64,
125    ) -> 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    /// Remove a vertex completely
136    pub fn remove_vertex(&mut self, id: &VertexId) -> Result<(), GraphError> {
137        if self.vertices.remove(id).is_some() {
138            // Remove all incident edges
139            self.edges
140                .retain(|_, edge| edge.source != *id && edge.target != *id);
141            Ok(())
142        } else {
143            Err(GraphError::new("Vertex not found".to_string()))
144        }
145    }
146
147    /// Remove an edge completely
148    pub fn remove_edge(&mut self, id: &EdgeId) -> Result<(), GraphError> {
149        if self.edges.remove(id).is_some() {
150            Ok(())
151        } else {
152            Err(GraphError::new("Edge not found".to_string()))
153        }
154    }
155
156    /// Get a vertex by ID
157    pub fn get_vertex(&self, id: &VertexId) -> Option<&Vertex<T>> {
158        self.vertices.get(id)
159    }
160
161    /// Get an edge by ID
162    pub fn get_edge(&self, id: &EdgeId) -> Option<&Edge> {
163        self.edges.get(id)
164    }
165
166    /// Get all vertices
167    pub fn vertices(&self) -> Vec<&Vertex<T>> {
168        self.vertices.values().collect()
169    }
170
171    /// Get all edges
172    pub fn edges(&self) -> Vec<&Edge> {
173        self.edges.values().collect()
174    }
175
176    /// Get neighbors of a vertex
177    pub fn neighbors(&self, id: &VertexId) -> Vec<&Vertex<T>> {
178        let mut neighbors = Vec::new();
179
180        for edge in self.edges.values() {
181            if edge.source == *id {
182                if let Some(target) = self.vertices.get(&edge.target) {
183                    neighbors.push(target);
184                }
185            } else if edge.target == *id {
186                if let Some(source) = self.vertices.get(&edge.source) {
187                    neighbors.push(source);
188                }
189            }
190        }
191
192        neighbors
193    }
194
195    /// Get incoming edges to a vertex
196    pub fn incoming_edges(&self, id: &VertexId) -> Vec<&Edge> {
197        self.edges.values().filter(|e| e.target == *id).collect()
198    }
199
200    /// Get outgoing edges from a vertex
201    pub fn outgoing_edges(&self, id: &VertexId) -> Vec<&Edge> {
202        self.edges.values().filter(|e| e.source == *id).collect()
203    }
204
205    /// Find shortest path between two vertices using BFS
206    pub fn shortest_path(&self, source: &VertexId, target: &VertexId) -> Option<Vec<VertexId>> {
207        if !self.vertices.contains_key(source) || !self.vertices.contains_key(target) {
208            return None;
209        }
210
211        let mut visited = HashSet::new();
212        let mut queue = VecDeque::new();
213        let mut parent: HashMap<VertexId, VertexId> = HashMap::new();
214
215        queue.push_back(source.clone());
216        visited.insert(source.clone());
217
218        while let Some(current) = queue.pop_front() {
219            if current == *target {
220                // Reconstruct path
221                let mut path = Vec::new();
222                let mut current_id = current;
223
224                while current_id != *source {
225                    path.push(current_id.clone());
226                    current_id = parent[&current_id].clone();
227                }
228                path.push(source.clone());
229                path.reverse();
230                return Some(path);
231            }
232
233            for neighbor in self.neighbors(&current) {
234                if !visited.contains(&neighbor.id) {
235                    visited.insert(neighbor.id.clone());
236                    parent.insert(neighbor.id.clone(), current.clone());
237                    queue.push_back(neighbor.id.clone());
238                }
239            }
240        }
241
242        None
243    }
244
245    /// Check if the graph contains a vertex
246    pub fn contains_vertex(&self, id: &VertexId) -> bool {
247        self.vertices.contains_key(id)
248    }
249
250    /// Check if the graph contains an edge
251    pub fn contains_edge(&self, id: &EdgeId) -> bool {
252        self.edges.contains_key(id)
253    }
254
255    /// Get the number of vertices
256    pub fn vertex_count(&self) -> usize {
257        self.vertices.len()
258    }
259
260    /// Get the number of edges
261    pub fn edge_count(&self) -> usize {
262        self.edges.len()
263    }
264
265    /// Check if the graph is empty
266    pub fn is_empty(&self) -> bool {
267        self.vertex_count() == 0
268    }
269
270    /// Clear all vertices and edges
271    pub fn clear(&mut self) {
272        self.vertices.clear();
273        self.edges.clear();
274    }
275}
276
277impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for RemoveWinsGraph<T> {
278    fn replica_id(&self) -> &ReplicaId {
279        &self.replica
280    }
281}
282
283impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for RemoveWinsGraph<T> {
284    type Error = GraphError;
285
286    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
287        // Merge vertices
288        for (id, vertex) in &other.vertices {
289            match self.vertices.get(id) {
290                Some(existing) => {
291                    // Conflict resolution: later timestamp wins
292                    if vertex.metadata.modified_at > existing.metadata.modified_at {
293                        self.vertices.insert(id.clone(), vertex.clone());
294                    }
295                }
296                None => {
297                    // New vertex, add it
298                    self.vertices.insert(id.clone(), vertex.clone());
299                }
300            }
301        }
302
303        // Merge edges
304        for (id, edge) in &other.edges {
305            match self.edges.get(id) {
306                Some(existing) => {
307                    // Conflict resolution: later timestamp wins
308                    if edge.metadata.modified_at > existing.metadata.modified_at {
309                        self.edges.insert(id.clone(), edge.clone());
310                    }
311                }
312                None => {
313                    // New edge, add it
314                    self.edges.insert(id.clone(), edge.clone());
315                }
316            }
317        }
318
319        Ok(())
320    }
321
322    fn has_conflict(&self, other: &Self) -> bool {
323        // Check for conflicts in overlapping vertices
324        for (id, vertex) in &other.vertices {
325            if let Some(existing) = self.vertices.get(id) {
326                if vertex.metadata.modified_at == existing.metadata.modified_at
327                    && vertex.metadata.last_modified_by != existing.metadata.last_modified_by
328                {
329                    return true;
330                }
331            }
332        }
333
334        // Check for conflicts in overlapping edges
335        for (id, edge) in &other.edges {
336            if let Some(existing) = self.edges.get(id) {
337                if edge.metadata.modified_at == existing.metadata.modified_at
338                    && edge.metadata.last_modified_by != existing.metadata.last_modified_by
339                {
340                    return true;
341                }
342            }
343        }
344        false
345    }
346}
347
348#[cfg(test)]
349mod tests {
350    use super::super::super::ReplicaId;
351    use super::*;
352    use uuid::Uuid;
353
354    fn create_replica(id: u64) -> ReplicaId {
355        ReplicaId::from(Uuid::from_u64_pair(0, id))
356    }
357
358    #[test]
359    fn test_remove_wins_graph_basic_operations() {
360        let replica = create_replica(1);
361        let mut graph = RemoveWinsGraph::new(replica);
362
363        // Add vertices and edge
364        let v1_id = graph.add_vertex("vertex1", 1000);
365        let v2_id = graph.add_vertex("vertex2", 2000);
366        let edge_id = graph.add_edge(&v1_id, &v2_id, 3000, None).unwrap();
367
368        assert_eq!(graph.vertex_count(), 2);
369        assert_eq!(graph.edge_count(), 1);
370
371        // Remove edge completely
372        graph.remove_edge(&edge_id).unwrap();
373        assert_eq!(graph.edge_count(), 0);
374        assert!(!graph.contains_edge(&edge_id));
375
376        // Remove vertex completely
377        graph.remove_vertex(&v1_id).unwrap();
378        assert_eq!(graph.vertex_count(), 1);
379        assert!(!graph.contains_vertex(&v1_id));
380    }
381
382    #[test]
383    fn test_remove_wins_graph_merge() {
384        let replica1 = create_replica(1);
385        let replica2 = create_replica(2);
386
387        let mut graph1 = RemoveWinsGraph::new(replica1);
388        let mut graph2 = RemoveWinsGraph::new(replica2);
389
390        // Add vertices to both graphs
391        let v1_id = graph1.add_vertex("vertex1", 1000);
392        let v2_id = graph2.add_vertex("vertex2", 2000);
393
394        // Merge graph2 into graph1
395        graph1.merge(&graph2).unwrap();
396
397        // Both vertices should be present
398        assert_eq!(graph1.vertex_count(), 2);
399        assert!(graph1.contains_vertex(&v1_id));
400        assert!(graph1.contains_vertex(&v2_id));
401    }
402}
leptos_sync_core/crdt/graph/remove_wins.rs

leptos_sync_core/crdt/graph/
remove_wins.rs
