reddb_server/storage/engine/
pathfinding.rs

1//! Path Finding Algorithms for RedDB
2//!
3//! Shortest path and graph traversal algorithms optimized for attack path analysis:
4//! - BFS: Unweighted shortest paths
5//! - DFS: Deep exploration with backtracking
6//! - Dijkstra: Weighted shortest paths (non-negative weights)
7//! - A*: Heuristic-guided shortest paths
8//! - Bellman-Ford: Handles negative weights
9//! - All Shortest Paths: Find all minimum-length paths
10//! - K-Shortest Paths: Find k best paths (Yen's algorithm)
11//!
12//! # Security Use Cases
13//!
14//! - **Attack Path Analysis**: Find shortest exploitation paths
15//! - **Lateral Movement**: Discover movement paths between hosts
16//! - **Privilege Escalation**: Map paths to high-value targets
17//! - **Risk Assessment**: Weight paths by exploit difficulty
18
19use std::cmp::Ordering;
20use std::collections::{BinaryHeap, HashMap, HashSet, VecDeque};
21
22use super::graph_store::GraphStore;
23
24// ============================================================================
25// Path Result Types
26// ============================================================================
27
28/// A path through the graph
29#[derive(Debug, Clone)]
30pub struct Path {
31    /// Ordered list of node IDs from source to target
32    pub nodes: Vec<String>,
33    /// Total weight/cost of the path
34    pub total_weight: f64,
35    /// Edge labels along the path (canonical lower-snake-case strings).
36    /// Resolved against the graph's [`crate::storage::engine::graph_store::LabelRegistry`]
37    /// when the caller needs the original `LabelId`.
38    pub edge_types: Vec<String>,
39}
40
41impl Path {
42    /// Create a path with a single node (start)
43    pub fn start(node: &str) -> Self {
44        Self {
45            nodes: vec![node.to_string()],
46            total_weight: 0.0,
47            edge_types: Vec::new(),
48        }
49    }
50
51    /// Extend path with a new node + edge label.
52    pub fn extend(&self, node: &str, edge_label: impl Into<String>, weight: f64) -> Self {
53        let mut nodes = self.nodes.clone();
54        nodes.push(node.to_string());
55        let mut edge_types = self.edge_types.clone();
56        edge_types.push(edge_label.into());
57        Self {
58            nodes,
59            total_weight: self.total_weight + weight,
60            edge_types,
61        }
62    }
63
64    /// Path length (number of edges)
65    pub fn len(&self) -> usize {
66        self.nodes.len().saturating_sub(1)
67    }
68
69    /// Check if path is empty
70    pub fn is_empty(&self) -> bool {
71        self.nodes.is_empty()
72    }
73
74    /// Get source node
75    pub fn source(&self) -> Option<&str> {
76        self.nodes.first().map(|s| s.as_str())
77    }
78
79    /// Get target node
80    pub fn target(&self) -> Option<&str> {
81        self.nodes.last().map(|s| s.as_str())
82    }
83}
84
85/// Result of a shortest path query
86#[derive(Debug, Clone)]
87pub struct ShortestPathResult {
88    /// The shortest path (None if no path exists)
89    pub path: Option<Path>,
90    /// Number of nodes visited during search
91    pub nodes_visited: usize,
92}
93
94impl ShortestPathResult {
95    /// Check if a path was found
96    pub fn found(&self) -> bool {
97        self.path.is_some()
98    }
99
100    /// Get the path length
101    pub fn distance(&self) -> Option<usize> {
102        self.path.as_ref().map(|p| p.len())
103    }
104
105    /// Get the total weight
106    pub fn total_weight(&self) -> Option<f64> {
107        self.path.as_ref().map(|p| p.total_weight)
108    }
109}
110
111/// Result of all shortest paths query
112#[derive(Debug, Clone)]
113pub struct AllPathsResult {
114    /// All shortest paths found
115    pub paths: Vec<Path>,
116    /// Number of nodes visited during search
117    pub nodes_visited: usize,
118}
119
120// ============================================================================
121// BFS - Breadth-First Search
122// ============================================================================
123
124/// Breadth-First Search for unweighted shortest paths
125///
126/// Use when all edges have equal weight (or you only care about hop count).
127/// Time: O(V + E), Space: O(V)
128pub struct BFS;
129
130mod bfs_impl;
131
132// ============================================================================
133// DFS - Depth-First Search
134// ============================================================================
135
136/// Depth-First Search for deep graph exploration
137///
138/// Use for finding paths, detecting cycles, topological sorting.
139/// Time: O(V + E), Space: O(V)
140pub struct DFS;
141
142mod dfs_impl;
143// ============================================================================
144// Dijkstra - Weighted Shortest Paths
145// ============================================================================
146
147/// State for Dijkstra's priority queue
148#[derive(Clone)]
149struct DijkstraState {
150    node: String,
151    cost: f64,
152    path: Path,
153}
154
155impl Eq for DijkstraState {}
156
157impl PartialEq for DijkstraState {
158    fn eq(&self, other: &Self) -> bool {
159        self.node == other.node && (self.cost - other.cost).abs() < f64::EPSILON
160    }
161}
162
163impl Ord for DijkstraState {
164    fn cmp(&self, other: &Self) -> Ordering {
165        // Reverse ordering for min-heap
166        other
167            .cost
168            .partial_cmp(&self.cost)
169            .unwrap_or(Ordering::Equal)
170    }
171}
172
173impl PartialOrd for DijkstraState {
174    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
175        Some(self.cmp(other))
176    }
177}
178
179/// Dijkstra's Algorithm for weighted shortest paths
180///
181/// Use when edges have non-negative weights (e.g., exploit difficulty).
182/// Time: O((V + E) log V), Space: O(V)
183pub struct Dijkstra;
184
185mod dijkstra_impl;
186
187// ============================================================================
188// A* - Heuristic Shortest Paths
189// ============================================================================
190
191/// A* state for priority queue
192#[derive(Clone)]
193struct AStarState {
194    node: String,
195    g_cost: f64, // Actual cost from start
196    f_cost: f64, // g_cost + heuristic
197    path: Path,
198}
199
200impl Eq for AStarState {}
201
202impl PartialEq for AStarState {
203    fn eq(&self, other: &Self) -> bool {
204        self.node == other.node && (self.f_cost - other.f_cost).abs() < f64::EPSILON
205    }
206}
207
208impl Ord for AStarState {
209    fn cmp(&self, other: &Self) -> Ordering {
210        other
211            .f_cost
212            .partial_cmp(&self.f_cost)
213            .unwrap_or(Ordering::Equal)
214    }
215}
216
217impl PartialOrd for AStarState {
218    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
219        Some(self.cmp(other))
220    }
221}
222
223/// A* Algorithm for heuristic-guided shortest paths
224///
225/// Use when you have a heuristic estimate of distance to target.
226/// Faster than Dijkstra when heuristic is good.
227/// Time: O((V + E) log V) typical, Space: O(V)
228pub struct AStar;
229
230mod astar_impl;
231
232// ============================================================================
233// Bellman-Ford - Handles Negative Weights
234// ============================================================================
235
236/// Result of Bellman-Ford algorithm
237#[derive(Debug, Clone)]
238pub struct BellmanFordResult {
239    /// Shortest path to target (None if no path or negative cycle)
240    pub path: Option<Path>,
241    /// Distances from source to all reachable nodes
242    pub distances: HashMap<String, f64>,
243    /// Whether a negative cycle was detected
244    pub has_negative_cycle: bool,
245    /// Nodes visited during computation
246    pub nodes_visited: usize,
247}
248
249/// Bellman-Ford Algorithm for graphs with negative weights
250///
251/// Use when edges can have negative weights.
252/// Also detects negative cycles.
253/// Time: O(V * E), Space: O(V)
254pub struct BellmanFord;
255
256mod bellman_ford_impl;
257
258// ============================================================================
259// K-Shortest Paths (Yen's Algorithm)
260// ============================================================================
261
262/// K-Shortest Paths using Yen's Algorithm
263///
264/// Find the k shortest loopless paths from source to target.
265/// Useful for finding alternative attack paths.
266/// Time: O(k * V * (V + E) log V), Space: O(k * V)
267pub struct KShortestPaths;
268
269mod k_shortest_impl;
270
271/// Candidate path for k-shortest paths
272struct PathCandidate {
273    path: Path,
274}
275
276impl Eq for PathCandidate {}
277
278impl PartialEq for PathCandidate {
279    fn eq(&self, other: &Self) -> bool {
280        (self.path.total_weight - other.path.total_weight).abs() < f64::EPSILON
281    }
282}
283
284impl Ord for PathCandidate {
285    fn cmp(&self, other: &Self) -> Ordering {
286        other
287            .path
288            .total_weight
289            .partial_cmp(&self.path.total_weight)
290            .unwrap_or(Ordering::Equal)
291    }
292}
293
294impl PartialOrd for PathCandidate {
295    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
296        Some(self.cmp(other))
297    }
298}
299
300// ============================================================================
301// All Shortest Paths
302// ============================================================================
303
304/// Find all shortest paths (same minimum length) between two nodes
305pub struct AllShortestPaths;
306
307mod all_shortest_impl;
308
309// ============================================================================
310// Tests
311// ============================================================================
312
313#[cfg(test)]
314mod tests {
315    use super::*;
316    use crate::storage::query::test_support::{add_edge_or_panic, add_node_or_panic};
317
318    fn create_simple_graph() -> GraphStore {
319        let graph = GraphStore::new();
320
321        // A -> B -> C
322        // |    |
323        // v    v
324        // D -> E
325        add_node_or_panic(&graph, "A", "Node A", "host");
326        add_node_or_panic(&graph, "B", "Node B", "host");
327        add_node_or_panic(&graph, "C", "Node C", "host");
328        add_node_or_panic(&graph, "D", "Node D", "host");
329        add_node_or_panic(&graph, "E", "Node E", "host");
330
331        add_edge_or_panic(&graph, "A", "B", "connects_to", 1.0);
332        add_edge_or_panic(&graph, "B", "C", "connects_to", 1.0);
333        add_edge_or_panic(&graph, "A", "D", "connects_to", 1.0);
334        add_edge_or_panic(&graph, "B", "E", "connects_to", 1.0);
335        add_edge_or_panic(&graph, "D", "E", "connects_to", 1.0);
336
337        graph
338    }
339
340    fn create_weighted_graph() -> GraphStore {
341        let graph = GraphStore::new();
342
343        // A --(1)--> B --(2)--> D
344        // |          ^
345        // (4)        (1)
346        // v          |
347        // C --(1)--> E
348        add_node_or_panic(&graph, "A", "Node A", "host");
349        add_node_or_panic(&graph, "B", "Node B", "host");
350        add_node_or_panic(&graph, "C", "Node C", "host");
351        add_node_or_panic(&graph, "D", "Node D", "host");
352        add_node_or_panic(&graph, "E", "Node E", "host");
353
354        add_edge_or_panic(&graph, "A", "B", "connects_to", 1.0);
355        add_edge_or_panic(&graph, "A", "C", "connects_to", 4.0);
356        add_edge_or_panic(&graph, "B", "D", "connects_to", 2.0);
357        add_edge_or_panic(&graph, "C", "E", "connects_to", 1.0);
358        add_edge_or_panic(&graph, "E", "B", "connects_to", 1.0);
359
360        graph
361    }
362
363    // BFS Tests
364    #[test]
365    fn test_bfs_shortest_path() {
366        let graph = create_simple_graph();
367        let result = BFS::shortest_path(&graph, "A", "C");
368
369        assert!(result.found());
370        assert_eq!(result.distance(), Some(2)); // A -> B -> C
371    }
372
373    #[test]
374    fn test_bfs_same_source_target() {
375        let graph = create_simple_graph();
376        let result = BFS::shortest_path(&graph, "A", "A");
377
378        assert!(result.found());
379        assert_eq!(result.distance(), Some(0));
380    }
381
382    #[test]
383    fn test_bfs_no_path() {
384        let graph = GraphStore::new();
385        add_node_or_panic(&graph, "A", "A", "host");
386        add_node_or_panic(&graph, "B", "B", "host");
387        // No edge between A and B
388
389        let result = BFS::shortest_path(&graph, "A", "B");
390        assert!(!result.found());
391    }
392
393    #[test]
394    fn test_bfs_reachable() {
395        let graph = create_simple_graph();
396        let reachable = BFS::reachable(&graph, "A", 2);
397
398        assert!(reachable.iter().any(|(n, _)| n == "A"));
399        assert!(reachable.iter().any(|(n, _)| n == "B"));
400        assert!(reachable.iter().any(|(n, _)| n == "D"));
401    }
402
403    // DFS Tests
404    #[test]
405    fn test_dfs_find_path() {
406        let graph = create_simple_graph();
407        let result = DFS::find_path(&graph, "A", "E");
408
409        assert!(result.found());
410        // Path exists (either A->B->E or A->D->E)
411    }
412
413    #[test]
414    fn test_dfs_all_paths() {
415        let graph = create_simple_graph();
416        let result = DFS::all_paths(&graph, "A", "E", 3);
417
418        assert!(!result.paths.is_empty());
419        // Should find both A->B->E and A->D->E
420        assert!(result.paths.len() >= 2);
421    }
422
423    #[test]
424    fn test_dfs_topological_sort() {
425        let graph = GraphStore::new();
426        add_node_or_panic(&graph, "A", "A", "host");
427        add_node_or_panic(&graph, "B", "B", "host");
428        add_node_or_panic(&graph, "C", "C", "host");
429        add_edge_or_panic(&graph, "A", "B", "connects_to", 1.0);
430        add_edge_or_panic(&graph, "B", "C", "connects_to", 1.0);
431
432        let result = DFS::topological_sort(&graph);
433        assert!(result.is_some());
434
435        let order = result.unwrap();
436        let a_pos = order.iter().position(|n| n == "A").unwrap();
437        let b_pos = order.iter().position(|n| n == "B").unwrap();
438        let c_pos = order.iter().position(|n| n == "C").unwrap();
439        assert!(a_pos < b_pos);
440        assert!(b_pos < c_pos);
441    }
442
443    // Dijkstra Tests
444    #[test]
445    fn test_dijkstra_weighted() {
446        let graph = create_weighted_graph();
447        let result = Dijkstra::shortest_path(&graph, "A", "D");
448
449        assert!(result.found());
450        // Shortest path should be A->B->D (weight 3) not A->C->E->B->D (weight 7)
451        assert_eq!(result.total_weight(), Some(3.0));
452    }
453
454    #[test]
455    fn test_dijkstra_all_paths() {
456        let graph = create_weighted_graph();
457        let paths = Dijkstra::shortest_paths_from(&graph, "A");
458
459        assert!(paths.contains_key("A"));
460        assert!(paths.contains_key("B"));
461        assert!(paths.contains_key("D"));
462    }
463
464    // A* Tests
465    #[test]
466    fn test_astar_zero_heuristic() {
467        let graph = create_weighted_graph();
468        let result = AStar::shortest_path_no_heuristic(&graph, "A", "D");
469
470        // Should match Dijkstra result
471        assert!(result.found());
472        assert_eq!(result.total_weight(), Some(3.0));
473    }
474
475    // Bellman-Ford Tests
476    #[test]
477    fn test_bellman_ford_positive() {
478        let graph = create_weighted_graph();
479        let result = BellmanFord::shortest_path(&graph, "A", "D");
480
481        assert!(!result.has_negative_cycle);
482        assert!(result.path.is_some());
483    }
484
485    // K-Shortest Paths Tests
486    #[test]
487    fn test_k_shortest_paths() {
488        let graph = create_simple_graph();
489        let paths = KShortestPaths::find(&graph, "A", "E", 2);
490
491        assert!(!paths.is_empty());
492        // Should find at least 2 different paths to E
493    }
494
495    // All Shortest Paths Tests
496    #[test]
497    fn test_all_shortest_paths() {
498        let graph = create_simple_graph();
499        let result = AllShortestPaths::find(&graph, "A", "E");
500
501        // Both A->B->E and A->D->E have length 2
502        assert!(result.paths.len() >= 2);
503        for path in &result.paths {
504            assert_eq!(path.len(), 2);
505        }
506    }
507}
reddb_server/storage/engine/pathfinding.rs

reddb_server/storage/engine/
pathfinding.rs
