Beam search over `layer` with the given `ef`, returning candidates sorted by ascending distance from `query_idx` (excluding deleted nodes).
(
&self,
query_idx: u32,
ep_idx: u32,
ef: usize,
layer: usize,
)
| 156 | /// Beam search over `layer` with the given `ef`, returning candidates |
| 157 | /// sorted by ascending distance from `query_idx` (excluding deleted nodes). |
| 158 | fn search_layer_build( |
| 159 | &self, |
| 160 | query_idx: u32, |
| 161 | ep_idx: u32, |
| 162 | ef: usize, |
| 163 | layer: usize, |
| 164 | ) -> Vec<Cand> { |
| 165 | let mut visited: HashSet<u32> = HashSet::new(); |
| 166 | visited.insert(ep_idx); |
| 167 | |
| 168 | let ep_dist = self.sym_dist(query_idx, ep_idx); |
| 169 | let ep_cand = Cand { |
| 170 | dist: ep_dist, |
| 171 | idx: ep_idx, |
| 172 | }; |
| 173 | |
| 174 | let mut candidates: BinaryHeap<Reverse<Cand>> = BinaryHeap::new(); |
| 175 | candidates.push(Reverse(ep_cand)); |
| 176 | |
| 177 | let mut results: BinaryHeap<Cand> = BinaryHeap::new(); |
| 178 | if !self.nodes[ep_idx as usize].deleted { |
| 179 | results.push(ep_cand); |
| 180 | } |
| 181 | |
| 182 | while let Some(Reverse(cur)) = candidates.pop() { |
| 183 | let worst = results.peek().map_or(f32::INFINITY, |w| w.dist); |
| 184 | if cur.dist > worst && results.len() >= ef { |
| 185 | break; |
| 186 | } |
| 187 | |
| 188 | for &nb in self.neighbors_at(cur.idx, layer) { |
| 189 | if !visited.insert(nb) { |
| 190 | continue; |
| 191 | } |
| 192 | let d = self.sym_dist(query_idx, nb); |
| 193 | let worst_now = results.peek().map_or(f32::INFINITY, |w| w.dist); |
| 194 | if d < worst_now || results.len() < ef { |
| 195 | candidates.push(Reverse(Cand { dist: d, idx: nb })); |
| 196 | } |
| 197 | if !self.nodes[nb as usize].deleted { |
| 198 | results.push(Cand { dist: d, idx: nb }); |
| 199 | if results.len() > ef { |
| 200 | results.pop(); |
| 201 | } |
| 202 | } |
| 203 | } |
| 204 | } |
| 205 | |
| 206 | let mut out: Vec<Cand> = results.into_vec(); |
| 207 | out.sort_unstable_by(|a, b| a.dist.total_cmp(&b.dist)); |
| 208 | out |
| 209 | } |
| 210 | |
| 211 | /// Prune the neighbor list of `nb_idx` at `layer` to `max_nb` entries, |
| 212 | /// removing the farthest neighbours (simple distance-based strategy). |