oxgraph_db/
traversal.rs

1//! Graph projection traversal primitives.
2
3use core::ops::ControlFlow;
4
5use oxgraph_algo::{
6    BfsBounds, BfsEpochScratch, breadth_first_search_bounded, breadth_first_search_bounded_both,
7    reverse_breadth_first_search_bounded,
8};
9use oxgraph_graph::{CanonicalElementIdentity, ElementIndex, LocalElementIdentity};
10
11use crate::{
12    DbError, ElementId,
13    projection::{GraphProjection, ProjectionElementId},
14};
15
16/// Direction used by graph projection traversal.
17///
18/// # Performance
19///
20/// Copying and comparing are `O(1)`.
21#[derive(Clone, Copy, Debug, Default, Eq, Hash, Ord, PartialEq, PartialOrd)]
22pub enum TraversalDirection {
23    /// Follow outgoing graph projection neighbors.
24    #[default]
25    Outgoing,
26    /// Follow incoming graph projection neighbors.
27    Incoming,
28    /// Follow outgoing neighbors first, then incoming neighbors.
29    Both,
30}
31
32/// Options for bounded graph projection traversal.
33///
34/// # Performance
35///
36/// Copying is `O(1)`.
37#[derive(Clone, Copy, Debug, Eq, PartialEq)]
38pub struct TraversalOptions {
39    /// Maximum hop depth to traverse from any seed.
40    pub max_depth: usize,
41    /// Direction used to expand each frontier element.
42    pub direction: TraversalDirection,
43    /// Maximum number of rows to emit.
44    pub limit: usize,
45    /// Whether depth-0 seed elements are included in the result rows.
46    pub include_start: bool,
47}
48
49impl Default for TraversalOptions {
50    /// Creates outgoing depth-1 traversal options with an unbounded row limit.
51    ///
52    /// # Performance
53    ///
54    /// This function is `O(1)`.
55    fn default() -> Self {
56        Self {
57            max_depth: 1,
58            direction: TraversalDirection::Outgoing,
59            limit: usize::MAX,
60            include_start: false,
61        }
62    }
63}
64
65/// One graph traversal result row.
66///
67/// # Performance
68///
69/// Copying and comparing are `O(1)`.
70#[derive(Clone, Copy, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
71pub struct TraversalRow {
72    /// Canonical element discovered by traversal.
73    pub element: ElementId,
74    /// Shortest discovered hop depth from any seed.
75    pub depth: usize,
76}
77
78/// Materialized graph traversal result.
79///
80/// Rows are unique by canonical element and ordered by BFS first discovery.
81///
82/// # Performance
83///
84/// Iterating rows is `O(row count)`.
85#[derive(Clone, Debug, Eq, PartialEq)]
86pub struct TraversalResult {
87    /// Materialized traversal rows.
88    rows: Vec<TraversalRow>,
89}
90
91impl TraversalResult {
92    /// Creates a traversal result from rows.
93    ///
94    /// # Performance
95    ///
96    /// This function is `O(1)` excluding row ownership transfer.
97    #[must_use]
98    pub(crate) const fn new(rows: Vec<TraversalRow>) -> Self {
99        Self { rows }
100    }
101
102    /// Returns result rows.
103    ///
104    /// # Performance
105    ///
106    /// This method is `O(1)`.
107    #[must_use]
108    pub fn rows(&self) -> &[TraversalRow] {
109        &self.rows
110    }
111}
112
113/// Traverses a materialized graph projection over the substrate bounded BFS.
114///
115/// Seeds, depth bound, row limit, and seed inclusion map onto
116/// [`BfsBounds`]; the visitor records each discovered element as one
117/// [`TraversalRow`] in first-discovery order. Outgoing traversal uses
118/// [`breadth_first_search_bounded`], incoming uses
119/// [`reverse_breadth_first_search_bounded`], and both uses
120/// [`breadth_first_search_bounded_both`]. The projection already exposes the
121/// `ContainsElement + ElementIndex + ElementSuccessors + ElementPredecessors`
122/// capabilities these entry points require.
123pub(crate) fn traverse_graph_projection(
124    graph: &GraphProjection,
125    seeds: &[ElementId],
126    options: TraversalOptions,
127) -> Result<TraversalResult, DbError> {
128    if seeds.is_empty() || options.limit == 0 {
129        return Ok(TraversalResult::new(Vec::new()));
130    }
131
132    let local_seeds = seeds
133        .iter()
134        .map(|seed| {
135            graph
136                .local_element_id(*seed)
137                .ok_or(DbError::UnknownElement { id: *seed })
138        })
139        .collect::<Result<Vec<ProjectionElementId>, DbError>>()?;
140
141    let bounds = BfsBounds {
142        max_depth: Some(u32::try_from(options.max_depth).unwrap_or(u32::MAX)),
143        result_limit: options.limit,
144        include_seeds: options.include_start,
145    };
146
147    let bound = graph.element_bound();
148    let mut marks = vec![0_u32; bound];
149    let mut queue = vec![ProjectionElementId::new(0); bound];
150    let mut scratch = BfsEpochScratch::for_graph(graph, &mut marks, &mut queue);
151
152    let mut rows = Vec::new();
153    {
154        let mut visitor = |element: ProjectionElementId, depth: u32| {
155            rows.push(TraversalRow {
156                element: graph.canonical_element_id(element),
157                depth: usize::try_from(depth).unwrap_or(usize::MAX),
158            });
159            ControlFlow::Continue(())
160        };
161
162        match options.direction {
163            TraversalDirection::Outgoing => breadth_first_search_bounded(
164                graph,
165                &local_seeds,
166                bounds,
167                &mut scratch,
168                &mut visitor,
169            ),
170            TraversalDirection::Incoming => reverse_breadth_first_search_bounded(
171                graph,
172                &local_seeds,
173                bounds,
174                &mut scratch,
175                &mut visitor,
176            ),
177            TraversalDirection::Both => breadth_first_search_bounded_both(
178                graph,
179                &local_seeds,
180                bounds,
181                &mut scratch,
182                &mut visitor,
183            ),
184        }
185        .map_err(DbError::traversal)?;
186    }
187
188    Ok(TraversalResult::new(rows))
189}
oxgraph_db/traversal.rs

oxgraph_db/
traversal.rs
