1use crate::DbError;
2use crate::StorageData;
3use crate::collections::bit_set::BitSet;
4use crate::graph::GraphData;
5use crate::graph::GraphImpl;
6use crate::graph::GraphIndex;
7use crate::storage::Storage;
8use std::cmp::Ordering;
9
10pub trait PathSearchHandler {
11 fn process(&self, index: GraphIndex, distance: u64) -> Result<(u64, bool), DbError>;
12}
13
14#[derive(Clone)]
15struct Path {
16 elements: Vec<(GraphIndex, bool)>,
17 cost: u64,
18}
19
20pub struct PathSearch<'a, D, Data, Handler>
21where
22 Data: GraphData<D>,
23 D: StorageData,
24 Handler: PathSearchHandler,
25{
26 current_path: Path,
27 destination: GraphIndex,
28 graph: &'a GraphImpl<D, Data>,
29 storage: &'a Storage<D>,
30 handler: Handler,
31 paths: Vec<Path>,
32 result: Vec<(GraphIndex, bool)>,
33 visited: BitSet,
34}
35
36impl<'a, D, Data, Handler> PathSearch<'a, D, Data, Handler>
37where
38 Data: GraphData<D>,
39 D: StorageData,
40 Handler: PathSearchHandler,
41{
42 pub fn new(
43 graph: &'a GraphImpl<D, Data>,
44 storage: &'a Storage<D>,
45 from: GraphIndex,
46 to: GraphIndex,
47 handler: Handler,
48 ) -> Self {
49 let add = handler.process(from, 0).unwrap_or_default();
50
51 Self {
52 current_path: Path {
53 elements: vec![],
54 cost: 0,
55 },
56 destination: to,
57 graph,
58 storage,
59 handler,
60 paths: vec![Path {
61 elements: vec![(from, add.1)],
62 cost: 0,
63 }],
64 result: vec![],
65 visited: BitSet::new(),
66 }
67 }
68
69 pub fn search(&mut self) -> Result<Vec<GraphIndex>, DbError> {
70 while !self.is_finished() {
71 self.sort_paths();
72 self.process_last_path()?;
73 }
74
75 Ok(self.result.iter().filter(|e| e.1).map(|e| e.0).collect())
76 }
77
78 fn expand_edge(
79 &mut self,
80 mut path: Path,
81 index: GraphIndex,
82 node_index: GraphIndex,
83 ) -> Result<(), DbError> {
84 let cost = self
85 .handler
86 .process(index, self.current_path.elements.len() as u64 + 1)?;
87
88 if cost.0 != 0 && !self.visited.value(node_index.as_u64()) {
89 path.elements.push((index, cost.1));
90 path.cost += cost.0;
91 self.expand_node(path, node_index)?;
92 }
93
94 Ok(())
95 }
96
97 fn expand_node(&mut self, mut path: Path, index: GraphIndex) -> Result<(), DbError> {
98 let cost = self
99 .handler
100 .process(index, self.current_path.elements.len() as u64 + 1)?;
101
102 if cost.0 != 0 {
103 path.elements.push((index, cost.1));
104 path.cost += cost.0;
105 self.paths.push(path);
106 }
107
108 Ok(())
109 }
110
111 fn expand(&mut self, index: GraphIndex) -> Result<(), DbError> {
112 let node = self
113 .graph
114 .node(self.storage, index)
115 .expect("unexpected invalid node index");
116 for edge in node.edge_iter_from() {
117 self.expand_edge(self.current_path.clone(), edge.index(), edge.index_to())?;
118 }
119
120 Ok(())
121 }
122
123 fn is_finished(&self) -> bool {
124 self.paths.is_empty() || !self.result.is_empty()
125 }
126
127 fn process_path(&mut self) -> Result<(), DbError> {
128 let index = self
129 .current_path
130 .elements
131 .last()
132 .map_or(GraphIndex::default(), |index| index.0);
133 self.process_index(index)
134 }
135
136 fn process_index(&mut self, index: GraphIndex) -> Result<(), DbError> {
137 if !self.visited.value(index.as_u64()) {
138 if index.0 == self.destination.0 {
139 std::mem::swap(&mut self.result, &mut self.current_path.elements);
140 } else {
141 self.visited.set(index.as_u64());
142 self.expand(index)?;
143 }
144 }
145
146 Ok(())
147 }
148
149 fn process_last_path(&mut self) -> Result<(), DbError> {
150 self.current_path = self.paths.pop().unwrap_or(Path {
151 elements: vec![],
152 cost: 0,
153 });
154 self.process_path()
155 }
156
157 fn sort_paths(&mut self) {
158 self.paths.sort_by(|left, right| {
159 let ordering = left.cost.cmp(&right.cost);
160
161 if ordering == Ordering::Equal {
162 return left.elements.len().cmp(&right.elements.len()).reverse();
163 }
164
165 ordering.reverse()
166 });
167 }
168}
169
170#[cfg(test)]
171mod tests {
172 use super::*;
173 use crate::graph::DbGraph;
174 use crate::graph_search::GraphSearch;
175 use crate::storage::file_storage::FileStorage;
176 use crate::test_utilities::test_file::TestFile;
177
178 struct Handler {
179 pub processor: fn(GraphIndex, u64) -> (u64, bool),
180 }
181
182 impl Default for Handler {
183 fn default() -> Self {
184 Self {
185 processor: |_index: GraphIndex, _distance: u64| (1_u64, true),
186 }
187 }
188 }
189
190 impl PathSearchHandler for Handler {
191 fn process(&self, index: GraphIndex, distance: u64) -> Result<(u64, bool), DbError> {
192 Ok((self.processor)(index, distance))
193 }
194 }
195
196 #[test]
197 fn circular_path() {
198 let test_file = TestFile::new();
199 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
200 let mut graph = DbGraph::new(&mut storage).unwrap();
201 let node = graph.insert_node(&mut storage).unwrap();
202 let _edge = graph.insert_edge(&mut storage, node, node).unwrap();
203
204 let result = GraphSearch::from((&graph, &storage)).path(node, node, Handler::default());
205
206 assert_eq!(result, Ok(vec![]));
207 }
208
209 #[test]
210 fn empty_graph() {
211 let test_file = TestFile::new();
212 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
213 let graph = DbGraph::new(&mut storage).unwrap();
214
215 let result = GraphSearch::from((&graph, &storage)).path(
216 GraphIndex::default(),
217 GraphIndex::default(),
218 Handler::default(),
219 );
220
221 assert_eq!(result, Ok(vec![]));
222 }
223
224 #[test]
225 fn multi_edge_path() {
226 let test_file = TestFile::new();
227 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
228 let mut graph = DbGraph::new(&mut storage).unwrap();
229
230 let node1 = graph.insert_node(&mut storage).unwrap();
231 let node2 = graph.insert_node(&mut storage).unwrap();
232 let node3 = graph.insert_node(&mut storage).unwrap();
233
234 let edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
235 let _edge2 = graph.insert_edge(&mut storage, node1, node2).unwrap();
236
237 let edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();
238 let _edge4 = graph.insert_edge(&mut storage, node2, node3).unwrap();
239
240 let result = GraphSearch::from((&graph, &storage)).path(node1, node3, Handler::default());
241
242 assert_eq!(result, Ok(vec![node1, edge1, node2, edge3, node3]));
243 }
244
245 #[test]
246 fn origin_is_destination() {
247 let test_file = TestFile::new();
248 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
249 let mut graph = DbGraph::new(&mut storage).unwrap();
250 let node = graph.insert_node(&mut storage).unwrap();
251
252 let result = GraphSearch::from((&graph, &storage)).path(node, node, Handler::default());
253
254 assert_eq!(result, Ok(vec![]));
255 }
256
257 #[test]
258 fn short_circuit_path() {
259 let test_file = TestFile::new();
260 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
261 let mut graph = DbGraph::new(&mut storage).unwrap();
262
263 let node1 = graph.insert_node(&mut storage).unwrap();
264 let node2 = graph.insert_node(&mut storage).unwrap();
265 let node3 = graph.insert_node(&mut storage).unwrap();
266
267 let edge1 = graph.insert_edge(&mut storage, node1, node3).unwrap();
268 let _edge2 = graph.insert_edge(&mut storage, node1, node2).unwrap();
269 let _edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();
270
271 let result = GraphSearch::from((&graph, &storage)).path(node1, node3, Handler::default());
272
273 assert_eq!(result, Ok(vec![node1, edge1, node3]));
274 }
275
276 #[test]
277 fn single_path() {
278 let test_file = TestFile::new();
279 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
280 let mut graph = DbGraph::new(&mut storage).unwrap();
281
282 let node1 = graph.insert_node(&mut storage).unwrap();
283 let node2 = graph.insert_node(&mut storage).unwrap();
284 let node3 = graph.insert_node(&mut storage).unwrap();
285
286 let edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
287 let edge2 = graph.insert_edge(&mut storage, node2, node3).unwrap();
288
289 let result = GraphSearch::from((&graph, &storage)).path(node1, node3, Handler::default());
290
291 assert_eq!(result, Ok(vec![node1, edge1, node2, edge2, node3]));
292 }
293
294 #[test]
295 fn skip_short_circuit_path() {
296 let test_file = TestFile::new();
297 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
298 let mut graph = DbGraph::new(&mut storage).unwrap();
299
300 let node1 = graph.insert_node(&mut storage).unwrap();
301 let node2 = graph.insert_node(&mut storage).unwrap();
302 let node3 = graph.insert_node(&mut storage).unwrap();
303
304 let _edge1 = graph.insert_edge(&mut storage, node1, node3).unwrap();
305 let edge2 = graph.insert_edge(&mut storage, node1, node2).unwrap();
306 let edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();
307
308 let result = GraphSearch::from((&graph, &storage)).path(
309 node1,
310 node3,
311 Handler {
312 processor: |index: GraphIndex, _distance: u64| {
313 if index.0 == -4 {
314 return (0, true);
315 }
316
317 (1, true)
318 },
319 },
320 );
321
322 assert_eq!(result, Ok(vec![node1, edge2, node2, edge3, node3]));
323 }
324
325 #[test]
326 fn unconnected() {
327 let test_file = TestFile::new();
328 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
329 let mut graph = DbGraph::new(&mut storage).unwrap();
330
331 let node1 = graph.insert_node(&mut storage).unwrap();
332 let node2 = graph.insert_node(&mut storage).unwrap();
333 let node3 = graph.insert_node(&mut storage).unwrap();
334
335 let _edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
336
337 let result = GraphSearch::from((&graph, &storage)).path(node1, node3, Handler::default());
338
339 assert_eq!(result, Ok(vec![]));
340 }
341
342 #[test]
343 fn filtered_nodes() {
344 let test_file = TestFile::new();
345 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
346 let mut graph = DbGraph::new(&mut storage).unwrap();
347
348 let node1 = graph.insert_node(&mut storage).unwrap();
349 let node2 = graph.insert_node(&mut storage).unwrap();
350 let node3 = graph.insert_node(&mut storage).unwrap();
351
352 let _edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
353 let _edge2 = graph.insert_edge(&mut storage, node2, node2).unwrap();
354 let _edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();
355
356 let result = GraphSearch::from((&graph, &storage)).path(
357 node1,
358 node3,
359 Handler {
360 processor: |index: GraphIndex, _distance: u64| (1, index.is_node()),
361 },
362 );
363
364 assert_eq!(result, Ok(vec![node1, node2, node3]));
365 }
366
367 #[test]
368 fn filtered_edges() {
369 let test_file = TestFile::new();
370 let mut storage = Storage::<FileStorage>::new(test_file.file_name()).unwrap();
371 let mut graph = DbGraph::new(&mut storage).unwrap();
372
373 let node1 = graph.insert_node(&mut storage).unwrap();
374 let node2 = graph.insert_node(&mut storage).unwrap();
375 let node3 = graph.insert_node(&mut storage).unwrap();
376
377 let edge1 = graph.insert_edge(&mut storage, node1, node2).unwrap();
378 let _edge2 = graph.insert_edge(&mut storage, node2, node2).unwrap();
379 let edge3 = graph.insert_edge(&mut storage, node2, node3).unwrap();
380
381 let result = GraphSearch::from((&graph, &storage)).path(
382 node1,
383 node3,
384 Handler {
385 processor: |index: GraphIndex, _distance: u64| (1, index.is_edge()),
386 },
387 );
388
389 assert_eq!(result, Ok(vec![edge1, edge3]));
390 }
391}