uqa_graph/operators/
gmatch.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Constraint-pruned subgraph-isomorphism matching.
8
9use super::{
10    graph_id_value, synthetic_doc_id, BTreeMap, BTreeSet, DocId, Edge, EdgeId, EdgePattern,
11    GraphPattern, GraphPayload, GraphPostingList, GraphStore, GraphStoreError, GraphStoreResult,
12    Payload, PostingEntry, PostingList, VertexId, DEFAULT_GRAPH_SCORE,
13};
14
15/// Backtracking working set: which variables remain to be bound, the
16/// current partial assignment, the set of already-bound vertex ids, and
17/// the accumulator for completed matches.
18struct BacktrackState {
19    unassigned: BTreeSet<String>,
20    assignment: BTreeMap<String, VertexId>,
21    assigned_values: BTreeSet<VertexId>,
22    matches: Vec<BTreeMap<String, VertexId>>,
23}
24
25/// `GMatch_P` (Definition 2.2.2 / 5.2.2): subgraph-isomorphism pattern
26/// matching via backtracking with arc-consistency candidate pruning,
27/// MRV (minimum remaining values) variable ordering, and a negated-edge
28/// post-filter. Each match maps each pattern variable to a vertex id;
29/// the result is a `GraphPostingList` keyed on a synthetic 1-based
30/// match id, with the assignment carried as payload fields.
31pub struct GMatch<'a> {
32    pub pattern: GraphPattern,
33    pub graph: &'a str,
34    pub score: f64,
35}
36
37impl<'a> GMatch<'a> {
38    pub fn new(pattern: GraphPattern, graph: &'a str) -> Self {
39        Self {
40            pattern,
41            graph,
42            score: DEFAULT_GRAPH_SCORE,
43        }
44    }
45
46    pub fn execute<G: GraphStore>(&self, store: &G) -> GraphStoreResult<GraphPostingList> {
47        if let Some(result) = self.try_execute_single_edge(store)? {
48            return Ok(result);
49        }
50        if let Some(result) = self.try_execute_two_edge_path(store)? {
51            return Ok(result);
52        }
53
54        let candidates = self.compute_candidates(store)?;
55
56        let (positive_edges, negated_edges): (Vec<&EdgePattern>, Vec<&EdgePattern>) =
57            self.pattern.edge_patterns.iter().partition(|e| !e.negated);
58
59        let mut var_edges: BTreeMap<String, Vec<&EdgePattern>> = BTreeMap::new();
60        for ep in &positive_edges {
61            var_edges.entry(ep.source_var.clone()).or_default().push(ep);
62            var_edges.entry(ep.target_var.clone()).or_default().push(ep);
63        }
64
65        let variables: Vec<String> = self
66            .pattern
67            .vertex_patterns
68            .iter()
69            .map(|vp| vp.variable.clone())
70            .collect();
71        let mut state = BacktrackState {
72            unassigned: variables.iter().cloned().collect(),
73            assignment: BTreeMap::new(),
74            assigned_values: BTreeSet::new(),
75            matches: Vec::new(),
76        };
77        self.backtrack(store, &candidates, &var_edges, &mut state)?;
78        let mut matches = state.matches;
79
80        if !negated_edges.is_empty() {
81            let mut retained = Vec::with_capacity(matches.len());
82            for assignment in matches {
83                if Self::check_negated(store, self.graph, &negated_edges, &assignment)? {
84                    retained.push(assignment);
85                }
86            }
87            matches = retained;
88        }
89
90        let mut entries: Vec<PostingEntry> = Vec::with_capacity(matches.len());
91        let mut graph_payloads: BTreeMap<DocId, GraphPayload> = BTreeMap::new();
92        for (i, m) in matches.iter().enumerate() {
93            let doc_id = synthetic_doc_id(i, "GMatch")?;
94            let mut fields = BTreeMap::new();
95            for (var, vid) in m {
96                fields.insert(var.clone(), graph_id_value(*vid, "GMatch assignment")?);
97            }
98            entries.push(PostingEntry::new(
99                doc_id,
100                Payload {
101                    positions: Vec::new(),
102                    score: self.score,
103                    fields,
104                },
105            ));
106            let mut subgraph_vertices: Vec<VertexId> = m.values().copied().collect();
107            subgraph_vertices.sort_unstable();
108            subgraph_vertices.dedup();
109            let subgraph_edges = Self::collect_match_edges(store, self.graph, &positive_edges, m)?;
110            graph_payloads.insert(
111                doc_id,
112                GraphPayload {
113                    subgraph_vertices,
114                    subgraph_edges,
115                    graph_name: self.graph.to_string(),
116                    score_override: Some(self.score),
117                },
118            );
119        }
120        GraphPostingList::try_from_parts(
121            PostingList::from_sorted_unchecked(entries),
122            graph_payloads,
123        )
124        .map_err(Into::into)
125    }
126
127    fn try_execute_single_edge<G: GraphStore>(
128        &self,
129        store: &G,
130    ) -> GraphStoreResult<Option<GraphPostingList>> {
131        if self.pattern.vertex_patterns.len() != 2 || self.pattern.edge_patterns.len() != 1 {
132            return Ok(None);
133        }
134        let edge_pattern = &self.pattern.edge_patterns[0];
135        if edge_pattern.negated || edge_pattern.source_var == edge_pattern.target_var {
136            return Ok(None);
137        }
138        let Some(source_pattern) = self.vertex_pattern(&edge_pattern.source_var) else {
139            return Ok(None);
140        };
141        let Some(target_pattern) = self.vertex_pattern(&edge_pattern.target_var) else {
142            return Ok(None);
143        };
144        let edge_list = self.edge_list_for_pattern(store, edge_pattern)?;
145
146        let mut seen_assignments: BTreeSet<(VertexId, VertexId)> = BTreeSet::new();
147        let mut entries: Vec<PostingEntry> = Vec::new();
148        let mut graph_payloads: BTreeMap<DocId, GraphPayload> = BTreeMap::new();
149        for edge in edge_list {
150            if !edge_pattern.satisfies(&edge) {
151                continue;
152            }
153            let source = store.get_vertex(edge.source_id).ok_or_else(|| {
154                GraphStoreError::CorruptGraph(format!(
155                    "edge {} references missing source vertex {}",
156                    edge.edge_id, edge.source_id
157                ))
158            })?;
159            if !source_pattern.satisfies(source) {
160                continue;
161            }
162            let target = store.get_vertex(edge.target_id).ok_or_else(|| {
163                GraphStoreError::CorruptGraph(format!(
164                    "edge {} references missing target vertex {}",
165                    edge.edge_id, edge.target_id
166                ))
167            })?;
168            if !target_pattern.satisfies(target) {
169                continue;
170            }
171            if !seen_assignments.insert((edge.source_id, edge.target_id)) {
172                continue;
173            }
174
175            let doc_id = synthetic_doc_id(entries.len(), "single-edge GMatch")?;
176            let mut fields = BTreeMap::new();
177            fields.insert(
178                edge_pattern.source_var.clone(),
179                graph_id_value(edge.source_id, "GMatch source")?,
180            );
181            fields.insert(
182                edge_pattern.target_var.clone(),
183                graph_id_value(edge.target_id, "GMatch target")?,
184            );
185            entries.push(PostingEntry::new(
186                doc_id,
187                Payload {
188                    positions: Vec::new(),
189                    score: self.score,
190                    fields,
191                },
192            ));
193            let mut subgraph_vertices = vec![edge.source_id, edge.target_id];
194            subgraph_vertices.sort_unstable();
195            subgraph_vertices.dedup();
196            graph_payloads.insert(
197                doc_id,
198                GraphPayload {
199                    subgraph_vertices,
200                    subgraph_edges: vec![edge.edge_id],
201                    graph_name: self.graph.to_string(),
202                    score_override: Some(self.score),
203                },
204            );
205        }
206
207        Ok(Some(GraphPostingList::try_from_parts(
208            PostingList::from_sorted_unchecked(entries),
209            graph_payloads,
210        )?))
211    }
212
213    fn try_execute_two_edge_path<G: GraphStore>(
214        &self,
215        store: &G,
216    ) -> GraphStoreResult<Option<GraphPostingList>> {
217        if self.pattern.vertex_patterns.len() != 3 || self.pattern.edge_patterns.len() != 2 {
218            return Ok(None);
219        }
220        let edge_patterns = &self.pattern.edge_patterns;
221        if edge_patterns.iter().any(|edge| edge.negated) {
222            return Ok(None);
223        }
224        let (first, second) = if edge_patterns[0].target_var == edge_patterns[1].source_var {
225            (&edge_patterns[0], &edge_patterns[1])
226        } else if edge_patterns[1].target_var == edge_patterns[0].source_var {
227            (&edge_patterns[1], &edge_patterns[0])
228        } else {
229            return Ok(None);
230        };
231        if first.source_var == first.target_var
232            || second.source_var == second.target_var
233            || first.source_var == second.target_var
234        {
235            return Ok(None);
236        }
237        let Some(source_pattern) = self.vertex_pattern(&first.source_var) else {
238            return Ok(None);
239        };
240        let Some(middle_pattern) = self.vertex_pattern(&first.target_var) else {
241            return Ok(None);
242        };
243        let Some(target_pattern) = self.vertex_pattern(&second.target_var) else {
244            return Ok(None);
245        };
246
247        let first_edges = self.edge_list_for_pattern(store, first)?;
248        let mut seen_assignments: BTreeSet<(VertexId, VertexId, VertexId)> = BTreeSet::new();
249        let mut entries: Vec<PostingEntry> = Vec::new();
250        let mut graph_payloads: BTreeMap<DocId, GraphPayload> = BTreeMap::new();
251
252        for first_edge in first_edges {
253            if !first.satisfies(&first_edge) {
254                continue;
255            }
256            let source = store.get_vertex(first_edge.source_id).ok_or_else(|| {
257                GraphStoreError::CorruptGraph(format!(
258                    "edge {} references missing source vertex {}",
259                    first_edge.edge_id, first_edge.source_id
260                ))
261            })?;
262            if !source_pattern.satisfies(source) {
263                continue;
264            }
265            let middle = store.get_vertex(first_edge.target_id).ok_or_else(|| {
266                GraphStoreError::CorruptGraph(format!(
267                    "edge {} references missing middle vertex {}",
268                    first_edge.edge_id, first_edge.target_id
269                ))
270            })?;
271            if !middle_pattern.satisfies(middle) {
272                continue;
273            }
274
275            for second_edge_id in store.out_edge_ids(first_edge.target_id, self.graph)? {
276                let second_edge = store.get_edge(second_edge_id).ok_or_else(|| {
277                    GraphStoreError::CorruptGraph(format!("missing path edge {second_edge_id}"))
278                })?;
279                if !second.satisfies(second_edge) {
280                    continue;
281                }
282                if first_edge.source_id == second_edge.target_id
283                    || first_edge.target_id == second_edge.target_id
284                {
285                    continue;
286                }
287                let target = store.get_vertex(second_edge.target_id).ok_or_else(|| {
288                    GraphStoreError::CorruptGraph(format!(
289                        "edge {} references missing target vertex {}",
290                        second_edge.edge_id, second_edge.target_id
291                    ))
292                })?;
293                if !target_pattern.satisfies(target) {
294                    continue;
295                }
296                let assignment = (
297                    first_edge.source_id,
298                    first_edge.target_id,
299                    second_edge.target_id,
300                );
301                if !seen_assignments.insert(assignment) {
302                    continue;
303                }
304                self.push_two_edge_path_match(
305                    first,
306                    second,
307                    &first_edge,
308                    second_edge,
309                    &mut entries,
310                    &mut graph_payloads,
311                )?;
312            }
313        }
314
315        Ok(Some(GraphPostingList::try_from_parts(
316            PostingList::from_sorted_unchecked(entries),
317            graph_payloads,
318        )?))
319    }
320
321    fn push_two_edge_path_match(
322        &self,
323        first: &EdgePattern,
324        second: &EdgePattern,
325        first_edge: &Edge,
326        second_edge: &Edge,
327        entries: &mut Vec<PostingEntry>,
328        graph_payloads: &mut BTreeMap<DocId, GraphPayload>,
329    ) -> GraphStoreResult<()> {
330        let doc_id = synthetic_doc_id(entries.len(), "two-edge GMatch")?;
331        let mut fields = BTreeMap::new();
332        fields.insert(
333            first.source_var.clone(),
334            graph_id_value(first_edge.source_id, "GMatch source")?,
335        );
336        fields.insert(
337            first.target_var.clone(),
338            graph_id_value(first_edge.target_id, "GMatch middle")?,
339        );
340        fields.insert(
341            second.target_var.clone(),
342            graph_id_value(second_edge.target_id, "GMatch target")?,
343        );
344        entries.push(PostingEntry::new(
345            doc_id,
346            Payload {
347                positions: Vec::new(),
348                score: self.score,
349                fields,
350            },
351        ));
352
353        let mut subgraph_edges = vec![first_edge.edge_id, second_edge.edge_id];
354        subgraph_edges.sort_unstable();
355        subgraph_edges.dedup();
356        let mut subgraph_vertices = vec![
357            first_edge.source_id,
358            first_edge.target_id,
359            second_edge.target_id,
360        ];
361        subgraph_vertices.sort_unstable();
362        subgraph_vertices.dedup();
363        graph_payloads.insert(
364            doc_id,
365            GraphPayload {
366                subgraph_vertices,
367                subgraph_edges,
368                graph_name: self.graph.to_string(),
369                score_override: Some(self.score),
370            },
371        );
372        Ok(())
373    }
374
375    fn edge_list_for_pattern<G: GraphStore>(
376        &self,
377        store: &G,
378        pattern: &EdgePattern,
379    ) -> GraphStoreResult<Vec<Edge>> {
380        let edge_ids = match pattern.label.as_deref() {
381            Some(label) => store.edge_ids_by_label(label, self.graph)?,
382            None => return store.edges_in_graph(self.graph),
383        };
384        edge_ids
385            .into_iter()
386            .map(|edge_id| {
387                store.get_edge(edge_id).cloned().ok_or_else(|| {
388                    GraphStoreError::CorruptGraph(format!("missing pattern edge {edge_id}"))
389                })
390            })
391            .collect()
392    }
393
394    fn vertex_pattern(&self, variable: &str) -> Option<&crate::pattern::VertexPattern> {
395        self.pattern
396            .vertex_patterns
397            .iter()
398            .find(|pattern| pattern.variable == variable)
399    }
400
401    fn compute_candidates<G: GraphStore>(
402        &self,
403        store: &G,
404    ) -> GraphStoreResult<BTreeMap<String, Vec<VertexId>>> {
405        let mut candidates: BTreeMap<String, Vec<VertexId>> = BTreeMap::new();
406        let graph_vids = store.vertex_ids_in_graph(self.graph)?;
407        for vp in &self.pattern.vertex_patterns {
408            let mut cands = Vec::new();
409            for vid in &graph_vids {
410                let vtx = store.get_vertex(*vid).ok_or_else(|| {
411                    GraphStoreError::CorruptGraph(format!("missing candidate vertex {vid}"))
412                })?;
413                if vp.satisfies(vtx) {
414                    cands.push(*vid);
415                }
416            }
417            candidates.insert(vp.variable.clone(), cands);
418        }
419
420        // Arc consistency pass — skip negated edges (post-filtered).
421        let mut changed = true;
422        while changed {
423            changed = false;
424            for ep in &self.pattern.edge_patterns {
425                if ep.negated {
426                    continue;
427                }
428                let (src_var, tgt_var) = (&ep.source_var, &ep.target_var);
429                let Some(_src_cands) = candidates.get(src_var) else {
430                    continue;
431                };
432                let Some(tgt_cands) = candidates.get(tgt_var) else {
433                    continue;
434                };
435                let tgt_set: BTreeSet<VertexId> = tgt_cands.iter().copied().collect();
436                let mut new_src = Vec::new();
437                for vid in candidates[src_var].iter().copied() {
438                    if Self::has_edge_out(store, self.graph, vid, &tgt_set, ep)? {
439                        new_src.push(vid);
440                    }
441                }
442                if new_src.len() < candidates[src_var].len() {
443                    candidates.insert(src_var.clone(), new_src);
444                    changed = true;
445                }
446                let src_set: BTreeSet<VertexId> = candidates[src_var].iter().copied().collect();
447                let mut new_tgt = Vec::new();
448                for vid in candidates[tgt_var].iter().copied() {
449                    if Self::has_edge_in(store, self.graph, vid, &src_set, ep)? {
450                        new_tgt.push(vid);
451                    }
452                }
453                if new_tgt.len() < candidates[tgt_var].len() {
454                    candidates.insert(tgt_var.clone(), new_tgt);
455                    changed = true;
456                }
457            }
458        }
459        Ok(candidates)
460    }
461
462    fn has_edge_out<G: GraphStore>(
463        store: &G,
464        graph: &str,
465        src: VertexId,
466        tgt_set: &BTreeSet<VertexId>,
467        ep: &EdgePattern,
468    ) -> GraphStoreResult<bool> {
469        for eid in store.out_edge_ids(src, graph)? {
470            let edge = store.get_edge(eid).ok_or_else(|| {
471                GraphStoreError::CorruptGraph(format!("missing pattern edge {eid}"))
472            })?;
473            if !tgt_set.contains(&edge.target_id) {
474                continue;
475            }
476            if ep.satisfies(edge) {
477                return Ok(true);
478            }
479        }
480        Ok(false)
481    }
482
483    fn has_edge_in<G: GraphStore>(
484        store: &G,
485        graph: &str,
486        tgt: VertexId,
487        src_set: &BTreeSet<VertexId>,
488        ep: &EdgePattern,
489    ) -> GraphStoreResult<bool> {
490        for eid in store.in_edge_ids(tgt, graph)? {
491            let edge = store.get_edge(eid).ok_or_else(|| {
492                GraphStoreError::CorruptGraph(format!("missing pattern edge {eid}"))
493            })?;
494            if !src_set.contains(&edge.source_id) {
495                continue;
496            }
497            if ep.satisfies(edge) {
498                return Ok(true);
499            }
500        }
501        Ok(false)
502    }
503
504    fn backtrack<G: GraphStore>(
505        &self,
506        store: &G,
507        candidates: &BTreeMap<String, Vec<VertexId>>,
508        var_edges: &BTreeMap<String, Vec<&EdgePattern>>,
509        state: &mut BacktrackState,
510    ) -> GraphStoreResult<()> {
511        if state.unassigned.is_empty() {
512            state.matches.push(state.assignment.clone());
513            return Ok(());
514        }
515        let var = state
516            .unassigned
517            .iter()
518            .min_by_key(|v| candidates.get(*v).map_or(usize::MAX, Vec::len))
519            .cloned()
520            .ok_or_else(|| {
521                GraphStoreError::CorruptGraph(
522                    "GMatch has no variable despite non-empty unassigned state".into(),
523                )
524            })?;
525        let cands = candidates.get(&var).cloned().ok_or_else(|| {
526            GraphStoreError::CorruptGraph(format!("missing candidate set for variable {var:?}"))
527        })?;
528        for vid in cands {
529            if state.assigned_values.contains(&vid) {
530                continue;
531            }
532            state.assignment.insert(var.clone(), vid);
533            state.assigned_values.insert(vid);
534            state.unassigned.remove(&var);
535            if Self::validate_edges_for(store, self.graph, &var, var_edges, &state.assignment)? {
536                self.backtrack(store, candidates, var_edges, state)?;
537            }
538            state.assignment.remove(&var);
539            state.assigned_values.remove(&vid);
540            state.unassigned.insert(var.clone());
541        }
542        Ok(())
543    }
544
545    fn validate_edges_for<G: GraphStore>(
546        store: &G,
547        graph: &str,
548        var: &str,
549        var_edges: &BTreeMap<String, Vec<&EdgePattern>>,
550        assignment: &BTreeMap<String, VertexId>,
551    ) -> GraphStoreResult<bool> {
552        let Some(edges) = var_edges.get(var) else {
553            return Ok(true);
554        };
555        for ep in edges {
556            let (Some(src_id), Some(tgt_id)) = (
557                assignment.get(&ep.source_var).copied(),
558                assignment.get(&ep.target_var).copied(),
559            ) else {
560                continue;
561            };
562            let mut found = false;
563            for eid in store.out_edge_ids(src_id, graph)? {
564                let edge = store.get_edge(eid).ok_or_else(|| {
565                    GraphStoreError::CorruptGraph(format!("missing pattern edge {eid}"))
566                })?;
567                if edge.target_id != tgt_id {
568                    continue;
569                }
570                if ep.satisfies(edge) {
571                    found = true;
572                    break;
573                }
574            }
575            if !found {
576                return Ok(false);
577            }
578        }
579        Ok(true)
580    }
581
582    fn check_negated<G: GraphStore>(
583        store: &G,
584        graph: &str,
585        negated: &[&EdgePattern],
586        assignment: &BTreeMap<String, VertexId>,
587    ) -> GraphStoreResult<bool> {
588        for ep in negated {
589            let (Some(src_id), Some(tgt_id)) = (
590                assignment.get(&ep.source_var).copied(),
591                assignment.get(&ep.target_var).copied(),
592            ) else {
593                continue;
594            };
595            for eid in store.out_edge_ids(src_id, graph)? {
596                let edge = store.get_edge(eid).ok_or_else(|| {
597                    GraphStoreError::CorruptGraph(format!("missing pattern edge {eid}"))
598                })?;
599                if edge.target_id != tgt_id {
600                    continue;
601                }
602                if ep.satisfies(edge) {
603                    return Ok(false);
604                }
605            }
606        }
607        Ok(true)
608    }
609
610    fn collect_match_edges<G: GraphStore>(
611        store: &G,
612        graph: &str,
613        positive: &[&EdgePattern],
614        assignment: &BTreeMap<String, VertexId>,
615    ) -> GraphStoreResult<Vec<EdgeId>> {
616        let mut edges: BTreeSet<EdgeId> = BTreeSet::new();
617        for ep in positive {
618            let (Some(src_id), Some(tgt_id)) = (
619                assignment.get(&ep.source_var).copied(),
620                assignment.get(&ep.target_var).copied(),
621            ) else {
622                continue;
623            };
624            for eid in store.out_edge_ids(src_id, graph)? {
625                let edge = store.get_edge(eid).ok_or_else(|| {
626                    GraphStoreError::CorruptGraph(format!("missing pattern edge {eid}"))
627                })?;
628                if edge.target_id == tgt_id && ep.satisfies(edge) {
629                    edges.insert(eid);
630                    break;
631                }
632            }
633        }
634        Ok(edges.into_iter().collect())
635    }
636}
637
638// -------------------------------------------------------------------------
639// VertexAggregation
640// -------------------------------------------------------------------------
uqa_graph/operators/gmatch.rs

uqa_graph/operators/
gmatch.rs
