Function expand_directed

nodedb-vector/src/navix/traversal.rs:338–396

(
    index: &HnswIndex,
    query: &[f32],
    neighbors_1hop: &[u32],
    allowed: &RoaringBitmap,
    ef: usize,
    metric: nodedb_types::vector_distance::DistanceMetric,
    visited: &mut HashSet

/// then expand that neighbor's 2-hop neighbors into the heaps.
#[allow(clippy::too_many_arguments)]
fn expand_directed(
    index: &HnswIndex,
    query: &[f32],
    neighbors_1hop: &[u32],
    allowed: &RoaringBitmap,
    ef: usize,
    metric: nodedb_types::vector_distance::DistanceMetric,
    visited: &mut HashSet<u32>,
    candidates: &mut BinaryHeap<Reverse<Candidate>>,
    results: &mut BinaryHeap<Candidate>,
) {
    // Score 1-hop; track the best allowed neighbor.
    let mut best_allowed: Option<(u32, f32)> = None;

    for &nb in neighbors_1hop {
        let already_visited = !visited.insert(nb);
        if already_visited {
            continue;
        }
        let d = dist(index, query, nb, metric);
        let nb_cand = Candidate { dist: d, id: nb };

        let worst_dist = results.peek().map_or(f32::INFINITY, |w| w.dist);
        if d < worst_dist || results.len() < ef {
            candidates.push(Reverse(nb_cand));
        }

        if !index.is_deleted(nb) && allowed.contains(nb) {
            if best_allowed.is_none_or(|(_, bd)| d < bd) {
                best_allowed = Some((nb, d));
            }
            results.push(nb_cand);
            if results.len() > ef {
                results.pop();
            }
        }
    }

    // Expand 2-hop of the single best allowed neighbor.
    if let Some((best_id, _)) = best_allowed {
        for &nb2 in index.neighbors_at(best_id, 0) {
            if !visited.insert(nb2) {
                continue;
            }
            let d = dist(index, query, nb2, metric);
            let nb2_cand = Candidate { dist: d, id: nb2 };
            let worst_dist = results.peek().map_or(f32::INFINITY, |w| w.dist);
            if d < worst_dist || results.len() < ef {
                candidates.push(Reverse(nb2_cand));
            }
            if !index.is_deleted(nb2) && allowed.contains(nb2) {
                results.push(nb2_cand);
                if results.len() > ef {
                    results.pop();
                }
            }
        }
    }