reddb_server/storage/engine/pathfinding/
dfs_impl.rs

1use super::*;
2
3impl DFS {
4    /// Find any path from source to target (not necessarily shortest)
5    pub fn find_path(graph: &GraphStore, source: &str, target: &str) -> ShortestPathResult {
6        let mut visited: HashSet<String> = HashSet::new();
7        let mut nodes_visited = 0;
8
9        fn dfs_recursive(
10            graph: &GraphStore,
11            current: &str,
12            target: &str,
13            path: Path,
14            visited: &mut HashSet<String>,
15            nodes_visited: &mut usize,
16        ) -> Option<Path> {
17            *nodes_visited += 1;
18            visited.insert(current.to_string());
19
20            if current == target {
21                return Some(path);
22            }
23
24            for (edge_type, neighbor, weight) in graph.outgoing_edges(current) {
25                if !visited.contains(&neighbor) {
26                    let new_path = path.extend(&neighbor, edge_type, weight as f64);
27                    if let Some(result) =
28                        dfs_recursive(graph, &neighbor, target, new_path, visited, nodes_visited)
29                    {
30                        return Some(result);
31                    }
32                }
33            }
34
35            None
36        }
37
38        let path = dfs_recursive(
39            graph,
40            source,
41            target,
42            Path::start(source),
43            &mut visited,
44            &mut nodes_visited,
45        );
46
47        ShortestPathResult {
48            path,
49            nodes_visited,
50        }
51    }
52
53    /// DFS traversal returning all nodes in DFS order
54    pub fn traverse(graph: &GraphStore, source: &str) -> Vec<String> {
55        let mut visited: HashSet<String> = HashSet::new();
56        let mut result: Vec<String> = Vec::new();
57
58        fn dfs_visit(
59            graph: &GraphStore,
60            current: &str,
61            visited: &mut HashSet<String>,
62            result: &mut Vec<String>,
63        ) {
64            visited.insert(current.to_string());
65            result.push(current.to_string());
66
67            for (_, neighbor, _) in graph.outgoing_edges(current) {
68                if !visited.contains(&neighbor) {
69                    dfs_visit(graph, &neighbor, visited, result);
70                }
71            }
72        }
73
74        dfs_visit(graph, source, &mut visited, &mut result);
75        result
76    }
77
78    /// Find all paths from source to target (with depth limit)
79    pub fn all_paths(
80        graph: &GraphStore,
81        source: &str,
82        target: &str,
83        max_depth: usize,
84    ) -> AllPathsResult {
85        let mut paths: Vec<Path> = Vec::new();
86        let mut nodes_visited = 0;
87
88        fn dfs_all(
89            graph: &GraphStore,
90            target: &str,
91            path: Path,
92            max_depth: usize,
93            paths: &mut Vec<Path>,
94            visited_in_path: &mut HashSet<String>,
95            nodes_visited: &mut usize,
96        ) {
97            let current = path.nodes.last().unwrap().clone();
98            *nodes_visited += 1;
99
100            if current == target {
101                paths.push(path);
102                return;
103            }
104
105            if path.len() >= max_depth {
106                return;
107            }
108
109            for (edge_type, neighbor, weight) in graph.outgoing_edges(&current) {
110                if !visited_in_path.contains(&neighbor) {
111                    visited_in_path.insert(neighbor.clone());
112                    let new_path = path.extend(&neighbor, edge_type, weight as f64);
113                    dfs_all(
114                        graph,
115                        target,
116                        new_path,
117                        max_depth,
118                        paths,
119                        visited_in_path,
120                        nodes_visited,
121                    );
122                    visited_in_path.remove(&neighbor);
123                }
124            }
125        }
126
127        let mut visited_in_path: HashSet<String> = HashSet::new();
128        visited_in_path.insert(source.to_string());
129        dfs_all(
130            graph,
131            target,
132            Path::start(source),
133            max_depth,
134            &mut paths,
135            &mut visited_in_path,
136            &mut nodes_visited,
137        );
138
139        AllPathsResult {
140            paths,
141            nodes_visited,
142        }
143    }
144
145    /// Topological sort (returns None if graph has cycles)
146    pub fn topological_sort(graph: &GraphStore) -> Option<Vec<String>> {
147        let nodes: Vec<String> = graph.iter_nodes().map(|n| n.id.clone()).collect();
148        let mut visited: HashSet<String> = HashSet::new();
149        let mut temp_marks: HashSet<String> = HashSet::new();
150        let mut result: Vec<String> = Vec::new();
151
152        fn visit(
153            graph: &GraphStore,
154            node: &str,
155            visited: &mut HashSet<String>,
156            temp_marks: &mut HashSet<String>,
157            result: &mut Vec<String>,
158        ) -> bool {
159            if temp_marks.contains(node) {
160                return false; // Cycle detected
161            }
162            if visited.contains(node) {
163                return true;
164            }
165
166            temp_marks.insert(node.to_string());
167
168            for (_, neighbor, _) in graph.outgoing_edges(node) {
169                if !visit(graph, &neighbor, visited, temp_marks, result) {
170                    return false;
171                }
172            }
173
174            temp_marks.remove(node);
175            visited.insert(node.to_string());
176            result.push(node.to_string());
177            true
178        }
179
180        for node in &nodes {
181            if !visited.contains(node)
182                && !visit(graph, node, &mut visited, &mut temp_marks, &mut result)
183            {
184                return None; // Cycle detected
185            }
186        }
187
188        result.reverse();
189        Some(result)
190    }
191}
reddb_server/storage/engine/pathfinding/dfs_impl.rs

reddb_server/storage/engine/pathfinding/
dfs_impl.rs
