uni_query/query/df_graph/
pred_dag.rs

1use fxhash::{FxHashMap, FxHashSet};
2use std::ops::ControlFlow;
3use uni_common::core::id::{Eid, Vid};
4
5use super::nfa::{NfaStateId, PathMode, PathSelector};
6
7/// A single predecessor record in the DAG pool.
8///
9/// Records that to reach `(dst_vid, dst_state)` at a given depth,
10/// one can come from `(src_vid, src_state)` via edge `eid`.
11/// The `next` field implements a singly-linked list within the pool.
12#[derive(Debug, Clone)]
13pub struct PredRec {
14    pub src_vid: Vid,
15    pub src_state: NfaStateId,
16    pub eid: Eid,
17    /// Index of next PredRec in the chain, or -1 for end of chain.
18    pub next: i32,
19}
20
21/// Predecessor DAG for path enumeration.
22///
23/// During BFS frontier expansion, predecessors are recorded into an append-only pool.
24/// After BFS completes, backward DFS through the DAG enumerates all valid paths
25/// while applying Trail/Acyclic/Simple filtering.
26pub struct PredecessorDag {
27    /// Append-only pool of predecessor records.
28    pred_pool: Vec<PredRec>,
29
30    /// Head of predecessor chain for each `(dst_vid, dst_state, depth)`.
31    /// Value is an index into `pred_pool`, or absent if no predecessors.
32    pred_head: FxHashMap<(Vid, NfaStateId, u32), i32>,
33
34    /// First-visit depth for each `(vid, state)`.
35    first_depth: FxHashMap<(Vid, NfaStateId), u32>,
36
37    /// Path selector determines DAG construction mode.
38    selector: PathSelector,
39}
40
41impl PredecessorDag {
42    /// Create a new empty DAG with the given path selector.
43    pub fn new(selector: PathSelector) -> Self {
44        Self {
45            pred_pool: Vec::new(),
46            pred_head: FxHashMap::default(),
47            first_depth: FxHashMap::default(),
48            selector,
49        }
50    }
51
52    /// Returns true for layered DAG modes (All/Any), false for shortest-only.
53    pub fn is_layered(&self) -> bool {
54        matches!(self.selector, PathSelector::All | PathSelector::Any)
55    }
56
57    /// Add a predecessor record to the DAG.
58    ///
59    /// Records that to reach `(dst, dst_state)` at `depth`, one can come from
60    /// `(src, src_state)` via edge `eid`. In shortest-only mode, predecessors
61    /// at depths greater than the first-visit depth are skipped.
62    pub fn add_predecessor(
63        &mut self,
64        dst: Vid,
65        dst_state: NfaStateId,
66        src: Vid,
67        src_state: NfaStateId,
68        eid: Eid,
69        depth: u32,
70    ) {
71        // Update first_depth to track minimum discovery depth.
72        let first = self.first_depth.entry((dst, dst_state)).or_insert(depth);
73        if depth < *first {
74            *first = depth;
75        }
76
77        // For shortest-only mode, skip predecessors at depths > first visit.
78        if !self.is_layered() && depth > *self.first_depth.get(&(dst, dst_state)).unwrap() {
79            return;
80        }
81
82        // Get current head for this (dst, dst_state, depth) chain.
83        let key = (dst, dst_state, depth);
84        let current_head = self.pred_head.get(&key).copied().unwrap_or(-1);
85
86        // Append new PredRec to pool, linking to current head.
87        let new_idx = self.pred_pool.len() as i32;
88        self.pred_pool.push(PredRec {
89            src_vid: src,
90            src_state,
91            eid,
92            next: current_head,
93        });
94
95        // Update head to point to new record.
96        self.pred_head.insert(key, new_idx);
97    }
98
99    /// Enumerate all valid paths from `source` to `target` through `accepting_state`.
100    ///
101    /// Iterates over depths in `[min_depth, max_depth]`, performing backward DFS
102    /// through predecessor chains. Applies mode-specific filtering (Trail/Acyclic/Simple).
103    /// The callback can return `ControlFlow::Break(())` to stop enumeration early.
104    #[expect(
105        clippy::too_many_arguments,
106        reason = "path enumeration requires full traversal context"
107    )]
108    pub fn enumerate_paths<F>(
109        &self,
110        source: Vid,
111        target: Vid,
112        accepting_state: NfaStateId,
113        min_depth: u32,
114        max_depth: u32,
115        mode: &PathMode,
116        yield_path: &mut F,
117    ) where
118        F: FnMut(&[Vid], &[Eid]) -> ControlFlow<()>,
119    {
120        for depth in min_depth..=max_depth {
121            // Special case: zero-length path.
122            if depth == 0 {
123                if source == target && yield_path(&[source], &[]).is_break() {
124                    return;
125                }
126                continue;
127            }
128
129            if !self
130                .pred_head
131                .contains_key(&(target, accepting_state, depth))
132            {
133                continue;
134            }
135
136            let mut nodes = Vec::with_capacity(depth as usize + 1);
137            let mut edges = Vec::with_capacity(depth as usize);
138            let mut node_set = FxHashSet::default();
139            let mut edge_set = FxHashSet::default();
140
141            // Start backward DFS from target.
142            nodes.push(target);
143            if matches!(mode, PathMode::Acyclic | PathMode::Simple) {
144                node_set.insert(target);
145            }
146
147            if self
148                .dfs_backward(
149                    source,
150                    target,
151                    accepting_state,
152                    depth,
153                    &mut nodes,
154                    &mut edges,
155                    &mut node_set,
156                    &mut edge_set,
157                    mode,
158                    yield_path,
159                )
160                .is_break()
161            {
162                return;
163            }
164        }
165    }
166
167    /// Check if at least one Trail-valid path exists from source to target.
168    ///
169    /// Returns true on the first valid path found (early-stop).
170    pub fn has_trail_valid_path(
171        &self,
172        source: Vid,
173        target: Vid,
174        accepting_state: NfaStateId,
175        min_depth: u32,
176        max_depth: u32,
177    ) -> bool {
178        let mut found = false;
179        self.enumerate_paths(
180            source,
181            target,
182            accepting_state,
183            min_depth,
184            max_depth,
185            &PathMode::Trail,
186            &mut |_nodes, _edges| {
187                found = true;
188                ControlFlow::Break(())
189            },
190        );
191        found
192    }
193
194    /// Internal backward DFS through predecessor chains.
195    #[expect(
196        clippy::too_many_arguments,
197        reason = "recursive DFS carries full path state"
198    )]
199    fn dfs_backward<F>(
200        &self,
201        source: Vid,
202        current_vid: Vid,
203        current_state: NfaStateId,
204        remaining_depth: u32,
205        nodes: &mut Vec<Vid>,
206        edges: &mut Vec<Eid>,
207        node_set: &mut FxHashSet<Vid>,
208        edge_set: &mut FxHashSet<Eid>,
209        mode: &PathMode,
210        yield_path: &mut F,
211    ) -> ControlFlow<()>
212    where
213        F: FnMut(&[Vid], &[Eid]) -> ControlFlow<()>,
214    {
215        if remaining_depth == 0 {
216            if current_vid == source {
217                // Reverse stacks to get forward path order.
218                let fwd_nodes: Vec<Vid> = nodes.iter().rev().copied().collect();
219                let fwd_edges: Vec<Eid> = edges.iter().rev().copied().collect();
220                return yield_path(&fwd_nodes, &fwd_edges);
221            }
222            return ControlFlow::Continue(());
223        }
224
225        let key = (current_vid, current_state, remaining_depth);
226        let Some(&head) = self.pred_head.get(&key) else {
227            return ControlFlow::Continue(());
228        };
229
230        let mut idx = head;
231        while idx >= 0 {
232            let pred = &self.pred_pool[idx as usize];
233
234            // Mode-specific filtering.
235            let skip = match mode {
236                PathMode::Walk => false,
237                PathMode::Trail => edge_set.contains(&pred.eid),
238                PathMode::Acyclic => node_set.contains(&pred.src_vid),
239                PathMode::Simple => {
240                    // No repeated nodes except source may equal target.
241                    node_set.contains(&pred.src_vid)
242                        && !(remaining_depth == 1 && pred.src_vid == source)
243                }
244            };
245
246            if skip {
247                idx = pred.next;
248                continue;
249            }
250
251            // Push to stacks.
252            nodes.push(pred.src_vid);
253            edges.push(pred.eid);
254
255            if matches!(mode, PathMode::Trail) {
256                edge_set.insert(pred.eid);
257            }
258            if matches!(mode, PathMode::Acyclic | PathMode::Simple) {
259                node_set.insert(pred.src_vid);
260            }
261
262            // Recurse.
263            let result = self.dfs_backward(
264                source,
265                pred.src_vid,
266                pred.src_state,
267                remaining_depth - 1,
268                nodes,
269                edges,
270                node_set,
271                edge_set,
272                mode,
273                yield_path,
274            );
275
276            // Pop from stacks.
277            nodes.pop();
278            edges.pop();
279
280            if matches!(mode, PathMode::Trail) {
281                edge_set.remove(&pred.eid);
282            }
283            if matches!(mode, PathMode::Acyclic | PathMode::Simple) {
284                node_set.remove(&pred.src_vid);
285            }
286
287            if result.is_break() {
288                return ControlFlow::Break(());
289            }
290
291            idx = pred.next;
292        }
293
294        ControlFlow::Continue(())
295    }
296
297    /// Get the number of records in the predecessor pool.
298    pub fn pool_len(&self) -> usize {
299        self.pred_pool.len()
300    }
301
302    /// Get the first-visit depth for a (vid, state) pair, if any.
303    pub fn first_depth_of(&self, vid: Vid, state: NfaStateId) -> Option<u32> {
304        self.first_depth.get(&(vid, state)).copied()
305    }
306}
307
308#[cfg(test)]
309mod tests {
310    use super::*;
311
312    fn vid(n: u64) -> Vid {
313        Vid::new(n)
314    }
315    fn eid(n: u64) -> Eid {
316        Eid::new(n)
317    }
318
319    /// Collect all enumerated paths as (Vec<Vid>, Vec<Eid>) pairs.
320    fn collect_paths(
321        dag: &PredecessorDag,
322        source: Vid,
323        target: Vid,
324        accepting_state: NfaStateId,
325        min_depth: u32,
326        max_depth: u32,
327        mode: &PathMode,
328    ) -> Vec<(Vec<Vid>, Vec<Eid>)> {
329        let mut paths = Vec::new();
330        dag.enumerate_paths(
331            source,
332            target,
333            accepting_state,
334            min_depth,
335            max_depth,
336            mode,
337            &mut |nodes, edges| {
338                paths.push((nodes.to_vec(), edges.to_vec()));
339                ControlFlow::Continue(())
340            },
341        );
342        paths
343    }
344
345    // ── Pool Storage Tests (23-26) ─────────────────────────────────────
346
347    #[test]
348    fn test_pred_dag_add_single() {
349        let mut dag = PredecessorDag::new(PathSelector::All);
350        dag.add_predecessor(vid(2), 1, vid(1), 0, eid(10), 1);
351        assert_eq!(dag.pool_len(), 1);
352        assert!(dag.pred_head.contains_key(&(vid(2), 1, 1)));
353    }
354
355    #[test]
356    fn test_pred_dag_add_chain() {
357        // A(0)→B(1)→C(2) chain
358        let mut dag = PredecessorDag::new(PathSelector::All);
359        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(10), 1);
360        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(11), 2);
361        assert_eq!(dag.pool_len(), 2);
362        assert!(dag.pred_head.contains_key(&(vid(1), 1, 1)));
363        assert!(dag.pred_head.contains_key(&(vid(2), 2, 2)));
364    }
365
366    #[test]
367    fn test_pred_dag_multiple_preds() {
368        // Both A(0) and B(1) reach C(2) at depth 1
369        let mut dag = PredecessorDag::new(PathSelector::All);
370        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(10), 1);
371        dag.add_predecessor(vid(2), 1, vid(1), 0, eid(11), 1);
372        assert_eq!(dag.pool_len(), 2);
373        // Both are in the same chain for (vid(2), state=1, depth=1)
374        let head = dag.pred_head[&(vid(2), 1, 1)];
375        assert!(head >= 0);
376        let first = &dag.pred_pool[head as usize];
377        assert!(first.next >= 0); // Chain has a second element
378    }
379
380    #[test]
381    fn test_pred_dag_first_depth() {
382        let mut dag = PredecessorDag::new(PathSelector::All);
383        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(10), 3);
384        assert_eq!(dag.first_depth_of(vid(2), 1), Some(3));
385
386        dag.add_predecessor(vid(2), 1, vid(1), 0, eid(11), 2);
387        assert_eq!(dag.first_depth_of(vid(2), 1), Some(2));
388
389        // Adding at higher depth doesn't change first_depth
390        dag.add_predecessor(vid(2), 1, vid(3), 0, eid(12), 5);
391        assert_eq!(dag.first_depth_of(vid(2), 1), Some(2));
392    }
393
394    // ── PathSelector / DAG Mode Tests (27-29) ─────────────────────────
395
396    #[test]
397    fn test_pred_dag_layered_stores_all() {
398        let mut dag = PredecessorDag::new(PathSelector::All);
399        assert!(dag.is_layered());
400
401        // Add at depth 2 and depth 3 — both should be stored
402        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(10), 2);
403        dag.add_predecessor(vid(2), 1, vid(1), 0, eid(11), 3);
404        assert_eq!(dag.pool_len(), 2);
405        assert!(dag.pred_head.contains_key(&(vid(2), 1, 2)));
406        assert!(dag.pred_head.contains_key(&(vid(2), 1, 3)));
407    }
408
409    #[test]
410    fn test_pred_dag_shortest_skips() {
411        let mut dag = PredecessorDag::new(PathSelector::AnyShortest);
412        assert!(!dag.is_layered());
413
414        // First visit at depth 2
415        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(10), 2);
416        assert_eq!(dag.pool_len(), 1);
417
418        // Second visit at depth 3 — should be skipped
419        dag.add_predecessor(vid(2), 1, vid(1), 0, eid(11), 3);
420        assert_eq!(dag.pool_len(), 1); // Still 1 — depth 3 was skipped
421
422        // Another visit at depth 2 — should be stored (same depth as first)
423        dag.add_predecessor(vid(2), 1, vid(3), 0, eid(12), 2);
424        assert_eq!(dag.pool_len(), 2);
425    }
426
427    #[test]
428    fn test_pred_dag_selector_switch() {
429        // Same graph, different selectors produce different pool sizes
430        let build = |selector: PathSelector| -> usize {
431            let mut dag = PredecessorDag::new(selector);
432            dag.add_predecessor(vid(2), 1, vid(0), 0, eid(10), 2);
433            dag.add_predecessor(vid(2), 1, vid(1), 0, eid(11), 3);
434            dag.add_predecessor(vid(2), 1, vid(3), 0, eid(12), 4);
435            dag.pool_len()
436        };
437
438        assert_eq!(build(PathSelector::All), 3); // Layered: stores all
439        assert_eq!(build(PathSelector::AnyShortest), 1); // Only depth 2
440    }
441
442    // ── Walk Enumeration Tests (30-33) ─────────────────────────────────
443
444    #[test]
445    fn test_pred_dag_linear_walk() {
446        // A(0) → B(1) → C(2) linear chain
447        let mut dag = PredecessorDag::new(PathSelector::All);
448        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(10), 1);
449        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(11), 2);
450
451        let paths = collect_paths(&dag, vid(0), vid(2), 2, 2, 2, &PathMode::Walk);
452        assert_eq!(paths.len(), 1);
453        assert_eq!(paths[0].0, vec![vid(0), vid(1), vid(2)]);
454        assert_eq!(paths[0].1, vec![eid(10), eid(11)]);
455    }
456
457    #[test]
458    fn test_pred_dag_diamond_walk() {
459        // A(0) → {B(1), C(2)} → D(3) diamond
460        let mut dag = PredecessorDag::new(PathSelector::All);
461        // A→B and A→C at depth 1
462        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(10), 1);
463        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(11), 1);
464        // B→D and C→D at depth 2
465        dag.add_predecessor(vid(3), 2, vid(1), 1, eid(12), 2);
466        dag.add_predecessor(vid(3), 2, vid(2), 1, eid(13), 2);
467
468        let paths = collect_paths(&dag, vid(0), vid(3), 2, 2, 2, &PathMode::Walk);
469        assert_eq!(paths.len(), 2);
470
471        let mut sorted: Vec<_> = paths.iter().map(|(n, _)| n.clone()).collect();
472        sorted.sort();
473        assert!(sorted.contains(&vec![vid(0), vid(1), vid(3)]));
474        assert!(sorted.contains(&vec![vid(0), vid(2), vid(3)]));
475    }
476
477    #[test]
478    fn test_pred_dag_multiple_depths() {
479        // Target reachable at depth 1 (state q1) and depth 2 (state q2).
480        // In a linear NFA, different depths use different NFA states.
481        let mut dag = PredecessorDag::new(PathSelector::All);
482        // Direct: A→C at depth 1, arriving at state 1
483        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(10), 1);
484        // Via B: A→B at depth 1 (state 1), B→C at depth 2 (state 2)
485        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(11), 1);
486        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(12), 2);
487
488        // Depth 1 via accepting state 1
489        let paths1 = collect_paths(&dag, vid(0), vid(2), 1, 1, 1, &PathMode::Walk);
490        assert_eq!(paths1.len(), 1);
491        assert_eq!(paths1[0].0, vec![vid(0), vid(2)]); // [A, C]
492
493        // Depth 2 via accepting state 2
494        let paths2 = collect_paths(&dag, vid(0), vid(2), 2, 2, 2, &PathMode::Walk);
495        assert_eq!(paths2.len(), 1);
496        assert_eq!(paths2[0].0, vec![vid(0), vid(1), vid(2)]); // [A, B, C]
497
498        // Total: 2 paths across both accepting states
499        assert_eq!(paths1.len() + paths2.len(), 2);
500    }
501
502    #[test]
503    fn test_pred_dag_fan_out() {
504        // A(0) → {B1(1), B2(2), B3(3)} → C(4)
505        let mut dag = PredecessorDag::new(PathSelector::All);
506        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(10), 1);
507        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(11), 1);
508        dag.add_predecessor(vid(3), 1, vid(0), 0, eid(12), 1);
509        dag.add_predecessor(vid(4), 2, vid(1), 1, eid(13), 2);
510        dag.add_predecessor(vid(4), 2, vid(2), 1, eid(14), 2);
511        dag.add_predecessor(vid(4), 2, vid(3), 1, eid(15), 2);
512
513        let paths = collect_paths(&dag, vid(0), vid(4), 2, 2, 2, &PathMode::Walk);
514        assert_eq!(paths.len(), 3);
515    }
516
517    // ── Trail Mode Tests (34-37) ──────────────────────────────────────
518
519    #[test]
520    fn test_pred_dag_trail_no_repeat() {
521        // A(0) → B(1) → A(0) → C(2) via edges e1, e2, e1
522        // The path A→B→A→B uses edge e1 twice — rejected by Trail
523        let mut dag = PredecessorDag::new(PathSelector::All);
524        // depth 1: B reached from A via e1
525        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(1), 1);
526        // depth 2: A reached from B via e2
527        dag.add_predecessor(vid(0), 2, vid(1), 1, eid(2), 2);
528        // depth 3: B reached from A via e1 again (same edge!)
529        dag.add_predecessor(vid(1), 3, vid(0), 2, eid(1), 3);
530
531        // Walk mode: path exists (edge repeat OK)
532        let walk_paths = collect_paths(&dag, vid(0), vid(1), 3, 3, 3, &PathMode::Walk);
533        assert_eq!(walk_paths.len(), 1);
534        assert_eq!(walk_paths[0].1, vec![eid(1), eid(2), eid(1)]);
535
536        // Trail mode: path rejected (e1 appears twice)
537        let trail_paths = collect_paths(&dag, vid(0), vid(1), 3, 3, 3, &PathMode::Trail);
538        assert_eq!(trail_paths.len(), 0);
539    }
540
541    #[test]
542    fn test_pred_dag_trail_allows_node_repeat() {
543        // A(0) → B(1) → C(2) → B(1) with distinct edges e1, e2, e3
544        // Trail allows this (node B repeated but all edges distinct)
545        let mut dag = PredecessorDag::new(PathSelector::All);
546        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(1), 1);
547        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(2), 2);
548        dag.add_predecessor(vid(1), 3, vid(2), 2, eid(3), 3);
549
550        let paths = collect_paths(&dag, vid(0), vid(1), 3, 3, 3, &PathMode::Trail);
551        assert_eq!(paths.len(), 1);
552        assert_eq!(paths[0].0, vec![vid(0), vid(1), vid(2), vid(1)]);
553        assert_eq!(paths[0].1, vec![eid(1), eid(2), eid(3)]);
554    }
555
556    #[test]
557    fn test_pred_dag_trail_diamond() {
558        // Diamond A→{B,C}→D with distinct edges on each path
559        let mut dag = PredecessorDag::new(PathSelector::All);
560        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(10), 1);
561        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(11), 1);
562        dag.add_predecessor(vid(3), 2, vid(1), 1, eid(12), 2);
563        dag.add_predecessor(vid(3), 2, vid(2), 1, eid(13), 2);
564
565        // Trail: both paths kept (distinct edges on each)
566        let paths = collect_paths(&dag, vid(0), vid(3), 2, 2, 2, &PathMode::Trail);
567        assert_eq!(paths.len(), 2);
568    }
569
570    #[test]
571    fn test_pred_dag_trail_cycle_2_hop() {
572        // A→B→A on *2 pattern
573        // depth 1: B from A via e1
574        // depth 2: A from B via e2
575        // This uses distinct edges so Trail allows it
576        let mut dag = PredecessorDag::new(PathSelector::All);
577        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(1), 1);
578        dag.add_predecessor(vid(0), 2, vid(1), 1, eid(2), 2);
579
580        let paths = collect_paths(&dag, vid(0), vid(0), 2, 2, 2, &PathMode::Trail);
581        assert_eq!(paths.len(), 1);
582        assert_eq!(paths[0].0, vec![vid(0), vid(1), vid(0)]);
583        assert_eq!(paths[0].1, vec![eid(1), eid(2)]);
584    }
585
586    // ── Acyclic Mode Tests (38-39) ────────────────────────────────────
587
588    #[test]
589    fn test_pred_dag_acyclic_filter() {
590        // A(0) → B(1) → C(2) → A(0) — node A repeated
591        let mut dag = PredecessorDag::new(PathSelector::All);
592        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(1), 1);
593        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(2), 2);
594        dag.add_predecessor(vid(0), 3, vid(2), 2, eid(3), 3);
595
596        // Walk: path exists
597        let walk_paths = collect_paths(&dag, vid(0), vid(0), 3, 3, 3, &PathMode::Walk);
598        assert_eq!(walk_paths.len(), 1);
599
600        // Acyclic: path rejected (node A repeated)
601        let acyclic_paths = collect_paths(&dag, vid(0), vid(0), 3, 3, 3, &PathMode::Acyclic);
602        assert_eq!(acyclic_paths.len(), 0);
603    }
604
605    #[test]
606    fn test_pred_dag_acyclic_diamond() {
607        // Diamond A→{B,C}→D — no node repeats
608        let mut dag = PredecessorDag::new(PathSelector::All);
609        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(10), 1);
610        dag.add_predecessor(vid(2), 1, vid(0), 0, eid(11), 1);
611        dag.add_predecessor(vid(3), 2, vid(1), 1, eid(12), 2);
612        dag.add_predecessor(vid(3), 2, vid(2), 1, eid(13), 2);
613
614        let paths = collect_paths(&dag, vid(0), vid(3), 2, 2, 2, &PathMode::Acyclic);
615        assert_eq!(paths.len(), 2);
616    }
617
618    // ── Trail Existence Tests (40-42) ─────────────────────────────────
619
620    #[test]
621    fn test_has_trail_valid_true() {
622        // Simple A→B→C chain — Trail-valid
623        let mut dag = PredecessorDag::new(PathSelector::All);
624        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(10), 1);
625        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(11), 2);
626
627        assert!(dag.has_trail_valid_path(vid(0), vid(2), 2, 2, 2));
628    }
629
630    #[test]
631    fn test_has_trail_valid_false() {
632        // Only path to target reuses an edge
633        let mut dag = PredecessorDag::new(PathSelector::All);
634        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(1), 1);
635        dag.add_predecessor(vid(0), 2, vid(1), 1, eid(2), 2);
636        dag.add_predecessor(vid(1), 3, vid(0), 2, eid(1), 3); // e1 reused
637
638        assert!(!dag.has_trail_valid_path(vid(0), vid(1), 3, 3, 3));
639    }
640
641    #[test]
642    fn test_has_trail_valid_one_of_many() {
643        // Two paths to target: one valid, one not
644        let mut dag = PredecessorDag::new(PathSelector::All);
645        // Path 1: A→B→C (valid, distinct edges)
646        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(1), 1);
647        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(2), 2);
648        // Path 2: A→D→C (also valid)
649        dag.add_predecessor(vid(3), 1, vid(0), 0, eid(3), 1);
650        dag.add_predecessor(vid(2), 2, vid(3), 1, eid(4), 2);
651
652        // At least one valid → true
653        assert!(dag.has_trail_valid_path(vid(0), vid(2), 2, 2, 2));
654    }
655
656    // ── Streaming & Early Termination Tests (43-45) ───────────────────
657
658    #[test]
659    fn test_pred_dag_early_stop() {
660        // Build a DAG with many paths, verify callback can break early.
661        // Fan-out: A → {B1..B10} → C (10 paths of length 2)
662        let mut dag = PredecessorDag::new(PathSelector::All);
663        for i in 1..=10u64 {
664            dag.add_predecessor(Vid::new(i), 1, vid(0), 0, Eid::new(i), 1);
665            dag.add_predecessor(vid(99), 2, Vid::new(i), 1, Eid::new(100 + i), 2);
666        }
667
668        let mut count = 0;
669        dag.enumerate_paths(
670            vid(0),
671            vid(99),
672            2,
673            2,
674            2,
675            &PathMode::Walk,
676            &mut |_nodes, _edges| {
677                count += 1;
678                if count >= 3 {
679                    ControlFlow::Break(())
680                } else {
681                    ControlFlow::Continue(())
682                }
683            },
684        );
685        assert_eq!(count, 3); // Stopped after 3, not 10
686    }
687
688    #[test]
689    fn test_pred_dag_empty_enumerate() {
690        // Empty DAG — no paths
691        let dag = PredecessorDag::new(PathSelector::All);
692        let paths = collect_paths(&dag, vid(0), vid(1), 0, 1, 5, &PathMode::Walk);
693        assert!(paths.is_empty());
694    }
695
696    #[test]
697    fn test_pred_dag_zero_length() {
698        // Zero-length path: source == target with min_depth=0
699        let dag = PredecessorDag::new(PathSelector::All);
700        let paths = collect_paths(&dag, vid(5), vid(5), 0, 0, 0, &PathMode::Walk);
701        assert_eq!(paths.len(), 1);
702        assert_eq!(paths[0].0, vec![vid(5)]);
703        assert!(paths[0].1.is_empty());
704    }
705
706    // ── Correctness Tests (46-47) ─────────────────────────────────────
707
708    #[test]
709    fn test_pred_dag_path_order() {
710        // Verify nodes and edges are in correct forward order (source → target)
711        // Build: A(0)→B(1)→C(2)→D(3)
712        let mut dag = PredecessorDag::new(PathSelector::All);
713        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(10), 1);
714        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(20), 2);
715        dag.add_predecessor(vid(3), 3, vid(2), 2, eid(30), 3);
716
717        let paths = collect_paths(&dag, vid(0), vid(3), 3, 3, 3, &PathMode::Walk);
718        assert_eq!(paths.len(), 1);
719        // Forward order: source first, target last
720        assert_eq!(paths[0].0, vec![vid(0), vid(1), vid(2), vid(3)]);
721        assert_eq!(paths[0].1, vec![eid(10), eid(20), eid(30)]);
722    }
723
724    #[test]
725    fn test_pred_dag_eid_in_path() {
726        // Verify edges match traversal order exactly
727        // A(0) →e1→ B(1) →e2→ C(2) →e3→ D(3)
728        let mut dag = PredecessorDag::new(PathSelector::All);
729        dag.add_predecessor(vid(1), 1, vid(0), 0, eid(100), 1);
730        dag.add_predecessor(vid(2), 2, vid(1), 1, eid(200), 2);
731        dag.add_predecessor(vid(3), 3, vid(2), 2, eid(300), 3);
732
733        let paths = collect_paths(&dag, vid(0), vid(3), 3, 3, 3, &PathMode::Walk);
734        assert_eq!(paths.len(), 1);
735
736        // Edge e1 connects nodes[0]→nodes[1], e2 connects nodes[1]→nodes[2], etc.
737        let (nodes, edges) = &paths[0];
738        assert_eq!(nodes.len(), edges.len() + 1);
739        assert_eq!(edges[0], eid(100)); // A→B
740        assert_eq!(edges[1], eid(200)); // B→C
741        assert_eq!(edges[2], eid(300)); // C→D
742    }
743}
uni_query/query/df_graph/pred_dag.rs

uni_query/query/df_graph/
pred_dag.rs
