leptos_sync_core/crdt/
graph.rs

1use super::{CRDT, Mergeable, ReplicaId};
2use serde::{Deserialize, Serialize};
3use std::collections::{HashMap, HashSet, VecDeque};
4use std::error::Error;
5use uuid::Uuid;
6
7/// Custom error type for graph operations
8#[derive(Debug, Clone, PartialEq, Eq)]
9pub struct GraphError {
10    message: String,
11}
12
13impl GraphError {
14    pub fn new(message: String) -> Self {
15        Self { message }
16    }
17}
18
19impl std::fmt::Display for GraphError {
20    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
21        write!(f, "GraphError: {}", self.message)
22    }
23}
24
25impl Error for GraphError {}
26
27/// Unique identifier for a graph vertex
28#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
29pub struct VertexId {
30    /// Unique identifier for the vertex
31    pub id: Uuid,
32    /// Replica that created the vertex
33    pub replica: ReplicaId,
34}
35
36impl VertexId {
37    /// Create a new vertex ID
38    pub fn new(replica: ReplicaId) -> Self {
39        Self {
40            id: Uuid::new_v4(),
41            replica,
42        }
43    }
44
45    /// Create a vertex ID from existing UUID and replica
46    pub fn from_parts(id: Uuid, replica: ReplicaId) -> Self {
47        Self { id, replica }
48    }
49}
50
51/// Unique identifier for a graph edge
52#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
53pub struct EdgeId {
54    /// Unique identifier for the edge
55    pub id: Uuid,
56    /// Replica that created the edge
57    pub replica: ReplicaId,
58}
59
60impl EdgeId {
61    /// Create a new edge ID
62    pub fn new(replica: ReplicaId) -> Self {
63        Self {
64            id: Uuid::new_v4(),
65            replica,
66        }
67    }
68
69    /// Create an edge ID from existing UUID and replica
70    pub fn from_parts(id: Uuid, replica: ReplicaId) -> Self {
71        Self { id, replica }
72    }
73}
74
75/// Metadata for a graph vertex
76#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
77pub struct VertexMetadata {
78    /// When the vertex was created
79    pub created_at: u64,
80    /// When the vertex was last modified
81    pub modified_at: u64,
82    /// Whether the vertex is marked as deleted
83    pub deleted: bool,
84    /// Replica that last modified the vertex
85    pub last_modified_by: ReplicaId,
86}
87
88impl VertexMetadata {
89    /// Create new metadata
90    pub fn new(replica: ReplicaId, timestamp: u64) -> Self {
91        Self {
92            created_at: timestamp,
93            modified_at: timestamp,
94            deleted: false,
95            last_modified_by: replica,
96        }
97    }
98
99    /// Mark as modified
100    pub fn mark_modified(&mut self, replica: ReplicaId, timestamp: u64) {
101        self.modified_at = timestamp;
102        self.last_modified_by = replica;
103    }
104
105    /// Mark as deleted
106    pub fn mark_deleted(&mut self, replica: ReplicaId, timestamp: u64) {
107        self.deleted = true;
108        self.mark_modified(replica, timestamp);
109    }
110}
111
112/// Metadata for a graph edge
113#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
114pub struct EdgeMetadata {
115    /// When the edge was created
116    pub created_at: u64,
117    /// When the edge was last modified
118    pub modified_at: u64,
119    /// Whether the edge is marked as deleted
120    pub deleted: bool,
121    /// Replica that last modified the edge
122    pub last_modified_by: ReplicaId,
123}
124
125impl EdgeMetadata {
126    /// Create new metadata
127    pub fn new(replica: ReplicaId, timestamp: u64) -> Self {
128        Self {
129            created_at: timestamp,
130            modified_at: timestamp,
131            deleted: false,
132            last_modified_by: replica,
133        }
134    }
135
136    /// Mark as modified
137    pub fn mark_modified(&mut self, replica: ReplicaId, timestamp: u64) {
138        self.modified_at = timestamp;
139        self.last_modified_by = replica;
140    }
141
142    /// Mark as deleted
143    pub fn mark_deleted(&mut self, replica: ReplicaId, timestamp: u64) {
144        self.deleted = true;
145        self.mark_modified(replica, timestamp);
146    }
147}
148
149/// A graph vertex with its metadata
150#[derive(Debug, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
151pub struct Vertex<T> {
152    /// Unique identifier
153    pub id: VertexId,
154    /// The actual value
155    pub value: T,
156    /// Metadata
157    pub metadata: VertexMetadata,
158}
159
160impl<T> Vertex<T> {
161    /// Create a new vertex
162    pub fn new(value: T, replica: ReplicaId, timestamp: u64) -> Self {
163        Self {
164            id: VertexId::new(replica),
165            value,
166            metadata: VertexMetadata::new(replica, timestamp),
167        }
168    }
169
170    /// Mark as modified
171    pub fn mark_modified(&mut self, replica: ReplicaId, timestamp: u64) {
172        self.metadata.mark_modified(replica, timestamp);
173    }
174
175    /// Mark as deleted
176    pub fn mark_deleted(&mut self, replica: ReplicaId, timestamp: u64) {
177        self.metadata.mark_deleted(replica, timestamp);
178    }
179}
180
181/// A graph edge connecting two vertices
182#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
183pub struct Edge {
184    /// Unique identifier
185    pub id: EdgeId,
186    /// Source vertex ID
187    pub source: VertexId,
188    /// Target vertex ID
189    pub target: VertexId,
190    /// Optional edge weight
191    pub weight: Option<f64>,
192    /// Metadata
193    pub metadata: EdgeMetadata,
194}
195
196impl Edge {
197    /// Create a new edge
198    pub fn new(source: VertexId, target: VertexId, replica: ReplicaId, timestamp: u64) -> Self {
199        Self {
200            id: EdgeId::new(replica),
201            source,
202            target,
203            weight: None,
204            metadata: EdgeMetadata::new(replica, timestamp),
205        }
206    }
207
208    /// Create a new edge with weight
209    pub fn with_weight(source: VertexId, target: VertexId, weight: f64, replica: ReplicaId, timestamp: u64) -> Self {
210        Self {
211            id: EdgeId::new(replica),
212            source,
213            target,
214            weight: Some(weight),
215            metadata: EdgeMetadata::new(replica, timestamp),
216        }
217    }
218
219    /// Mark as modified
220    pub fn mark_modified(&mut self, replica: ReplicaId, timestamp: u64) {
221        self.metadata.mark_modified(replica, timestamp);
222    }
223
224    /// Mark as deleted
225    pub fn mark_deleted(&mut self, replica: ReplicaId, timestamp: u64) {
226        self.metadata.mark_deleted(replica, timestamp);
227    }
228}
229
230/// Strategy for handling graph conflicts
231#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
232pub enum GraphStrategy {
233    /// Add-Wins: Vertices and edges are never removed, only marked as deleted
234    AddWins,
235    /// Remove-Wins: Deleted vertices and edges are completely removed
236    RemoveWins,
237}
238
239/// Configuration for graph CRDTs
240#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
241pub struct GraphConfig {
242    /// Conflict resolution strategy
243    pub strategy: GraphStrategy,
244    /// Whether to preserve deleted vertices and edges in metadata
245    pub preserve_deleted: bool,
246    /// Maximum number of vertices
247    pub max_vertices: Option<usize>,
248    /// Maximum number of edges
249    pub max_edges: Option<usize>,
250    /// Whether to allow self-loops
251    pub allow_self_loops: bool,
252    /// Whether to allow multiple edges between the same vertices
253    pub allow_multiple_edges: bool,
254}
255
256impl Default for GraphConfig {
257    fn default() -> Self {
258        Self {
259            strategy: GraphStrategy::AddWins,
260            preserve_deleted: true,
261            max_vertices: None,
262            max_edges: None,
263            allow_self_loops: false,
264            allow_multiple_edges: false,
265        }
266    }
267}
268
269/// Add-Wins Graph CRDT implementation
270/// 
271/// This implementation ensures that vertices and edges are never completely lost.
272/// Deleted elements are marked as deleted but preserved for potential recovery.
273#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
274pub struct AddWinsGraph<T> {
275    /// Configuration
276    config: GraphConfig,
277    /// Vertices in the graph
278    vertices: HashMap<VertexId, Vertex<T>>,
279    /// Edges in the graph
280    edges: HashMap<EdgeId, Edge>,
281    /// Replica ID for this instance
282    replica: ReplicaId,
283}
284
285impl<T: Clone + PartialEq + Eq + Send + Sync> AddWinsGraph<T> {
286    /// Create a new Add-Wins graph
287    pub fn new(replica: ReplicaId) -> Self {
288        Self {
289            config: GraphConfig::default(),
290            vertices: HashMap::new(),
291            edges: HashMap::new(),
292            replica,
293        }
294    }
295
296    /// Create with custom configuration
297    pub fn with_config(replica: ReplicaId, config: GraphConfig) -> Self {
298        Self {
299            config,
300            vertices: HashMap::new(),
301            edges: HashMap::new(),
302            replica,
303        }
304    }
305
306    /// Add a vertex to the graph
307    pub fn add_vertex(&mut self, value: T, timestamp: u64) -> VertexId {
308        let vertex = Vertex::new(value, self.replica, timestamp);
309        let id = vertex.id.clone();
310        self.vertices.insert(id.clone(), vertex);
311        id
312    }
313
314    /// Add an edge between two vertices
315    pub fn add_edge(&mut self, source: &VertexId, target: &VertexId, timestamp: u64, weight: Option<f64>) -> Result<EdgeId, GraphError> {
316        // Check if vertices exist
317        if !self.vertices.contains_key(source) || !self.vertices.contains_key(target) {
318            return Err(GraphError::new("Source or target vertex not found".to_string()));
319        }
320
321        // Check for self-loops
322        if !self.config.allow_self_loops && source == target {
323            return Err(GraphError::new("Self-loops are not allowed".to_string()));
324        }
325
326        // Check for multiple edges if not allowed
327        if !self.config.allow_multiple_edges {
328            for edge in self.edges.values() {
329                if !edge.metadata.deleted && edge.source == *source && edge.target == *target {
330                    return Err(GraphError::new("Multiple edges between same vertices not allowed".to_string()));
331                }
332            }
333        }
334
335        let edge = if let Some(w) = weight {
336            Edge::with_weight(source.clone(), target.clone(), w, self.replica, timestamp)
337        } else {
338            Edge::new(source.clone(), target.clone(), self.replica, timestamp)
339        };
340        
341        let id = edge.id.clone();
342        self.edges.insert(id.clone(), edge);
343        Ok(id)
344    }
345
346    /// Update an existing vertex
347    pub fn update_vertex(&mut self, id: &VertexId, value: T, timestamp: u64) -> Result<(), GraphError> {
348        if let Some(vertex) = self.vertices.get_mut(id) {
349            vertex.value = value;
350            vertex.mark_modified(self.replica, timestamp);
351            Ok(())
352        } else {
353            Err(GraphError::new("Vertex not found".to_string()))
354        }
355    }
356
357    /// Update an existing edge
358    pub fn update_edge(&mut self, id: &EdgeId, weight: f64, timestamp: u64) -> Result<(), GraphError> {
359        if let Some(edge) = self.edges.get_mut(id) {
360            edge.weight = Some(weight);
361            edge.mark_modified(self.replica, timestamp);
362            Ok(())
363        } else {
364            Err(GraphError::new("Edge not found".to_string()))
365        }
366    }
367
368    /// Mark a vertex as deleted
369    pub fn remove_vertex(&mut self, id: &VertexId, timestamp: u64) -> Result<(), GraphError> {
370        if let Some(vertex) = self.vertices.get_mut(id) {
371            vertex.mark_deleted(self.replica, timestamp);
372            
373            // Mark all incident edges as deleted
374            for edge in self.edges.values_mut() {
375                if !edge.metadata.deleted && (edge.source == *id || edge.target == *id) {
376                    edge.mark_deleted(self.replica, timestamp);
377                }
378            }
379            Ok(())
380        } else {
381            Err(GraphError::new("Vertex not found".to_string()))
382        }
383    }
384
385    /// Mark an edge as deleted
386    pub fn remove_edge(&mut self, id: &EdgeId, timestamp: u64) -> Result<(), GraphError> {
387        if let Some(edge) = self.edges.get_mut(id) {
388            edge.mark_deleted(self.replica, timestamp);
389            Ok(())
390        } else {
391            Err(GraphError::new("Edge not found".to_string()))
392        }
393    }
394
395    /// Get a vertex by ID
396    pub fn get_vertex(&self, id: &VertexId) -> Option<&Vertex<T>> {
397        self.vertices.get(id)
398    }
399
400    /// Get an edge by ID
401    pub fn get_edge(&self, id: &EdgeId) -> Option<&Edge> {
402        self.edges.get(id)
403    }
404
405    /// Get all visible vertices (not deleted)
406    pub fn visible_vertices(&self) -> Vec<&Vertex<T>> {
407        self.vertices
408            .values()
409            .filter(|v| !v.metadata.deleted)
410            .collect()
411    }
412
413    /// Get all visible edges (not deleted)
414    pub fn visible_edges(&self) -> Vec<&Edge> {
415        self.edges
416            .values()
417            .filter(|e| !e.metadata.deleted)
418            .collect()
419    }
420
421    /// Get all vertices including deleted ones
422    pub fn all_vertices(&self) -> Vec<&Vertex<T>> {
423        self.vertices.values().collect()
424    }
425
426    /// Get all edges including deleted ones
427    pub fn all_edges(&self) -> Vec<&Edge> {
428        self.edges.values().collect()
429    }
430
431    /// Get neighbors of a vertex
432    pub fn neighbors(&self, id: &VertexId) -> Vec<&Vertex<T>> {
433        let mut neighbors = Vec::new();
434        
435        for edge in self.edges.values() {
436            if !edge.metadata.deleted {
437                if edge.source == *id {
438                    if let Some(target) = self.vertices.get(&edge.target) {
439                        if !target.metadata.deleted {
440                            neighbors.push(target);
441                        }
442                    }
443                } else if edge.target == *id {
444                    if let Some(source) = self.vertices.get(&edge.source) {
445                        if !source.metadata.deleted {
446                            neighbors.push(source);
447                        }
448                    }
449                }
450            }
451        }
452        
453        neighbors
454    }
455
456    /// Get incoming edges to a vertex
457    pub fn incoming_edges(&self, id: &VertexId) -> Vec<&Edge> {
458        self.edges
459            .values()
460            .filter(|e| !e.metadata.deleted && e.target == *id)
461            .collect()
462    }
463
464    /// Get outgoing edges from a vertex
465    pub fn outgoing_edges(&self, id: &VertexId) -> Vec<&Edge> {
466        self.edges
467            .values()
468            .filter(|e| !e.metadata.deleted && e.source == *id)
469            .collect()
470    }
471
472    /// Find shortest path between two vertices using BFS
473    pub fn shortest_path(&self, source: &VertexId, target: &VertexId) -> Option<Vec<VertexId>> {
474        if !self.vertices.contains_key(source) || !self.vertices.contains_key(target) {
475            return None;
476        }
477
478        let mut visited = HashSet::new();
479        let mut queue = VecDeque::new();
480        let mut parent: HashMap<VertexId, VertexId> = HashMap::new();
481        
482        queue.push_back(source.clone());
483        visited.insert(source.clone());
484        
485        while let Some(current) = queue.pop_front() {
486            if current == *target {
487                // Reconstruct path
488                let mut path = Vec::new();
489                let mut current_id = current;
490                
491                while current_id != *source {
492                    path.push(current_id.clone());
493                    current_id = parent[&current_id].clone();
494                }
495                path.push(source.clone());
496                path.reverse();
497                return Some(path);
498            }
499            
500            for neighbor in self.neighbors(&current) {
501                if !visited.contains(&neighbor.id) {
502                    visited.insert(neighbor.id.clone());
503                    parent.insert(neighbor.id.clone(), current.clone());
504                    queue.push_back(neighbor.id.clone());
505                }
506            }
507        }
508        
509        None
510    }
511
512    /// Check if the graph contains a vertex
513    pub fn contains_vertex(&self, id: &VertexId) -> bool {
514        self.vertices.contains_key(id)
515    }
516
517    /// Check if the graph contains an edge
518    pub fn contains_edge(&self, id: &EdgeId) -> bool {
519        self.edges.contains_key(id)
520    }
521
522    /// Get the number of visible vertices
523    pub fn vertex_count(&self) -> usize {
524        self.visible_vertices().len()
525    }
526
527    /// Get the number of visible edges
528    pub fn edge_count(&self) -> usize {
529        self.visible_edges().len()
530    }
531
532    /// Check if the graph is empty
533    pub fn is_empty(&self) -> bool {
534        self.vertex_count() == 0
535    }
536
537    /// Clear all vertices and edges
538    pub fn clear(&mut self) {
539        self.vertices.clear();
540        self.edges.clear();
541    }
542}
543
544impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for AddWinsGraph<T> {
545    fn replica_id(&self) -> &ReplicaId {
546        &self.replica
547    }
548}
549
550impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for AddWinsGraph<T> {
551    type Error = GraphError;
552
553    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
554        // Merge vertices
555        for (id, vertex) in &other.vertices {
556            match self.vertices.get(id) {
557                Some(existing) => {
558                    // Conflict resolution: later timestamp wins
559                    if vertex.metadata.modified_at > existing.metadata.modified_at {
560                        self.vertices.insert(id.clone(), vertex.clone());
561                    }
562                }
563                None => {
564                    // New vertex, add it
565                    self.vertices.insert(id.clone(), vertex.clone());
566                }
567            }
568        }
569
570        // Merge edges
571        for (id, edge) in &other.edges {
572            match self.edges.get(id) {
573                Some(existing) => {
574                    // Conflict resolution: later timestamp wins
575                    if edge.metadata.modified_at > existing.metadata.modified_at {
576                        self.edges.insert(id.clone(), edge.clone());
577                    }
578                }
579                None => {
580                    // New edge, add it
581                    self.edges.insert(id.clone(), edge.clone());
582                }
583            }
584        }
585        
586        Ok(())
587    }
588
589    fn has_conflict(&self, other: &Self) -> bool {
590        // Check for conflicts in overlapping vertices
591        for (id, vertex) in &other.vertices {
592            if let Some(existing) = self.vertices.get(id) {
593                if vertex.metadata.modified_at == existing.metadata.modified_at
594                    && vertex.metadata.last_modified_by != existing.metadata.last_modified_by
595                {
596                    return true;
597                }
598            }
599        }
600
601        // Check for conflicts in overlapping edges
602        for (id, edge) in &other.edges {
603            if let Some(existing) = self.edges.get(id) {
604                if edge.metadata.modified_at == existing.metadata.modified_at
605                    && edge.metadata.last_modified_by != existing.metadata.last_modified_by
606                {
607                    return true;
608                }
609            }
610        }
611        false
612    }
613}
614
615/// Remove-Wins Graph CRDT implementation
616/// 
617/// This implementation completely removes deleted vertices and edges.
618/// It's more memory-efficient but elements cannot be recovered.
619#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
620pub struct RemoveWinsGraph<T> {
621    /// Configuration
622    config: GraphConfig,
623    /// Vertices in the graph
624    vertices: HashMap<VertexId, Vertex<T>>,
625    /// Edges in the graph
626    edges: HashMap<EdgeId, Edge>,
627    /// Replica ID for this instance
628    replica: ReplicaId,
629}
630
631impl<T: Clone + PartialEq + Eq + Send + Sync> RemoveWinsGraph<T> {
632    /// Create a new Remove-Wins graph
633    pub fn new(replica: ReplicaId) -> Self {
634        Self {
635            config: GraphConfig {
636                strategy: GraphStrategy::RemoveWins,
637                preserve_deleted: false,
638                max_vertices: None,
639                max_edges: None,
640                allow_self_loops: false,
641                allow_multiple_edges: false,
642            },
643            vertices: HashMap::new(),
644            edges: HashMap::new(),
645            replica,
646        }
647    }
648
649    /// Create with custom configuration
650    pub fn with_config(replica: ReplicaId, config: GraphConfig) -> Self {
651        Self {
652            config,
653            vertices: HashMap::new(),
654            edges: HashMap::new(),
655            replica,
656        }
657    }
658
659    /// Add a vertex to the graph
660    pub fn add_vertex(&mut self, value: T, timestamp: u64) -> VertexId {
661        let vertex = Vertex::new(value, self.replica, timestamp);
662        let id = vertex.id.clone();
663        self.vertices.insert(id.clone(), vertex);
664        id
665    }
666
667    /// Add an edge between two vertices
668    pub fn add_edge(&mut self, source: &VertexId, target: &VertexId, timestamp: u64, weight: Option<f64>) -> Result<EdgeId, GraphError> {
669        // Check if vertices exist
670        if !self.vertices.contains_key(source) || !self.vertices.contains_key(target) {
671            return Err(GraphError::new("Source or target vertex not found".to_string()));
672        }
673
674        // Check for self-loops
675        if !self.config.allow_self_loops && source == target {
676            return Err(GraphError::new("Self-loops are not allowed".to_string()));
677        }
678
679        // Check for multiple edges if not allowed
680        if !self.config.allow_multiple_edges {
681            for edge in self.edges.values() {
682                if edge.source == *source && edge.target == *target {
683                    return Err(GraphError::new("Multiple edges between same vertices not allowed".to_string()));
684                }
685            }
686        }
687
688        let edge = if let Some(w) = weight {
689            Edge::with_weight(source.clone(), target.clone(), w, self.replica, timestamp)
690        } else {
691            Edge::new(source.clone(), target.clone(), self.replica, timestamp)
692        };
693        
694        let id = edge.id.clone();
695        self.edges.insert(id.clone(), edge);
696        Ok(id)
697    }
698
699    /// Update an existing vertex
700    pub fn update_vertex(&mut self, id: &VertexId, value: T, timestamp: u64) -> Result<(), GraphError> {
701        if let Some(vertex) = self.vertices.get_mut(id) {
702            vertex.value = value;
703            vertex.mark_modified(self.replica, timestamp);
704            Ok(())
705        } else {
706            Err(GraphError::new("Vertex not found".to_string()))
707        }
708    }
709
710    /// Update an existing edge
711    pub fn update_edge(&mut self, id: &EdgeId, weight: f64, timestamp: u64) -> Result<(), GraphError> {
712        if let Some(edge) = self.edges.get_mut(id) {
713            edge.weight = Some(weight);
714            edge.mark_modified(self.replica, timestamp);
715            Ok(())
716        } else {
717            Err(GraphError::new("Edge not found".to_string()))
718        }
719    }
720
721    /// Remove a vertex completely
722    pub fn remove_vertex(&mut self, id: &VertexId) -> Result<(), GraphError> {
723        if self.vertices.remove(id).is_some() {
724            // Remove all incident edges
725            self.edges.retain(|_, edge| edge.source != *id && edge.target != *id);
726            Ok(())
727        } else {
728            Err(GraphError::new("Vertex not found".to_string()))
729        }
730    }
731
732    /// Remove an edge completely
733    pub fn remove_edge(&mut self, id: &EdgeId) -> Result<(), GraphError> {
734        if self.edges.remove(id).is_some() {
735            Ok(())
736        } else {
737            Err(GraphError::new("Edge not found".to_string()))
738        }
739    }
740
741    /// Get a vertex by ID
742    pub fn get_vertex(&self, id: &VertexId) -> Option<&Vertex<T>> {
743        self.vertices.get(id)
744    }
745
746    /// Get an edge by ID
747    pub fn get_edge(&self, id: &EdgeId) -> Option<&Edge> {
748        self.edges.get(id)
749    }
750
751    /// Get all vertices
752    pub fn vertices(&self) -> Vec<&Vertex<T>> {
753        self.vertices.values().collect()
754    }
755
756    /// Get all edges
757    pub fn edges(&self) -> Vec<&Edge> {
758        self.edges.values().collect()
759    }
760
761    /// Get neighbors of a vertex
762    pub fn neighbors(&self, id: &VertexId) -> Vec<&Vertex<T>> {
763        let mut neighbors = Vec::new();
764        
765        for edge in self.edges.values() {
766            if edge.source == *id {
767                if let Some(target) = self.vertices.get(&edge.target) {
768                    neighbors.push(target);
769                }
770            } else if edge.target == *id {
771                if let Some(source) = self.vertices.get(&edge.source) {
772                    neighbors.push(source);
773                }
774            }
775        }
776        
777        neighbors
778    }
779
780    /// Get incoming edges to a vertex
781    pub fn incoming_edges(&self, id: &VertexId) -> Vec<&Edge> {
782        self.edges
783            .values()
784            .filter(|e| e.target == *id)
785            .collect()
786    }
787
788    /// Get outgoing edges from a vertex
789    pub fn outgoing_edges(&self, id: &VertexId) -> Vec<&Edge> {
790        self.edges
791            .values()
792            .filter(|e| e.source == *id)
793            .collect()
794    }
795
796    /// Find shortest path between two vertices using BFS
797    pub fn shortest_path(&self, source: &VertexId, target: &VertexId) -> Option<Vec<VertexId>> {
798        if !self.vertices.contains_key(source) || !self.vertices.contains_key(target) {
799            return None;
800        }
801
802        let mut visited = HashSet::new();
803        let mut queue = VecDeque::new();
804        let mut parent: HashMap<VertexId, VertexId> = HashMap::new();
805        
806        queue.push_back(source.clone());
807        visited.insert(source.clone());
808        
809        while let Some(current) = queue.pop_front() {
810            if current == *target {
811                // Reconstruct path
812                let mut path = Vec::new();
813                let mut current_id = current;
814                
815                while current_id != *source {
816                    path.push(current_id.clone());
817                    current_id = parent[&current_id].clone();
818                }
819                path.push(source.clone());
820                path.reverse();
821                return Some(path);
822            }
823            
824            for neighbor in self.neighbors(&current) {
825                if !visited.contains(&neighbor.id) {
826                    visited.insert(neighbor.id.clone());
827                    parent.insert(neighbor.id.clone(), current.clone());
828                    queue.push_back(neighbor.id.clone());
829                }
830            }
831        }
832        
833        None
834    }
835
836    /// Check if the graph contains a vertex
837    pub fn contains_vertex(&self, id: &VertexId) -> bool {
838        self.vertices.contains_key(id)
839    }
840
841    /// Check if the graph contains an edge
842    pub fn contains_edge(&self, id: &EdgeId) -> bool {
843        self.edges.contains_key(id)
844    }
845
846    /// Get the number of vertices
847    pub fn vertex_count(&self) -> usize {
848        self.vertices.len()
849    }
850
851    /// Get the number of edges
852    pub fn edge_count(&self) -> usize {
853        self.edges.len()
854    }
855
856    /// Check if the graph is empty
857    pub fn is_empty(&self) -> bool {
858        self.vertex_count() == 0
859    }
860
861    /// Clear all vertices and edges
862    pub fn clear(&mut self) {
863        self.vertices.clear();
864        self.edges.clear();
865    }
866}
867
868impl<T: Clone + PartialEq + Eq + Send + Sync> CRDT for RemoveWinsGraph<T> {
869    fn replica_id(&self) -> &ReplicaId {
870        &self.replica
871    }
872}
873
874impl<T: Clone + PartialEq + Eq + Send + Sync> Mergeable for RemoveWinsGraph<T> {
875    type Error = GraphError;
876
877    fn merge(&mut self, other: &Self) -> Result<(), Self::Error> {
878        // Merge vertices
879        for (id, vertex) in &other.vertices {
880            match self.vertices.get(id) {
881                Some(existing) => {
882                    // Conflict resolution: later timestamp wins
883                    if vertex.metadata.modified_at > existing.metadata.modified_at {
884                        self.vertices.insert(id.clone(), vertex.clone());
885                    }
886                }
887                None => {
888                    // New vertex, add it
889                    self.vertices.insert(id.clone(), vertex.clone());
890                }
891            }
892        }
893
894        // Merge edges
895        for (id, edge) in &other.edges {
896            match self.edges.get(id) {
897                Some(existing) => {
898                    // Conflict resolution: later timestamp wins
899                    if edge.metadata.modified_at > existing.metadata.modified_at {
900                        self.edges.insert(id.clone(), edge.clone());
901                    }
902                }
903                None => {
904                    // New edge, add it
905                    self.edges.insert(id.clone(), edge.clone());
906                }
907            }
908        }
909        
910        Ok(())
911    }
912
913    fn has_conflict(&self, other: &Self) -> bool {
914        // Check for conflicts in overlapping vertices
915        for (id, vertex) in &other.vertices {
916            if let Some(existing) = self.vertices.get(id) {
917                if vertex.metadata.modified_at == existing.metadata.modified_at
918                    && vertex.metadata.last_modified_by != existing.metadata.last_modified_by
919                {
920                    return true;
921                }
922            }
923        }
924
925        // Check for conflicts in overlapping edges
926        for (id, edge) in &other.edges {
927            if let Some(existing) = self.edges.get(id) {
928                if edge.metadata.modified_at == existing.metadata.modified_at
929                    && edge.metadata.last_modified_by != existing.metadata.last_modified_by
930                {
931                    return true;
932                }
933            }
934        }
935        false
936    }
937}
938
939#[cfg(test)]
940mod tests {
941    use super::*;
942    use super::super::ReplicaId;
943    use uuid::Uuid;
944
945    fn create_replica(id: u64) -> ReplicaId {
946        ReplicaId::from(Uuid::from_u64_pair(0, id))
947    }
948
949    #[test]
950    fn test_vertex_id_creation() {
951        let replica = create_replica(1);
952        let vertex_id = VertexId::new(replica);
953        
954        assert_eq!(vertex_id.replica, replica);
955        assert_ne!(vertex_id.id, Uuid::nil());
956    }
957
958    #[test]
959    fn test_edge_id_creation() {
960        let replica = create_replica(1);
961        let edge_id = EdgeId::new(replica);
962        
963        assert_eq!(edge_id.replica, replica);
964        assert_ne!(edge_id.id, Uuid::nil());
965    }
966
967    #[test]
968    fn test_vertex_creation() {
969        let replica = create_replica(1);
970        let timestamp = 1234567890;
971        let vertex = Vertex::new("test_value", replica, timestamp);
972        
973        assert_eq!(vertex.value, "test_value");
974        assert_eq!(vertex.metadata.created_at, timestamp);
975        assert_eq!(vertex.metadata.modified_at, timestamp);
976        assert_eq!(vertex.metadata.deleted, false);
977        assert_eq!(vertex.metadata.last_modified_by, replica);
978    }
979
980    #[test]
981    fn test_edge_creation() {
982        let replica = create_replica(1);
983        let timestamp = 1234567890;
984        let source = VertexId::new(replica);
985        let target = VertexId::new(replica);
986        let edge = Edge::new(source.clone(), target.clone(), replica, timestamp);
987        
988        assert_eq!(edge.source, source);
989        assert_eq!(edge.target, target);
990        assert_eq!(edge.weight, None);
991        assert_eq!(edge.metadata.created_at, timestamp);
992        assert_eq!(edge.metadata.deleted, false);
993    }
994
995    #[test]
996    fn test_edge_with_weight() {
997        let replica = create_replica(1);
998        let timestamp = 1234567890;
999        let source = VertexId::new(replica);
1000        let target = VertexId::new(replica);
1001        let weight = 5.5;
1002        let edge = Edge::with_weight(source.clone(), target.clone(), weight, replica, timestamp);
1003        
1004        assert_eq!(edge.weight, Some(weight));
1005    }
1006
1007    #[test]
1008    fn test_add_wins_graph_basic_operations() {
1009        let replica = create_replica(1);
1010        let mut graph = AddWinsGraph::new(replica);
1011        
1012        // Add vertices
1013        let v1_id = graph.add_vertex("vertex1", 1000);
1014        let v2_id = graph.add_vertex("vertex2", 2000);
1015        
1016        assert_eq!(graph.vertex_count(), 2);
1017        assert!(graph.contains_vertex(&v1_id));
1018        assert!(graph.contains_vertex(&v2_id));
1019        
1020        // Add edge
1021        let edge_id = graph.add_edge(&v1_id, &v2_id, 3000, None).unwrap();
1022        assert_eq!(graph.edge_count(), 1);
1023        assert!(graph.contains_edge(&edge_id));
1024        
1025        // Update vertex
1026        graph.update_vertex(&v1_id, "updated_vertex1", 4000).unwrap();
1027        assert_eq!(graph.get_vertex(&v1_id).unwrap().value, "updated_vertex1");
1028    }
1029
1030    #[test]
1031    fn test_remove_wins_graph_basic_operations() {
1032        let replica = create_replica(1);
1033        let mut graph = RemoveWinsGraph::new(replica);
1034        
1035        // Add vertices and edge
1036        let v1_id = graph.add_vertex("vertex1", 1000);
1037        let v2_id = graph.add_vertex("vertex2", 2000);
1038        let edge_id = graph.add_edge(&v1_id, &v2_id, 3000, None).unwrap();
1039        
1040        assert_eq!(graph.vertex_count(), 2);
1041        assert_eq!(graph.edge_count(), 1);
1042        
1043        // Remove edge completely
1044        graph.remove_edge(&edge_id).unwrap();
1045        assert_eq!(graph.edge_count(), 0);
1046        assert!(!graph.contains_edge(&edge_id));
1047        
1048        // Remove vertex completely
1049        graph.remove_vertex(&v1_id).unwrap();
1050        assert_eq!(graph.vertex_count(), 1);
1051        assert!(!graph.contains_vertex(&v1_id));
1052    }
1053
1054    #[test]
1055    fn test_graph_neighbors() {
1056        let replica = create_replica(1);
1057        let mut graph = AddWinsGraph::new(replica);
1058        
1059        // Create triangle: v1 -> v2 -> v3 -> v1
1060        let v1_id = graph.add_vertex("vertex1", 1000);
1061        let v2_id = graph.add_vertex("vertex2", 2000);
1062        let v3_id = graph.add_vertex("vertex3", 3000);
1063        
1064        graph.add_edge(&v1_id, &v2_id, 4000, None).unwrap();
1065        graph.add_edge(&v2_id, &v3_id, 5000, None).unwrap();
1066        graph.add_edge(&v3_id, &v1_id, 6000, None).unwrap();
1067        
1068        // Check neighbors
1069        let v1_neighbors = graph.neighbors(&v1_id);
1070        assert_eq!(v1_neighbors.len(), 2); // v2 and v3
1071        
1072        let v2_neighbors = graph.neighbors(&v2_id);
1073        assert_eq!(v2_neighbors.len(), 2); // v1 and v3
1074        
1075        let v3_neighbors = graph.neighbors(&v3_id);
1076        assert_eq!(v3_neighbors.len(), 2); // v1 and v2
1077    }
1078
1079    #[test]
1080    fn test_graph_shortest_path() {
1081        let replica = create_replica(1);
1082        let mut graph = AddWinsGraph::new(replica);
1083        
1084        // Create path: v1 -> v2 -> v3 -> v4
1085        let v1_id = graph.add_vertex("vertex1", 1000);
1086        let v2_id = graph.add_vertex("vertex2", 2000);
1087        let v3_id = graph.add_vertex("vertex3", 3000);
1088        let v4_id = graph.add_vertex("vertex4", 4000);
1089        
1090        graph.add_edge(&v1_id, &v2_id, 5000, None).unwrap();
1091        graph.add_edge(&v2_id, &v3_id, 6000, None).unwrap();
1092        graph.add_edge(&v3_id, &v4_id, 7000, None).unwrap();
1093        
1094        // Find shortest path
1095        let path = graph.shortest_path(&v1_id, &v4_id).unwrap();
1096        assert_eq!(path.len(), 4);
1097        assert_eq!(path[0], v1_id);
1098        assert_eq!(path[1], v2_id);
1099        assert_eq!(path[2], v3_id);
1100        assert_eq!(path[3], v4_id);
1101    }
1102
1103    #[test]
1104    fn test_graph_merge() {
1105        let replica1 = create_replica(1);
1106        let replica2 = create_replica(2);
1107        
1108        let mut graph1 = AddWinsGraph::new(replica1);
1109        let mut graph2 = AddWinsGraph::new(replica2);
1110        
1111        // Add vertices to both graphs
1112        let v1_id = graph1.add_vertex("vertex1", 1000);
1113        let v2_id = graph2.add_vertex("vertex2", 2000);
1114        
1115        // Merge graph2 into graph1
1116        graph1.merge(&graph2).unwrap();
1117        
1118        // Both vertices should be present
1119        assert_eq!(graph1.vertex_count(), 2);
1120        assert!(graph1.contains_vertex(&v1_id));
1121        assert!(graph1.contains_vertex(&v2_id));
1122    }
1123
1124    #[test]
1125    fn test_graph_configuration() {
1126        let replica = create_replica(1);
1127        let config = GraphConfig {
1128            strategy: GraphStrategy::RemoveWins,
1129            preserve_deleted: false,
1130            max_vertices: Some(100),
1131            max_edges: Some(200),
1132            allow_self_loops: true,
1133            allow_multiple_edges: true,
1134        };
1135        
1136        let graph: AddWinsGraph<String> = AddWinsGraph::with_config(replica, config);
1137        assert_eq!(graph.config.strategy, GraphStrategy::RemoveWins);
1138        assert_eq!(graph.config.max_vertices, Some(100));
1139        assert_eq!(graph.config.allow_self_loops, true);
1140        assert_eq!(graph.config.allow_multiple_edges, true);
1141    }
1142
1143    #[test]
1144    fn test_graph_validation() {
1145        let replica = create_replica(1);
1146        let mut graph = AddWinsGraph::new(replica);
1147        
1148        // Add vertices
1149        let v1_id = graph.add_vertex("vertex1", 1000);
1150        let v2_id = graph.add_vertex("vertex2", 2000);
1151        
1152        // Try to add edge with non-existent vertex
1153        let fake_id = VertexId::new(create_replica(999));
1154        let result = graph.add_edge(&v1_id, &fake_id, 3000, None);
1155        assert!(result.is_err());
1156        
1157        // Try to add edge to itself (self-loop not allowed by default)
1158        let result = graph.add_edge(&v1_id, &v1_id, 3000, None);
1159        assert!(result.is_err());
1160    }
1161}
leptos_sync_core/crdt/graph.rs

leptos_sync_core/crdt/
graph.rs
