Method graph_shortest_path

nodedb-client/src/traits/core/trait_def.rs:336–398

Find the shortest path between two nodes. Returns the path as a list of node IDs (`from` first, `to` last), or `None` if no path exists within `max_depth` hops. Default: forward breadth-first search built on `graph_traverse`. Each frontier expansion calls `graph_traverse(node, 1, edge_filter)` to discover outgoing neighbors. Inherits the underlying impl's edge direction semantics. Implementation

(
        &self,
        collection: &str,
        from: &NodeId,
        to: &NodeId,
        max_depth: u8,
        edge_filter: Option<&EdgeFilter>,
    )

    /// performance — round-tripping per-hop is O(path_length) wire
    /// hops.
    async fn graph_shortest_path(
        &self,
        collection: &str,
        from: &NodeId,
        to: &NodeId,
        max_depth: u8,
        edge_filter: Option<&EdgeFilter>,
    ) -> NodeDbResult<Option<Vec<NodeId>>> {
        if from == to {
            return Ok(Some(vec![from.clone()]));
        }
        if max_depth == 0 {
            return Ok(None);
        }

        // Map of `node -> parent` used to reconstruct the path once the
        // target is reached. The source has no parent entry.
        let mut parent: std::collections::HashMap<NodeId, NodeId> =
            std::collections::HashMap::new();
        let mut frontier: Vec<NodeId> = vec![from.clone()];

        for _ in 0..max_depth {
            let mut next_frontier: Vec<NodeId> = Vec::new();
            for node in &frontier {
                let sg = self
                    .graph_traverse(collection, node, 1, edge_filter)
                    .await?;
                for edge in &sg.edges {
                    // Only follow edges originating from the current
                    // node — `graph_traverse` may include adjacent
                    // edges that don't extend the BFS frontier.
                    if &edge.from != node {
                        continue;
                    }
                    let dst = &edge.to;
                    if dst == from || parent.contains_key(dst) {
                        continue;
                    }
                    parent.insert(dst.clone(), node.clone());
                    if dst == to {
                        let mut path = vec![to.clone()];
                        let mut cur = to.clone();
                        while &cur != from {
                            let p = parent
                                .get(&cur)
                                .expect("BFS reached `to` so all ancestors are tracked")
                                .clone();
                            path.push(p.clone());
                            cur = p;
                        }
                        path.reverse();
                        return Ok(Some(path));
                    }
                    next_frontier.push(dst.clone());
                }
            }
            if next_frontier.is_empty() {
                return Ok(None);