1use glam::Vec3;
8use std::cmp::Ordering;
9use std::collections::{BTreeMap, BinaryHeap, HashMap, HashSet, VecDeque};
10
11pub type GraphProperties = BTreeMap<String, serde_json::Value>;
12
13#[derive(Debug, Clone, Copy, PartialEq, Eq)]
14pub struct TemporalWindow {
15 pub start: u64,
16 pub end: u64,
17}
18
19impl TemporalWindow {
20 pub fn overlaps(self, begin_ts: u64, end_ts: u64) -> bool {
21 begin_ts < self.end && (end_ts == 0 || end_ts > self.start)
22 }
23}
24
25#[derive(Debug, Clone, Copy, PartialEq)]
26pub enum SpatialRegion {
27 Sphere { center: Vec3, radius: f32 },
28 Aabb { min: Vec3, max: Vec3 },
29}
30
31impl SpatialRegion {
32 pub fn contains(self, point: Vec3) -> bool {
33 match self {
34 SpatialRegion::Sphere { center, radius } => point.distance(center) <= radius,
35 SpatialRegion::Aabb { min, max } => {
36 point.x >= min.x
37 && point.x <= max.x
38 && point.y >= min.y
39 && point.y <= max.y
40 && point.z >= min.z
41 && point.z <= max.z
42 }
43 }
44 }
45}
46
47#[derive(Debug, Clone, Copy, PartialEq)]
48pub struct TraversalContext4D {
49 pub time_window: Option<TemporalWindow>,
50 pub spatial_region: Option<SpatialRegion>,
51 pub graph_weight: f32,
52 pub spatial_weight: f32,
53 pub temporal_weight: f32,
54}
55
56impl Default for TraversalContext4D {
57 fn default() -> Self {
58 Self {
59 time_window: None,
60 spatial_region: None,
61 graph_weight: 1.0,
62 spatial_weight: 0.0,
63 temporal_weight: 0.0,
64 }
65 }
66}
67
68#[derive(Debug, Clone, Copy, PartialEq)]
69pub struct TemporalEdge {
70 pub dst: u64,
71 pub weight: f32,
72 pub begin_ts: u64,
73 pub end_ts: u64,
74}
75
76#[derive(Debug, Clone, PartialEq)]
77pub struct GraphNode4D {
78 pub id: u64,
79 pub x: f32,
80 pub y: f32,
81 pub z: f32,
82 pub begin_ts: u64,
83 pub end_ts: u64,
84 pub properties: GraphProperties,
85 pub successors: Vec<TemporalEdge>,
86}
87
88impl GraphNode4D {
89 pub fn position(&self) -> Vec3 {
90 Vec3::new(self.x, self.y, self.z)
91 }
92}
93
94#[derive(Debug, Clone, PartialEq)]
95pub struct GraphPath4D {
96 pub node_ids: Vec<u64>,
97 pub total_cost: f32,
98 pub heuristic_cost: f32,
99 pub actual_cost: f32,
100}
101
102#[derive(Debug, Clone, PartialEq, Eq)]
103pub struct TemporalJourney4D {
104 pub node_ids: Vec<u64>,
105 pub departure_time: u64,
106 pub arrival_time: u64,
107 pub duration: u64,
108}
109
110#[derive(Debug, Clone, PartialEq)]
111pub struct TemporalArrival4D {
112 pub node_id: u64,
113 pub arrival_time: u64,
114 pub cost: f32,
115 pub path: Vec<u64>,
116}
117
118#[derive(Debug, Clone, PartialEq)]
119pub struct TemporalDijkstraResult4D {
120 pub start_node: u64,
121 pub departure_time: u64,
122 pub reachable: Vec<TemporalArrival4D>,
123 pub unreachable: Vec<u64>,
124}
125
126#[derive(Debug, Clone, Copy, PartialEq)]
127struct QueueNode4D {
128 node_id: u64,
129 f_score: f32,
130 g_score: f32,
131}
132
133impl Eq for QueueNode4D {}
134
135impl Ord for QueueNode4D {
136 fn cmp(&self, other: &Self) -> Ordering {
137 other
138 .f_score
139 .partial_cmp(&self.f_score)
140 .unwrap_or(Ordering::Equal)
141 }
142}
143
144impl PartialOrd for QueueNode4D {
145 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
146 Some(self.cmp(other))
147 }
148}
149
150fn node_is_valid(node: &GraphNode4D, ctx: &TraversalContext4D) -> bool {
151 if let Some(window) = ctx.time_window {
152 if !window.overlaps(node.begin_ts, node.end_ts) {
153 return false;
154 }
155 }
156
157 if let Some(region) = ctx.spatial_region {
158 if !region.contains(node.position()) {
159 return false;
160 }
161 }
162
163 true
164}
165
166fn edge_is_valid(edge: TemporalEdge, ctx: &TraversalContext4D) -> bool {
167 ctx.time_window
168 .map(|window| window.overlaps(edge.begin_ts, edge.end_ts))
169 .unwrap_or(true)
170}
171
172fn instant_in_validity(ts: u64, begin_ts: u64, end_ts: u64) -> bool {
173 ts >= begin_ts && (end_ts == 0 || ts <= end_ts)
174}
175
176fn traversal_duration(edge: TemporalEdge) -> Option<u64> {
177 if !edge.weight.is_finite() || edge.weight < 0.0 {
178 return None;
179 }
180 Some(edge.weight.ceil() as u64)
181}
182
183fn edge_departure_and_arrival(edge: TemporalEdge, current_time: u64) -> Option<(u64, u64)> {
184 let departure = current_time.max(edge.begin_ts);
185 if edge.end_ts != 0 && departure > edge.end_ts {
186 return None;
187 }
188
189 let arrival = departure.checked_add(traversal_duration(edge)?)?;
190 if edge.end_ts != 0 && arrival > edge.end_ts {
191 return None;
192 }
193
194 Some((departure, arrival))
195}
196
197fn temporal_node_is_usable(
198 node: &GraphNode4D,
199 arrival_time: u64,
200 region: Option<SpatialRegion>,
201) -> bool {
202 instant_in_validity(arrival_time, node.begin_ts, node.end_ts)
203 && region
204 .map(|spatial_region| spatial_region.contains(node.position()))
205 .unwrap_or(true)
206}
207
208fn temporal_delay(edge: TemporalEdge, ctx: &TraversalContext4D) -> f32 {
209 match ctx.time_window {
210 Some(window) if edge.begin_ts > window.start => (edge.begin_ts - window.start) as f32,
211 _ => 0.0,
212 }
213}
214
215fn edge_cost(
216 current: &GraphNode4D,
217 next: &GraphNode4D,
218 edge: TemporalEdge,
219 ctx: &TraversalContext4D,
220) -> f32 {
221 let graph = ctx.graph_weight * edge.weight.max(0.0);
222 let spatial = ctx.spatial_weight * current.position().distance(next.position());
223 let temporal = ctx.temporal_weight * temporal_delay(edge, ctx);
224 graph + spatial + temporal
225}
226
227fn heuristic(current: &GraphNode4D, goal: &GraphNode4D, ctx: &TraversalContext4D) -> f32 {
228 ctx.spatial_weight * current.position().distance(goal.position())
229}
230
231pub fn reachable_4d(nodes: &[GraphNode4D], start_id: u64, ctx: &TraversalContext4D) -> Vec<u64> {
232 let node_map: HashMap<u64, &GraphNode4D> = nodes.iter().map(|n| (n.id, n)).collect();
233 let Some(start) = node_map.get(&start_id) else {
234 return Vec::new();
235 };
236 if !node_is_valid(start, ctx) {
237 return Vec::new();
238 }
239
240 let mut visited = HashSet::new();
241 let mut queue = VecDeque::from([start_id]);
242 let mut result = Vec::new();
243
244 while let Some(current_id) = queue.pop_front() {
245 if !visited.insert(current_id) {
246 continue;
247 }
248 let Some(current) = node_map.get(¤t_id) else {
249 continue;
250 };
251 if !node_is_valid(current, ctx) {
252 continue;
253 }
254
255 result.push(current_id);
256
257 for edge in ¤t.successors {
258 if !edge_is_valid(*edge, ctx) || visited.contains(&edge.dst) {
259 continue;
260 }
261 if let Some(next) = node_map.get(&edge.dst) {
262 if node_is_valid(next, ctx) {
263 queue.push_back(edge.dst);
264 }
265 }
266 }
267 }
268
269 result
270}
271
272pub fn astar_find_path_4d(
273 nodes: &[GraphNode4D],
274 start_id: u64,
275 goal_id: u64,
276 ctx: &TraversalContext4D,
277) -> Option<GraphPath4D> {
278 let node_map: HashMap<u64, &GraphNode4D> = nodes.iter().map(|n| (n.id, n)).collect();
279 let start = *node_map.get(&start_id)?;
280 let goal = *node_map.get(&goal_id)?;
281
282 if !node_is_valid(start, ctx) || !node_is_valid(goal, ctx) {
283 return None;
284 }
285
286 let initial_h = heuristic(start, goal, ctx);
287 let mut open_set = BinaryHeap::from([QueueNode4D {
288 node_id: start_id,
289 f_score: initial_h,
290 g_score: 0.0,
291 }]);
292 let mut closed = HashSet::new();
293 let mut g_score = HashMap::from([(start_id, 0.0)]);
294 let mut came_from = HashMap::new();
295
296 while let Some(current) = open_set.pop() {
297 if !closed.insert(current.node_id) {
298 continue;
299 }
300
301 if current.node_id == goal_id {
302 let mut path = vec![goal_id];
303 let mut cursor = goal_id;
304 while let Some(prev) = came_from.get(&cursor).copied() {
305 path.push(prev);
306 cursor = prev;
307 }
308 path.reverse();
309 return Some(GraphPath4D {
310 node_ids: path,
311 total_cost: current.f_score,
312 heuristic_cost: initial_h,
313 actual_cost: current.g_score,
314 });
315 }
316
317 let current_node = *node_map.get(¤t.node_id)?;
318 for edge in ¤t_node.successors {
319 if !edge_is_valid(*edge, ctx) || closed.contains(&edge.dst) {
320 continue;
321 }
322 let Some(next) = node_map.get(&edge.dst).copied() else {
323 continue;
324 };
325 if !node_is_valid(next, ctx) {
326 continue;
327 }
328
329 let tentative_g = current.g_score + edge_cost(current_node, next, *edge, ctx);
330 let existing_g = g_score.get(&edge.dst).copied().unwrap_or(f32::INFINITY);
331 if tentative_g < existing_g {
332 came_from.insert(edge.dst, current.node_id);
333 g_score.insert(edge.dst, tentative_g);
334 open_set.push(QueueNode4D {
335 node_id: edge.dst,
336 f_score: tentative_g + heuristic(next, goal, ctx),
337 g_score: tentative_g,
338 });
339 }
340 }
341 }
342
343 None
344}
345
346pub fn strongly_connected_components_4d(
347 nodes: &[GraphNode4D],
348 ctx: &TraversalContext4D,
349) -> Vec<Vec<u64>> {
350 struct Tarjan<'a> {
351 nodes: HashMap<u64, &'a GraphNode4D>,
352 ctx: &'a TraversalContext4D,
353 index: usize,
354 stack: Vec<u64>,
355 on_stack: HashSet<u64>,
356 indices: HashMap<u64, usize>,
357 lowlinks: HashMap<u64, usize>,
358 components: Vec<Vec<u64>>,
359 }
360
361 impl<'a> Tarjan<'a> {
362 fn strong_connect(&mut self, node_id: u64) {
363 self.indices.insert(node_id, self.index);
364 self.lowlinks.insert(node_id, self.index);
365 self.index += 1;
366 self.stack.push(node_id);
367 self.on_stack.insert(node_id);
368
369 let Some(node) = self.nodes.get(&node_id) else {
370 return;
371 };
372 for edge in &node.successors {
373 if !edge_is_valid(*edge, self.ctx) {
374 continue;
375 }
376 let Some(next) = self.nodes.get(&edge.dst).copied() else {
377 continue;
378 };
379 if !node_is_valid(next, self.ctx) {
380 continue;
381 }
382
383 if !self.indices.contains_key(&edge.dst) {
384 self.strong_connect(edge.dst);
385 let low = self.lowlinks[&node_id].min(self.lowlinks[&edge.dst]);
386 self.lowlinks.insert(node_id, low);
387 } else if self.on_stack.contains(&edge.dst) {
388 let low = self.lowlinks[&node_id].min(self.indices[&edge.dst]);
389 self.lowlinks.insert(node_id, low);
390 }
391 }
392
393 if self.indices[&node_id] == self.lowlinks[&node_id] {
394 let mut component = Vec::new();
395 while let Some(member) = self.stack.pop() {
396 self.on_stack.remove(&member);
397 component.push(member);
398 if member == node_id {
399 break;
400 }
401 }
402 component.sort_unstable();
403 self.components.push(component);
404 }
405 }
406 }
407
408 let node_map: HashMap<u64, &GraphNode4D> = nodes
409 .iter()
410 .filter(|node| node_is_valid(node, ctx))
411 .map(|node| (node.id, node))
412 .collect();
413 let mut ids: Vec<u64> = node_map.keys().copied().collect();
414 ids.sort_unstable();
415
416 let mut tarjan = Tarjan {
417 nodes: node_map,
418 ctx,
419 index: 0,
420 stack: Vec::new(),
421 on_stack: HashSet::new(),
422 indices: HashMap::new(),
423 lowlinks: HashMap::new(),
424 components: Vec::new(),
425 };
426
427 for id in ids {
428 if !tarjan.indices.contains_key(&id) {
429 tarjan.strong_connect(id);
430 }
431 }
432
433 tarjan.components.sort_by_key(|component| component[0]);
434 tarjan.components
435}
436
437pub fn earliest_arrival_path_4d(
438 nodes: &[GraphNode4D],
439 start_id: u64,
440 goal_id: u64,
441 departure_time: u64,
442 spatial_region: Option<SpatialRegion>,
443) -> Option<TemporalJourney4D> {
444 let node_map: HashMap<u64, &GraphNode4D> = nodes.iter().map(|node| (node.id, node)).collect();
445 let start = *node_map.get(&start_id)?;
446 if !temporal_node_is_usable(start, departure_time, spatial_region) {
447 return None;
448 }
449
450 let mut best_arrival = HashMap::from([(start_id, departure_time)]);
451 let mut came_from = HashMap::new();
452 let mut queue = BinaryHeap::from([TemporalQueueNode {
453 node_id: start_id,
454 arrival_time: departure_time,
455 }]);
456
457 while let Some(current) = queue.pop() {
458 if current.arrival_time > best_arrival[¤t.node_id] {
459 continue;
460 }
461 if current.node_id == goal_id {
462 return Some(reconstruct_temporal_journey(
463 &came_from,
464 start_id,
465 goal_id,
466 departure_time,
467 current.arrival_time,
468 ));
469 }
470
471 let current_node = *node_map.get(¤t.node_id)?;
472 for edge in ¤t_node.successors {
473 let Some(next) = node_map.get(&edge.dst).copied() else {
474 continue;
475 };
476 let Some((_, arrival_time)) = edge_departure_and_arrival(*edge, current.arrival_time)
477 else {
478 continue;
479 };
480 if !temporal_node_is_usable(next, arrival_time, spatial_region) {
481 continue;
482 }
483
484 if arrival_time < best_arrival.get(&edge.dst).copied().unwrap_or(u64::MAX) {
485 best_arrival.insert(edge.dst, arrival_time);
486 came_from.insert(edge.dst, current.node_id);
487 queue.push(TemporalQueueNode {
488 node_id: edge.dst,
489 arrival_time,
490 });
491 }
492 }
493 }
494
495 None
496}
497
498pub fn fastest_temporal_path_4d(
499 nodes: &[GraphNode4D],
500 start_id: u64,
501 goal_id: u64,
502 earliest_departure: u64,
503 latest_departure: u64,
504 spatial_region: Option<SpatialRegion>,
505) -> Option<TemporalJourney4D> {
506 const MAX_WINDOW: u64 = 100_000;
507 if earliest_departure > latest_departure {
508 return None;
509 }
510 if latest_departure.saturating_sub(earliest_departure) > MAX_WINDOW {
511 return None;
512 }
513
514 let mut best: Option<TemporalJourney4D> = None;
515
516 for departure_time in earliest_departure..=latest_departure {
517 let Some(journey) =
518 earliest_arrival_path_4d(nodes, start_id, goal_id, departure_time, spatial_region)
519 else {
520 continue;
521 };
522
523 let should_replace = best
524 .as_ref()
525 .map(|current| {
526 journey.duration < current.duration
527 || (journey.duration == current.duration
528 && journey.arrival_time < current.arrival_time)
529 })
530 .unwrap_or(true);
531 if should_replace {
532 best = Some(journey);
533 }
534 }
535
536 best
537}
538
539pub fn articulation_points_4d(nodes: &[GraphNode4D], ctx: &TraversalContext4D) -> Vec<u64> {
540 let adjacency = active_undirected_adjacency(nodes, ctx);
541 let mut ids: Vec<u64> = adjacency.keys().copied().collect();
542 ids.sort_unstable();
543
544 let mut finder = LowLinkFinder {
545 adjacency: &adjacency,
546 time: 0,
547 visited: HashSet::new(),
548 discovery: HashMap::new(),
549 low: HashMap::new(),
550 parent: HashMap::new(),
551 articulation_points: HashSet::new(),
552 bridges: Vec::new(),
553 };
554
555 for id in ids {
556 if !finder.visited.contains(&id) {
557 finder.visit(id);
558 }
559 }
560
561 let mut points: Vec<u64> = finder.articulation_points.into_iter().collect();
562 points.sort_unstable();
563 points
564}
565
566pub fn bridges_4d(nodes: &[GraphNode4D], ctx: &TraversalContext4D) -> Vec<(u64, u64)> {
567 let adjacency = active_undirected_adjacency(nodes, ctx);
568 let mut ids: Vec<u64> = adjacency.keys().copied().collect();
569 ids.sort_unstable();
570
571 let mut finder = LowLinkFinder {
572 adjacency: &adjacency,
573 time: 0,
574 visited: HashSet::new(),
575 discovery: HashMap::new(),
576 low: HashMap::new(),
577 parent: HashMap::new(),
578 articulation_points: HashSet::new(),
579 bridges: Vec::new(),
580 };
581
582 for id in ids {
583 if !finder.visited.contains(&id) {
584 finder.visit(id);
585 }
586 }
587
588 finder.bridges.sort_unstable();
589 finder.bridges
590}
591
592pub fn time_dependent_dijkstra_4d(
593 nodes: &[GraphNode4D],
594 start_id: u64,
595 departure_time: u64,
596 spatial_region: Option<SpatialRegion>,
597) -> Option<TemporalDijkstraResult4D> {
598 let node_map: HashMap<u64, &GraphNode4D> = nodes
599 .iter()
600 .filter(|node| {
601 spatial_region
602 .map(|region| region.contains(node.position()))
603 .unwrap_or(true)
604 })
605 .map(|node| (node.id, node))
606 .collect();
607 let start = *node_map.get(&start_id)?;
608 if !instant_in_validity(departure_time, start.begin_ts, start.end_ts) {
609 return None;
610 }
611
612 let mut best_arrival = HashMap::from([(start_id, departure_time)]);
613 let mut came_from = HashMap::new();
614 let mut queue = BinaryHeap::from([TemporalQueueNode {
615 node_id: start_id,
616 arrival_time: departure_time,
617 }]);
618
619 while let Some(current) = queue.pop() {
620 if current.arrival_time > best_arrival[¤t.node_id] {
621 continue;
622 }
623
624 let current_node = *node_map.get(¤t.node_id)?;
625 for edge in ¤t_node.successors {
626 let Some(next) = node_map.get(&edge.dst).copied() else {
627 continue;
628 };
629 let Some((_, arrival_time)) = edge_departure_and_arrival(*edge, current.arrival_time)
630 else {
631 continue;
632 };
633 if !instant_in_validity(arrival_time, next.begin_ts, next.end_ts) {
634 continue;
635 }
636
637 if arrival_time < best_arrival.get(&edge.dst).copied().unwrap_or(u64::MAX) {
638 best_arrival.insert(edge.dst, arrival_time);
639 came_from.insert(edge.dst, current.node_id);
640 queue.push(TemporalQueueNode {
641 node_id: edge.dst,
642 arrival_time,
643 });
644 }
645 }
646 }
647
648 let mut reachable: Vec<TemporalArrival4D> = best_arrival
649 .iter()
650 .map(|(node_id, arrival_time)| TemporalArrival4D {
651 node_id: *node_id,
652 arrival_time: *arrival_time,
653 cost: arrival_time.saturating_sub(departure_time) as f32,
654 path: reconstruct_node_path(&came_from, start_id, *node_id),
655 })
656 .collect();
657 reachable.sort_by_key(|arrival| (arrival.arrival_time, arrival.node_id));
658
659 let mut unreachable: Vec<u64> = node_map
660 .keys()
661 .copied()
662 .filter(|id| !best_arrival.contains_key(id))
663 .collect();
664 unreachable.sort_unstable();
665
666 Some(TemporalDijkstraResult4D {
667 start_node: start_id,
668 departure_time,
669 reachable,
670 unreachable,
671 })
672}
673
674fn active_undirected_adjacency(
675 nodes: &[GraphNode4D],
676 ctx: &TraversalContext4D,
677) -> HashMap<u64, Vec<u64>> {
678 let node_map: HashMap<u64, &GraphNode4D> = nodes
679 .iter()
680 .filter(|node| node_is_valid(node, ctx))
681 .map(|node| (node.id, node))
682 .collect();
683 let mut adjacency: HashMap<u64, Vec<u64>> = node_map
684 .keys()
685 .copied()
686 .map(|id| (id, Vec::new()))
687 .collect();
688
689 for node in node_map.values() {
690 for edge in &node.successors {
691 if !edge_is_valid(*edge, ctx) || !node_map.contains_key(&edge.dst) {
692 continue;
693 }
694 add_undirected_edge(&mut adjacency, node.id, edge.dst);
695 }
696 }
697
698 for neighbors in adjacency.values_mut() {
699 neighbors.sort_unstable();
700 neighbors.dedup();
701 }
702
703 adjacency
704}
705
706fn add_undirected_edge(adjacency: &mut HashMap<u64, Vec<u64>>, a: u64, b: u64) {
707 if a == b {
708 return;
709 }
710 adjacency.entry(a).or_default().push(b);
711 adjacency.entry(b).or_default().push(a);
712}
713
714struct LowLinkFinder<'a> {
715 adjacency: &'a HashMap<u64, Vec<u64>>,
716 time: usize,
717 visited: HashSet<u64>,
718 discovery: HashMap<u64, usize>,
719 low: HashMap<u64, usize>,
720 parent: HashMap<u64, u64>,
721 articulation_points: HashSet<u64>,
722 bridges: Vec<(u64, u64)>,
723}
724
725impl LowLinkFinder<'_> {
726 fn visit(&mut self, node_id: u64) {
727 self.visited.insert(node_id);
728 self.discovery.insert(node_id, self.time);
729 self.low.insert(node_id, self.time);
730 self.time += 1;
731
732 let mut child_count = 0;
733 let neighbors = self.adjacency.get(&node_id).cloned().unwrap_or_default();
734 for next_id in neighbors {
735 if !self.visited.contains(&next_id) {
736 child_count += 1;
737 self.parent.insert(next_id, node_id);
738 self.visit(next_id);
739
740 let next_low = self.low[&next_id];
741 let node_low = self.low[&node_id].min(next_low);
742 self.low.insert(node_id, node_low);
743
744 let is_root = !self.parent.contains_key(&node_id);
745 if is_root && child_count > 1 {
746 self.articulation_points.insert(node_id);
747 }
748 if !is_root && next_low >= self.discovery[&node_id] {
749 self.articulation_points.insert(node_id);
750 }
751 if next_low > self.discovery[&node_id] {
752 self.bridges
753 .push((node_id.min(next_id), node_id.max(next_id)));
754 }
755 } else if self.parent.get(&node_id).copied() != Some(next_id) {
756 let node_low = self.low[&node_id].min(self.discovery[&next_id]);
757 self.low.insert(node_id, node_low);
758 }
759 }
760 }
761}
762
763#[derive(Debug, Clone, Copy, PartialEq, Eq)]
764struct TemporalQueueNode {
765 node_id: u64,
766 arrival_time: u64,
767}
768
769impl Ord for TemporalQueueNode {
770 fn cmp(&self, other: &Self) -> Ordering {
771 other
772 .arrival_time
773 .cmp(&self.arrival_time)
774 .then_with(|| other.node_id.cmp(&self.node_id))
775 }
776}
777
778impl PartialOrd for TemporalQueueNode {
779 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
780 Some(self.cmp(other))
781 }
782}
783
784fn reconstruct_temporal_journey(
785 came_from: &HashMap<u64, u64>,
786 start_id: u64,
787 goal_id: u64,
788 departure_time: u64,
789 arrival_time: u64,
790) -> TemporalJourney4D {
791 let mut node_ids = vec![goal_id];
792 let mut cursor = goal_id;
793 while cursor != start_id {
794 let Some(prev) = came_from.get(&cursor).copied() else {
795 break;
796 };
797 node_ids.push(prev);
798 cursor = prev;
799 }
800 node_ids.reverse();
801
802 TemporalJourney4D {
803 node_ids,
804 departure_time,
805 arrival_time,
806 duration: arrival_time.saturating_sub(departure_time),
807 }
808}
809
810fn reconstruct_node_path(came_from: &HashMap<u64, u64>, start_id: u64, target_id: u64) -> Vec<u64> {
811 let mut node_ids = vec![target_id];
812 let mut cursor = target_id;
813 while cursor != start_id {
814 let Some(prev) = came_from.get(&cursor).copied() else {
815 break;
816 };
817 node_ids.push(prev);
818 cursor = prev;
819 }
820 node_ids.reverse();
821 node_ids
822}