nodedb_graph/
path_overlay.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! In-transaction (read-your-own-writes) bidirectional shortest path.
4//!
5//! Runs only when a non-empty [`GraphOverlayDelta`] is supplied. Like the
6//! string-keyed BFS in [`crate::traversal_overlay`], the two frontiers are
7//! keyed on the node *string* rather than the u32 CSR id. That choice is what
8//! makes bidirectional search correct across staged edges: a node reachable
9//! only via a staged edge has no durable surrogate, so the durable dense
10//! bidirectional path — which detects a meeting by comparing u32 ids — cannot
11//! represent it. With string keys, a staged-only meeting node is simply a
12//! string present in both the forward and backward parent maps; the
13//! meeting point is a plain string-set intersection and no synthetic
14//! (ephemeral) u32 id is ever minted.
15//!
16//! Each forward frontier node expands its OUT edges (durable CSR out via
17//! `node_to_id`, skipping staged tombstones and bitmap-excluded durable
18//! targets, unioned with `overlay.out_neighbors`). Each backward frontier
19//! node expands its IN edges symmetrically. Staged edges bypass the frontier
20//! bitmap: the transaction's own writes have no durable surrogate to gate on.
21
22use std::collections::HashMap;
23use std::collections::hash_map::Entry;
24
25use crate::csr::CsrIndex;
26use crate::overlay_delta::GraphOverlayDelta;
27use crate::path_params::ShortestPathParams;
28
29impl CsrIndex {
30    /// String-keyed bidirectional BFS that merges the transaction's staged
31    /// edges/tombstones. Mirrors the durable `shortest_path_dense` loop
32    /// structure (alternating one forward then one backward level per depth
33    /// step) so that, when the overlay contributes nothing, the result and
34    /// path shape match the durable search.
35    pub(crate) fn shortest_path_overlay(
36        &self,
37        params: ShortestPathParams<'_>,
38        overlay: &GraphOverlayDelta,
39    ) -> Option<Vec<String>> {
40        let ShortestPathParams {
41            src,
42            dst,
43            label_filter,
44            max_depth,
45            max_visited,
46            frontier_bitmap,
47        } = params;
48        if src == dst {
49            return Some(vec![src.to_string()]);
50        }
51
52        // parent maps: node -> the neighbour it was reached from. The endpoint
53        // maps to itself, marking the reconstruction terminus.
54        let mut fwd_parent: HashMap<String, String> = HashMap::new();
55        let mut bwd_parent: HashMap<String, String> = HashMap::new();
56        fwd_parent.insert(src.to_string(), src.to_string());
57        bwd_parent.insert(dst.to_string(), dst.to_string());
58
59        let mut fwd_frontier: Vec<String> = vec![src.to_string()];
60        let mut bwd_frontier: Vec<String> = vec![dst.to_string()];
61
62        let label_id = label_filter.and_then(|l| self.label_id(l));
63
64        for _depth in 0..max_depth {
65            if fwd_parent.len() + bwd_parent.len() >= max_visited {
66                break;
67            }
68
69            let mut next_fwd = Vec::new();
70            for node in std::mem::take(&mut fwd_frontier) {
71                let neighbors =
72                    self.forward_neighbors(&node, label_id, label_filter, frontier_bitmap, overlay);
73                for neighbor in neighbors {
74                    if let Some(meeting) = relax(
75                        &neighbor,
76                        &node,
77                        &mut fwd_parent,
78                        &bwd_parent,
79                        &mut next_fwd,
80                    ) {
81                        return Some(reconstruct(&meeting, &fwd_parent, &bwd_parent));
82                    }
83                }
84            }
85            fwd_frontier = next_fwd;
86
87            let mut next_bwd = Vec::new();
88            for node in std::mem::take(&mut bwd_frontier) {
89                let neighbors = self.backward_neighbors(
90                    &node,
91                    label_id,
92                    label_filter,
93                    frontier_bitmap,
94                    overlay,
95                );
96                for neighbor in neighbors {
97                    if let Some(meeting) = relax(
98                        &neighbor,
99                        &node,
100                        &mut bwd_parent,
101                        &fwd_parent,
102                        &mut next_bwd,
103                    ) {
104                        return Some(reconstruct(&meeting, &fwd_parent, &bwd_parent));
105                    }
106                }
107            }
108            bwd_frontier = next_bwd;
109
110            if fwd_frontier.is_empty() && bwd_frontier.is_empty() {
111                break;
112            }
113        }
114        None
115    }
116
117    /// OUT neighbours of `node`: durable CSR out edges (skipping staged
118    /// tombstones and bitmap-excluded durable targets) unioned with staged
119    /// out edges.
120    fn forward_neighbors(
121        &self,
122        node: &str,
123        label_id: Option<u32>,
124        label_filter: Option<&str>,
125        frontier_bitmap: Option<&nodedb_types::SurrogateBitmap>,
126        overlay: &GraphOverlayDelta,
127    ) -> Vec<String> {
128        let mut out = Vec::new();
129        if let Some(&node_id) = self.node_to_id.get(node) {
130            self.record_access(node_id);
131            for (lid, dst) in self.dense_iter_out(node_id) {
132                if label_id.is_some_and(|f| f != lid) {
133                    continue;
134                }
135                let dst_name = &self.id_to_node[dst as usize];
136                if overlay.is_tombstoned(node, self.label_name(lid), dst_name) {
137                    continue;
138                }
139                if !frontier_bitmap.is_none_or(|bm| {
140                    bm.contains(nodedb_types::Surrogate::new(self.node_surrogate_raw(dst)))
141                }) {
142                    continue;
143                }
144                out.push(dst_name.clone());
145            }
146        }
147        for (_, dst) in overlay.out_neighbors(node, label_filter) {
148            out.push(dst.to_string());
149        }
150        out
151    }
152
153    /// IN neighbours of `node`: durable CSR in edges (skipping staged
154    /// tombstones and bitmap-excluded durable sources) unioned with staged
155    /// in edges.
156    fn backward_neighbors(
157        &self,
158        node: &str,
159        label_id: Option<u32>,
160        label_filter: Option<&str>,
161        frontier_bitmap: Option<&nodedb_types::SurrogateBitmap>,
162        overlay: &GraphOverlayDelta,
163    ) -> Vec<String> {
164        let mut out = Vec::new();
165        if let Some(&node_id) = self.node_to_id.get(node) {
166            self.record_access(node_id);
167            for (lid, src) in self.dense_iter_in(node_id) {
168                if label_id.is_some_and(|f| f != lid) {
169                    continue;
170                }
171                let src_name = &self.id_to_node[src as usize];
172                if overlay.is_tombstoned(src_name, self.label_name(lid), node) {
173                    continue;
174                }
175                if !frontier_bitmap.is_none_or(|bm| {
176                    bm.contains(nodedb_types::Surrogate::new(self.node_surrogate_raw(src)))
177                }) {
178                    continue;
179                }
180                out.push(src_name.clone());
181            }
182        }
183        for (_, src) in overlay.in_neighbors(node, label_filter) {
184            out.push(src.to_string());
185        }
186        out
187    }
188}
189
190/// Record `neighbor` (reached from `parent`) in `this_parent` if unseen and
191/// queue it for the next level. Returns `Some(neighbor)` when the two searches
192/// have met — i.e. `neighbor` is already present in `other_parent`. Meeting
193/// detection is independent of whether `neighbor` was newly inserted, matching
194/// the durable dense search. The caller reconstructs the path with the fixed
195/// forward/backward maps, so orientation is never ambiguous.
196fn relax(
197    neighbor: &str,
198    parent: &str,
199    this_parent: &mut HashMap<String, String>,
200    other_parent: &HashMap<String, String>,
201    next_frontier: &mut Vec<String>,
202) -> Option<String> {
203    if let Entry::Vacant(e) = this_parent.entry(neighbor.to_string()) {
204        e.insert(parent.to_string());
205        next_frontier.push(neighbor.to_string());
206    }
207    if other_parent.contains_key(neighbor) {
208        return Some(neighbor.to_string());
209    }
210    None
211}
212
213/// Reconstruct the ordered `src -> dst` path through `meeting`. `fwd_parent`
214/// roots at `src`, `bwd_parent` roots at `dst`; `meeting` is present in both
215/// (a caller invariant). Mirrors the durable dense `reconstruct_path`.
216fn reconstruct(
217    meeting: &str,
218    fwd_parent: &HashMap<String, String>,
219    bwd_parent: &HashMap<String, String>,
220) -> Vec<String> {
221    let mut path = walk_to_root(meeting, fwd_parent);
222    path.reverse();
223
224    let suffix_root = &bwd_parent[meeting];
225    if suffix_root != meeting {
226        let mut cur = suffix_root.clone();
227        loop {
228            path.push(cur.clone());
229            let parent = &bwd_parent[&cur];
230            if *parent == cur {
231                break;
232            }
233            cur = parent.clone();
234        }
235    }
236    path
237}
238
239/// Walk the parent chain from `start` to its self-parent root, collecting each
240/// node (root last). Presence is a caller invariant.
241fn walk_to_root(start: &str, parents: &HashMap<String, String>) -> Vec<String> {
242    let mut chain = Vec::new();
243    let mut cur = start.to_string();
244    loop {
245        chain.push(cur.clone());
246        let parent = &parents[&cur];
247        if *parent == cur {
248            break;
249        }
250        cur = parent.clone();
251    }
252    chain
253}
254
255#[cfg(test)]
256mod tests {
257    use crate::csr::CsrIndex;
258    use crate::overlay_delta::GraphOverlayDelta;
259    use crate::path_params::ShortestPathParams;
260    use crate::traversal::DEFAULT_MAX_VISITED;
261
262    fn params<'a>(
263        src: &'a str,
264        dst: &'a str,
265        label_filter: Option<&'a str>,
266        max_depth: usize,
267    ) -> ShortestPathParams<'a> {
268        ShortestPathParams {
269            src,
270            dst,
271            label_filter,
272            max_depth,
273            max_visited: DEFAULT_MAX_VISITED,
274            frontier_bitmap: None,
275        }
276    }
277
278    /// A staged edge completes a path the durable graph lacks: durable A->B,
279    /// staged B->C, so A->B->C must be found only with the overlay.
280    #[test]
281    fn staged_edge_completes_path() {
282        let mut csr = CsrIndex::new();
283        csr.add_edge("a", "KNOWS", "b").unwrap();
284        let mut ov = GraphOverlayDelta::new();
285        ov.stage_edge("b", "KNOWS", "c");
286
287        let path = csr
288            .shortest_path(params("a", "c", Some("KNOWS"), 5), Some(&ov))
289            .expect("staged edge should complete the path");
290        assert_eq!(path, vec!["a", "b", "c"]);
291
292        // Without the overlay the path does not exist.
293        assert!(
294            csr.shortest_path(params("a", "c", Some("KNOWS"), 5), None)
295                .is_none()
296        );
297    }
298
299    /// A path entirely through staged-only intermediate nodes: no durable
300    /// edges touch A, X, or D. String-keyed frontiers let X (no surrogate)
301    /// participate as the meeting point.
302    #[test]
303    fn path_through_staged_only_node() {
304        let csr = CsrIndex::new();
305        let mut ov = GraphOverlayDelta::new();
306        ov.stage_edge("a", "KNOWS", "x");
307        ov.stage_edge("x", "KNOWS", "d");
308
309        let path = csr
310            .shortest_path(params("a", "d", Some("KNOWS"), 5), Some(&ov))
311            .expect("staged-only path should be found");
312        assert_eq!(path, vec!["a", "x", "d"]);
313    }
314
315    /// A staged tombstone removes the only durable direct edge, forcing a
316    /// longer detour that exists only via other durable edges.
317    #[test]
318    fn tombstone_forces_detour() {
319        // Durable: a->d (direct), a->b, b->d. Tombstone a->d. Detour a->b->d.
320        let mut csr = CsrIndex::new();
321        csr.add_edge("a", "KNOWS", "d").unwrap();
322        csr.add_edge("a", "KNOWS", "b").unwrap();
323        csr.add_edge("b", "KNOWS", "d").unwrap();
324        let mut ov = GraphOverlayDelta::new();
325        ov.stage_tombstone("a", "KNOWS", "d");
326
327        let path = csr
328            .shortest_path(params("a", "d", Some("KNOWS"), 5), Some(&ov))
329            .expect("detour path should be found");
330        assert_eq!(path, vec!["a", "b", "d"]);
331    }
332
333    /// A staged tombstone that removes the only path yields None.
334    #[test]
335    fn tombstone_removes_only_path() {
336        let mut csr = CsrIndex::new();
337        csr.add_edge("a", "KNOWS", "d").unwrap();
338        let mut ov = GraphOverlayDelta::new();
339        ov.stage_tombstone("a", "KNOWS", "d");
340
341        assert!(
342            csr.shortest_path(params("a", "d", Some("KNOWS"), 5), Some(&ov))
343                .is_none()
344        );
345    }
346
347    /// Empty overlay yields the same result as the durable dense search on a
348    /// small fixed graph (parity check).
349    #[test]
350    fn empty_overlay_matches_dense() {
351        let mut csr = CsrIndex::new();
352        csr.add_edge("a", "KNOWS", "b").unwrap();
353        csr.add_edge("b", "KNOWS", "c").unwrap();
354        csr.add_edge("c", "KNOWS", "d").unwrap();
355        let ov = GraphOverlayDelta::new();
356
357        // Empty overlay dispatches to dense; force the overlay code path by
358        // calling it directly, then compare with dense.
359        let dense = csr
360            .shortest_path(params("a", "d", Some("KNOWS"), 10), None)
361            .unwrap();
362        let overlaid = csr.shortest_path_overlay(params("a", "d", Some("KNOWS"), 10), &ov);
363        assert_eq!(overlaid, Some(dense));
364    }
365
366    #[test]
367    fn src_equals_dst() {
368        let mut csr = CsrIndex::new();
369        csr.add_edge("a", "KNOWS", "b").unwrap();
370        let mut ov = GraphOverlayDelta::new();
371        ov.stage_edge("a", "KNOWS", "x");
372        let path = csr
373            .shortest_path(params("a", "a", None, 5), Some(&ov))
374            .unwrap();
375        assert_eq!(path, vec!["a"]);
376    }
377
378    #[test]
379    fn unreachable_is_none() {
380        let mut csr = CsrIndex::new();
381        csr.add_edge("a", "KNOWS", "b").unwrap();
382        let mut ov = GraphOverlayDelta::new();
383        ov.stage_edge("m", "KNOWS", "n");
384        assert!(
385            csr.shortest_path(params("a", "n", Some("KNOWS"), 5), Some(&ov))
386                .is_none()
387        );
388    }
389}
nodedb_graph/path_overlay.rs

nodedb_graph/
path_overlay.rs
