Method shortest_path

nodedb-graph/src/traversal.rs:180–260

Shortest path via bidirectional BFS. `max_visited` caps the combined forward+backward visited set to prevent supernode fan-out explosion. Pass [`DEFAULT_MAX_VISITED`] for the standard limit. `frontier_bitmap`: when `Some`, only nodes whose surrogate is present in the bitmap are eligible for expansion. Start and end nodes are not gated.

(
        &self,
        src: &str,
        dst: &str,
        label_filter: Option<&str>,
        max_depth: usize,
        max_visited: usize,
        frontier_bitmap: Option<&nodedb_types::Surrogat

    /// `frontier_bitmap`: when `Some`, only nodes whose surrogate is present in the
    /// bitmap are eligible for expansion. Start and end nodes are not gated.
    pub fn shortest_path(
        &self,
        src: &str,
        dst: &str,
        label_filter: Option<&str>,
        max_depth: usize,
        max_visited: usize,
        frontier_bitmap: Option<&nodedb_types::SurrogateBitmap>,
    ) -> Option<Vec<String>> {
        let src_id = *self.node_to_id.get(src)?;
        let dst_id = *self.node_to_id.get(dst)?;
        if src_id == dst_id {
            return Some(vec![src.to_string()]);
        }

        let label_id = label_filter.and_then(|l| self.label_id(l));
        let mut fwd_parent: HashMap<u32, u32> = HashMap::new();
        let mut bwd_parent: HashMap<u32, u32> = HashMap::new();
        fwd_parent.insert(src_id, src_id);
        bwd_parent.insert(dst_id, dst_id);

        let mut fwd_frontier: Vec<u32> = vec![src_id];
        let mut bwd_frontier: Vec<u32> = vec![dst_id];

        for _depth in 0..max_depth {
            if fwd_parent.len() + bwd_parent.len() >= max_visited {
                break;
            }

            let mut next_fwd = Vec::new();
            for &node in &fwd_frontier {
                self.record_access(node);
                for (lid, neighbor) in self.dense_iter_out(node) {
                    if label_id.is_none_or(|f| f == lid)
                        && frontier_bitmap.is_none_or(|bm| {
                            bm.contains(nodedb_types::Surrogate::new(
                                self.node_surrogate_raw(neighbor),
                            ))
                        })
                    {
                        if let Entry::Vacant(e) = fwd_parent.entry(neighbor) {
                            e.insert(node);
                            next_fwd.push(neighbor);
                        }
                        if bwd_parent.contains_key(&neighbor) {
                            return Some(self.reconstruct_path(neighbor, &fwd_parent, &bwd_parent));
                        }
                    }
                }
            }
            fwd_frontier = next_fwd;

            let mut next_bwd = Vec::new();
            for &node in &bwd_frontier {
                self.record_access(node);
                for (lid, neighbor) in self.dense_iter_in(node) {
                    if label_id.is_none_or(|f| f == lid)
                        && frontier_bitmap.is_none_or(|bm| {