uqa_graph/operators/
regular_path.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! DFA-backed regular path reachability.
8
9use super::{
10    build_nfa, simplify, subset_construction, BTreeMap, BTreeSet, Dfa, DfaState, DocId,
11    GraphPayload, GraphPostingList, GraphStore, GraphStoreError, GraphStoreResult, Payload,
12    PostingEntry, PostingList, RegularPathExpr, VecDeque, VertexId, DEFAULT_GRAPH_SCORE,
13};
14
15/// `RPQ_R` (Definition 5.1.2): evaluate a regular path expression over
16/// a graph. The expression is simplified, compiled to an NFA via
17/// Thompson's construction, then converted to a DFA and simulated by a
18/// BFS over `(vertex, dfa-state)` configurations.
19///
20/// The result lists every endpoint vertex reachable from a start
21/// vertex along a path matching the expression. Each endpoint becomes
22/// one entry in the returned `GraphPostingList`.
23pub struct RegularPathQuery<'a> {
24    pub path: RegularPathExpr,
25    pub graph: &'a str,
26    /// `Some(start)` restricts evaluation to a single source. `None`
27    /// runs the query from every vertex in the graph.
28    pub start_vertex: Option<VertexId>,
29    pub score: f64,
30}
31
32impl<'a> RegularPathQuery<'a> {
33    pub fn new(path: RegularPathExpr, graph: &'a str) -> Self {
34        Self {
35            path,
36            graph,
37            start_vertex: None,
38            score: DEFAULT_GRAPH_SCORE,
39        }
40    }
41
42    pub fn from_vertex(mut self, start: VertexId) -> Self {
43        self.start_vertex = Some(start);
44        self
45    }
46
47    pub fn execute<G: GraphStore>(&self, store: &G) -> GraphStoreResult<GraphPostingList> {
48        let simplified = simplify(&self.path)
49            .map_err(|error| GraphStoreError::InvalidQuery(error.to_string()))?;
50        let nfa = build_nfa(&simplified)
51            .map_err(|error| GraphStoreError::InvalidQuery(error.to_string()))?;
52        let dfa = subset_construction(&nfa)
53            .map_err(|error| GraphStoreError::InvalidQuery(error.to_string()))?;
54
55        let starts: Vec<VertexId> = match self.start_vertex {
56            Some(v) => {
57                store.require_vertex_in_graph(v, self.graph)?;
58                vec![v]
59            }
60            None => store.vertex_ids_in_graph(self.graph)?.into_iter().collect(),
61        };
62
63        let mut pairs: BTreeSet<(VertexId, VertexId)> = BTreeSet::new();
64        for sv in &starts {
65            self.simulate_from(store, *sv, &dfa, &mut pairs)?;
66        }
67
68        let mut entries: Vec<PostingEntry> = Vec::new();
69        let mut graph_payloads: BTreeMap<DocId, GraphPayload> = BTreeMap::new();
70        let mut seen: BTreeSet<DocId> = BTreeSet::new();
71        for (start_v, end_v) in &pairs {
72            let doc_id = *end_v;
73            if seen.insert(doc_id) {
74                entries.push(PostingEntry::new(doc_id, Payload::with_score(self.score)));
75                let mut subgraph_vertices = vec![*start_v, *end_v];
76                subgraph_vertices.sort_unstable();
77                subgraph_vertices.dedup();
78                graph_payloads.insert(
79                    doc_id,
80                    GraphPayload {
81                        subgraph_vertices,
82                        subgraph_edges: Vec::new(),
83                        graph_name: self.graph.to_string(),
84                        score_override: Some(self.score),
85                    },
86                );
87            }
88        }
89        entries.sort_by_key(|e| e.doc_id);
90        GraphPostingList::try_from_parts(
91            PostingList::from_sorted_unchecked(entries),
92            graph_payloads,
93        )
94        .map_err(Into::into)
95    }
96
97    fn simulate_from<G: GraphStore>(
98        &self,
99        store: &G,
100        start: VertexId,
101        dfa: &Dfa,
102        pairs: &mut BTreeSet<(VertexId, VertexId)>,
103    ) -> GraphStoreResult<()> {
104        let mut visited: BTreeSet<(VertexId, DfaState)> = BTreeSet::new();
105        let mut queue: VecDeque<(VertexId, DfaState)> = VecDeque::new();
106        queue.push_back((start, dfa.start.clone()));
107        visited.insert((start, dfa.start.clone()));
108
109        if dfa.accepts.contains(&dfa.start) {
110            pairs.insert((start, start));
111        }
112
113        while let Some((vertex, state)) = queue.pop_front() {
114            let Some(transitions) = dfa.transitions.get(&state) else {
115                continue;
116            };
117            for eid in store.out_edge_ids(vertex, self.graph)? {
118                let edge = store.get_edge(eid).ok_or_else(|| {
119                    GraphStoreError::CorruptGraph(format!("missing RPQ edge {eid}"))
120                })?;
121                let Some(next_state) = transitions.get(&edge.label) else {
122                    continue;
123                };
124                let neighbor = edge.target_id;
125                if dfa.accepts.contains(next_state) {
126                    pairs.insert((start, neighbor));
127                }
128                let key = (neighbor, next_state.clone());
129                if visited.insert(key.clone()) {
130                    queue.push_back(key);
131                }
132            }
133        }
134        Ok(())
135    }
136}
uqa_graph/operators/regular_path.rs

uqa_graph/operators/
regular_path.rs
