leptos_sync_core/crdt/graph/
algorithms.rs

1//! Graph algorithms and utilities
2
3use super::edge::Edge;
4use super::vertex::{Vertex, VertexId};
5use std::collections::{HashMap, HashSet, VecDeque};
6
7/// Graph traversal algorithms
8pub struct GraphAlgorithms;
9
10impl GraphAlgorithms {
11    /// Find shortest path between two vertices using BFS
12    pub fn shortest_path<T>(
13        vertices: &HashMap<VertexId, Vertex<T>>,
14        edges: &HashMap<super::edge::EdgeId, Edge>,
15        source: &VertexId,
16        target: &VertexId,
17    ) -> Option<Vec<VertexId>> {
18        if !vertices.contains_key(source) || !vertices.contains_key(target) {
19            return None;
20        }
21
22        let mut visited = HashSet::new();
23        let mut queue = VecDeque::new();
24        let mut parent: HashMap<VertexId, VertexId> = HashMap::new();
25
26        queue.push_back(source.clone());
27        visited.insert(source.clone());
28
29        while let Some(current) = queue.pop_front() {
30            if current == *target {
31                // Reconstruct path
32                let mut path = Vec::new();
33                let mut current_id = current;
34
35                while current_id != *source {
36                    path.push(current_id.clone());
37                    current_id = parent[&current_id].clone();
38                }
39                path.push(source.clone());
40                path.reverse();
41                return Some(path);
42            }
43
44            for neighbor in Self::get_neighbors(vertices, edges, &current) {
45                if !visited.contains(&neighbor.id) {
46                    visited.insert(neighbor.id.clone());
47                    parent.insert(neighbor.id.clone(), current.clone());
48                    queue.push_back(neighbor.id.clone());
49                }
50            }
51        }
52
53        None
54    }
55
56    /// Get neighbors of a vertex (considering only visible elements)
57    pub fn get_neighbors<'a, T>(
58        vertices: &'a HashMap<VertexId, Vertex<T>>,
59        edges: &'a HashMap<super::edge::EdgeId, Edge>,
60        id: &'a VertexId,
61    ) -> Vec<&'a Vertex<T>> {
62        let mut neighbors = Vec::new();
63
64        for edge in edges.values() {
65            if !edge.metadata.deleted {
66                if edge.source == *id {
67                    if let Some(target) = vertices.get(&edge.target) {
68                        if !target.metadata.deleted {
69                            neighbors.push(target);
70                        }
71                    }
72                } else if edge.target == *id {
73                    if let Some(source) = vertices.get(&edge.source) {
74                        if !source.metadata.deleted {
75                            neighbors.push(source);
76                        }
77                    }
78                }
79            }
80        }
81
82        neighbors
83    }
84
85    /// Get incoming edges to a vertex (considering only visible elements)
86    pub fn get_incoming_edges<'a>(
87        edges: &'a HashMap<super::edge::EdgeId, Edge>,
88        id: &'a VertexId,
89    ) -> Vec<&'a Edge> {
90        edges
91            .values()
92            .filter(|e| !e.metadata.deleted && e.target == *id)
93            .collect()
94    }
95
96    /// Get outgoing edges from a vertex (considering only visible elements)
97    pub fn get_outgoing_edges<'a>(
98        edges: &'a HashMap<super::edge::EdgeId, Edge>,
99        id: &'a VertexId,
100    ) -> Vec<&'a Edge> {
101        edges
102            .values()
103            .filter(|e| !e.metadata.deleted && e.source == *id)
104            .collect()
105    }
106
107    /// Check if graph is connected (all visible vertices reachable)
108    pub fn is_connected<T>(
109        vertices: &HashMap<VertexId, Vertex<T>>,
110        edges: &HashMap<super::edge::EdgeId, Edge>,
111    ) -> bool {
112        let visible_vertices: Vec<&VertexId> = vertices
113            .values()
114            .filter(|v| !v.metadata.deleted)
115            .map(|v| &v.id)
116            .collect();
117
118        if visible_vertices.is_empty() {
119            return true; // Empty graph is considered connected
120        }
121
122        let start = &visible_vertices[0];
123        let mut visited = HashSet::new();
124        let mut queue = VecDeque::new();
125
126        queue.push_back(start.clone());
127        visited.insert(start.clone());
128
129        while let Some(current) = queue.pop_front() {
130            for neighbor in Self::get_neighbors(vertices, edges, &current) {
131                if !visited.contains(&neighbor.id) {
132                    visited.insert(&neighbor.id);
133                    queue.push_back(&neighbor.id);
134                }
135            }
136        }
137
138        // Check if all visible vertices were visited
139        visible_vertices.iter().all(|v| visited.contains(v))
140    }
141
142    /// Find all connected components
143    pub fn connected_components<T>(
144        vertices: &HashMap<VertexId, Vertex<T>>,
145        edges: &HashMap<super::edge::EdgeId, Edge>,
146    ) -> Vec<Vec<VertexId>> {
147        let mut components = Vec::new();
148        let mut visited = HashSet::new();
149
150        for vertex in vertices.values() {
151            if !vertex.metadata.deleted && !visited.contains(&vertex.id) {
152                let mut component = Vec::new();
153                let mut queue = VecDeque::new();
154
155                queue.push_back(vertex.id.clone());
156                visited.insert(vertex.id.clone());
157                component.push(vertex.id.clone());
158
159                while let Some(current) = queue.pop_front() {
160                    for neighbor in Self::get_neighbors(vertices, edges, &current) {
161                        if !visited.contains(&neighbor.id) {
162                            visited.insert(neighbor.id.clone());
163                            queue.push_back(neighbor.id.clone());
164                            component.push(neighbor.id.clone());
165                        }
166                    }
167                }
168
169                components.push(component);
170            }
171        }
172
173        components
174    }
175
176    /// Calculate graph density (ratio of edges to maximum possible edges)
177    pub fn density<T>(
178        vertices: &HashMap<VertexId, Vertex<T>>,
179        edges: &HashMap<super::edge::EdgeId, Edge>,
180    ) -> f64 {
181        let visible_vertices: Vec<_> = vertices.values().filter(|v| !v.metadata.deleted).collect();
182
183        let visible_edges: Vec<_> = edges.values().filter(|e| !e.metadata.deleted).collect();
184
185        let n = visible_vertices.len();
186        if n <= 1 {
187            return 0.0;
188        }
189
190        let max_edges = n * (n - 1) / 2; // For undirected graph
191        visible_edges.len() as f64 / max_edges as f64
192    }
193
194    /// Find vertices with no incoming edges (sources)
195    pub fn find_sources<'a, T>(
196        vertices: &'a HashMap<VertexId, Vertex<T>>,
197        edges: &'a HashMap<super::edge::EdgeId, Edge>,
198    ) -> Vec<&'a VertexId> {
199        let mut sources = Vec::new();
200
201        for vertex in vertices.values() {
202            if !vertex.metadata.deleted {
203                let has_incoming = edges
204                    .values()
205                    .any(|e| !e.metadata.deleted && e.target == vertex.id);
206
207                if !has_incoming {
208                    sources.push(&vertex.id);
209                }
210            }
211        }
212
213        sources
214    }
215
216    /// Find vertices with no outgoing edges (sinks)
217    pub fn find_sinks<'a, T>(
218        vertices: &'a HashMap<VertexId, Vertex<T>>,
219        edges: &'a HashMap<super::edge::EdgeId, Edge>,
220    ) -> Vec<&'a VertexId> {
221        let mut sinks = Vec::new();
222
223        for vertex in vertices.values() {
224            if !vertex.metadata.deleted {
225                let has_outgoing = edges
226                    .values()
227                    .any(|e| !e.metadata.deleted && e.source == vertex.id);
228
229                if !has_outgoing {
230                    sinks.push(&vertex.id);
231                }
232            }
233        }
234
235        sinks
236    }
237}
238
239#[cfg(test)]
240mod tests {
241    use super::super::super::ReplicaId;
242    use super::super::edge::EdgeId;
243    use super::*;
244    use uuid::Uuid;
245
246    fn create_replica(id: u64) -> ReplicaId {
247        ReplicaId::from(Uuid::from_u64_pair(0, id))
248    }
249
250    #[test]
251    fn test_shortest_path() {
252        let replica = create_replica(1);
253        let mut vertices = HashMap::new();
254        let mut edges = HashMap::new();
255
256        // Create path: v1 -> v2 -> v3 -> v4
257        let v1 = Vertex::new("vertex1", replica, 1000);
258        let v2 = Vertex::new("vertex2", replica, 2000);
259        let v3 = Vertex::new("vertex3", replica, 3000);
260        let v4 = Vertex::new("vertex4", replica, 4000);
261
262        let v1_id = v1.id.clone();
263        let v2_id = v2.id.clone();
264        let v3_id = v3.id.clone();
265        let v4_id = v4.id.clone();
266
267        vertices.insert(v1_id.clone(), v1);
268        vertices.insert(v2_id.clone(), v2);
269        vertices.insert(v3_id.clone(), v3);
270        vertices.insert(v4_id.clone(), v4);
271
272        let e1 = Edge::new(v1_id.clone(), v2_id.clone(), replica, 5000);
273        let e2 = Edge::new(v2_id.clone(), v3_id.clone(), replica, 6000);
274        let e3 = Edge::new(v3_id.clone(), v4_id.clone(), replica, 7000);
275
276        edges.insert(e1.id.clone(), e1);
277        edges.insert(e2.id.clone(), e2);
278        edges.insert(e3.id.clone(), e3);
279
280        // Find shortest path
281        let path = GraphAlgorithms::shortest_path(&vertices, &edges, &v1_id, &v4_id).unwrap();
282        assert_eq!(path.len(), 4);
283        assert_eq!(path[0], v1_id);
284        assert_eq!(path[1], v2_id);
285        assert_eq!(path[2], v3_id);
286        assert_eq!(path[3], v4_id);
287    }
288
289    #[test]
290    fn test_connected_components() {
291        let replica = create_replica(1);
292        let mut vertices = HashMap::new();
293        let mut edges = HashMap::new();
294
295        // Create two disconnected components
296        let v1 = Vertex::new("vertex1", replica, 1000);
297        let v2 = Vertex::new("vertex2", replica, 2000);
298        let v3 = Vertex::new("vertex3", replica, 3000);
299        let v4 = Vertex::new("vertex4", replica, 4000);
300
301        let v1_id = v1.id.clone();
302        let v2_id = v2.id.clone();
303        let v3_id = v3.id.clone();
304        let v4_id = v4.id.clone();
305
306        vertices.insert(v1_id.clone(), v1);
307        vertices.insert(v2_id.clone(), v2);
308        vertices.insert(v3_id.clone(), v3);
309        vertices.insert(v4_id.clone(), v4);
310
311        // Connect v1-v2 and v3-v4 separately
312        let e1 = Edge::new(v1_id.clone(), v2_id.clone(), replica, 5000);
313        let e2 = Edge::new(v3_id.clone(), v4_id.clone(), replica, 6000);
314
315        edges.insert(e1.id.clone(), e1);
316        edges.insert(e2.id.clone(), e2);
317
318        let components = GraphAlgorithms::connected_components(&vertices, &edges);
319        assert_eq!(components.len(), 2);
320
321        // Each component should have 2 vertices
322        assert_eq!(components[0].len(), 2);
323        assert_eq!(components[1].len(), 2);
324    }
325
326    #[test]
327    fn test_graph_density() {
328        let replica = create_replica(1);
329        let mut vertices = HashMap::new();
330        let mut edges = HashMap::new();
331
332        // Create triangle (3 vertices, 3 edges)
333        let v1 = Vertex::new("vertex1", replica, 1000);
334        let v2 = Vertex::new("vertex2", replica, 2000);
335        let v3 = Vertex::new("vertex3", replica, 3000);
336
337        let v1_id = v1.id.clone();
338        let v2_id = v2.id.clone();
339        let v3_id = v3.id.clone();
340
341        vertices.insert(v1_id.clone(), v1);
342        vertices.insert(v2_id.clone(), v2);
343        vertices.insert(v3_id.clone(), v3);
344
345        let e1 = Edge::new(v1_id.clone(), v2_id.clone(), replica, 4000);
346        let e2 = Edge::new(v2_id.clone(), v3_id.clone(), replica, 5000);
347        let e3 = Edge::new(v3_id.clone(), v1_id.clone(), replica, 6000);
348
349        edges.insert(e1.id.clone(), e1);
350        edges.insert(e2.id.clone(), e2);
351        edges.insert(e3.id.clone(), e3);
352
353        let density = GraphAlgorithms::density(&vertices, &edges);
354        // For 3 vertices, max edges = 3, actual edges = 3, density = 1.0
355        assert_eq!(density, 1.0);
356    }
357}
leptos_sync_core/crdt/graph/algorithms.rs

leptos_sync_core/crdt/graph/
algorithms.rs
