eta_graph/algorithms/
path_finding.rs

1use std::cmp::Ordering;
2use std::collections::{BinaryHeap};
3use eta_algorithms::data_structs::array::Array;
4use eta_algorithms::data_structs::stack::Stack;
5use crate::handles::types::{Edge, VHandle, Weight};
6use crate::handles::{vh, wgt};
7use crate::traits::EdgeStore;
8
9struct MinHeapPair {
10    pub vertex: VHandle,
11    pub f_score: Weight,
12}
13
14#[derive(Clone, Copy)]
15struct PathVertex {
16    pub from: VHandle,
17    pub f_score: Weight,
18}
19
20impl MinHeapPair {
21    pub fn new(vertex: VHandle, f_score: Weight) -> Self {
22        MinHeapPair {
23            vertex,
24            f_score,
25        }
26    }
27}
28
29impl Eq for MinHeapPair {}
30
31impl PartialEq<Self> for MinHeapPair {
32    fn eq(&self, other: &Self) -> bool {
33        self.f_score == other.f_score
34    }
35}
36
37impl PartialOrd<Self> for MinHeapPair {
38    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
39        Some(self.cmp(other))
40    }
41}
42
43impl Ord for MinHeapPair {
44    fn cmp(&self, other: &Self) -> Ordering {
45        other.f_score.cmp(&self.f_score)
46    }
47}
48
49fn reconstruct_path(paths: &mut Array<PathVertex>, start: VHandle, goal: VHandle) -> Stack<VHandle> {
50    let mut path = Stack::new(paths.capacity());
51    let mut current = goal;
52    path.push(current);
53    while current != start {
54        let prev = paths[current as usize].from;
55        path.push(prev);
56        current = prev;
57    }
58    path
59}
60
61/// A* algorithm
62/// f_scores are sums of (distances + heuristic) from start to current vertex
63/// h_scores are heuristic values from start to current vertex
64/// g_scores sums of distances from start to current vertex. Not used purely in this implementation, but summed up to f_scores
65///
66// TODO Parallelization potential. Split the graph into multiple subgraphs, and run A* on each subgraph in parallel.
67// Put together the resulting paths
68pub fn a_star<Edges, Heuristic>(edge_storage: &mut Edges, start: VHandle, goal: VHandle, vertices_count: usize, h_score: Heuristic) -> Option<Stack<VHandle>>
69where
70    Edges: EdgeStore,
71    Heuristic: Fn(VHandle, Edge) -> Weight,
72{
73    let mut explore_list = BinaryHeap::<MinHeapPair>::with_capacity(vertices_count);
74
75    let mut f_scores = Array::<PathVertex>::new_with_default(vertices_count, PathVertex{from: 0, f_score: Weight::MAX});
76    explore_list.push(MinHeapPair {vertex: start, f_score: 0});
77
78    while let Some(current_vertex) = explore_list.pop() {
79        if current_vertex.vertex == goal{
80            return Some(reconstruct_path(&mut f_scores, start, goal))
81        }
82
83        let neighbors = edge_storage.edges_as_slice(current_vertex.vertex);
84        for neighbor in neighbors {
85            let neighbor_f_score = wgt(*neighbor) + current_vertex.f_score + h_score(current_vertex.vertex, *neighbor);
86            if f_scores[vh(*neighbor) as usize].f_score < neighbor_f_score {
87                continue;
88            }
89            explore_list.push(MinHeapPair::new(vh(*neighbor), neighbor_f_score));
90            f_scores[vh(*neighbor) as usize] = PathVertex{from: current_vertex.vertex, f_score: neighbor_f_score };
91        }
92    }
93    None
94}
95
96#[inline(always)]
97pub fn dijkstra<Edges>(edge_storage: &mut Edges, start: VHandle, goal: VHandle, vertices_count: usize) -> Option<Stack<VHandle>>
98where
99    Edges: EdgeStore
100{
101    a_star(edge_storage, start, goal, vertices_count, |_, _| {
102        0
103    })
104}
eta_graph/algorithms/path_finding.rs

eta_graph/algorithms/
path_finding.rs
