Skip to main content

qualia_core_db/modalities/
graph_theory.rs

1//! Advanced graph theory analysis for NQuin graphs.
2//!
3//! This module exposes two graph-analysis tiers:
4//! - `analyze_graph_topology_bounded` is the preferred zero-heap path for 10D tensor
5//!   orchestration and edge inference. It uses fixed-capacity arrays only.
6//! - `analyze_graph_topology` is the quarantined compatibility path for bounded,
7//!   batch-style topology jobs. It still uses `HashMap`, `HashSet`, `Vec`, and
8//!   `VecDeque`, so callers must keep it off hot paths and within the input cap below.
9
10use crate::NQuin;
11use std::collections::{HashMap, HashSet};
12
13/// Heap-backed graph analysis is quarantined behind a fixed input cap so daemon
14/// callers do not accidentally fan out into unbounded topology jobs on edge nodes.
15pub const MAX_HEAP_GRAPH_ANALYSIS_QUINS: usize = 4_096;
16
17#[derive(Debug, Clone, Copy, PartialEq, Eq)]
18pub enum GraphAnalysisError {
19    InputTooLarge,
20    NodeCapacityExceeded,
21    OutputBufferFull,
22}
23
24/// Preferred zero-heap node cap for edge-safe topology analysis.
25pub const MAX_BOUNDED_GRAPH_ANALYSIS_NODES: usize = 128;
26
27#[derive(Debug, Clone, Copy, PartialEq)]
28pub struct CommunitySpan {
29    pub start: u16,
30    pub len: u16,
31}
32
33#[derive(Debug, Clone, Copy, PartialEq)]
34pub struct TopNodeScore {
35    pub node_id: u64,
36    pub centrality_score: f32,
37}
38
39#[derive(Debug, Clone, Copy, PartialEq)]
40pub struct MotifRecord {
41    pub pattern: MotifPattern,
42    pub node_a: u64,
43    pub node_b: u64,
44    pub node_c: u64,
45    pub frequency: f32,
46}
47
48/// Maximum number of nodes in a subgraph-isomorphism query pattern. Bounding the
49/// pattern keeps the backtracking search depth (and therefore the stack) fixed.
50pub const MAX_SUBGRAPH_PATTERN_NODES: usize = 8;
51
52/// A directed query pattern for subgraph isomorphism. `adjacency[i][j] != 0`
53/// requires a data-graph edge from the node mapped to pattern node `i` to the
54/// node mapped to pattern node `j`. Only the first `node_count` rows/cols are read.
55#[derive(Debug, Clone, Copy)]
56pub struct SubgraphPattern {
57    pub adjacency: [[u8; MAX_SUBGRAPH_PATTERN_NODES]; MAX_SUBGRAPH_PATTERN_NODES],
58    pub node_count: usize,
59}
60
61impl SubgraphPattern {
62    /// Build an empty (edgeless) pattern of `node_count` nodes.
63    pub fn new(node_count: usize) -> Self {
64        Self {
65            adjacency: [[0; MAX_SUBGRAPH_PATTERN_NODES]; MAX_SUBGRAPH_PATTERN_NODES],
66            node_count: node_count.min(MAX_SUBGRAPH_PATTERN_NODES),
67        }
68    }
69
70    /// Add a required directed edge `from -> to` to the pattern.
71    pub fn with_edge(mut self, from: usize, to: usize) -> Self {
72        if from < self.node_count && to < self.node_count {
73            self.adjacency[from][to] = 1;
74        }
75        self
76    }
77}
78
79/// One subgraph-isomorphism match: the data-graph node ids assigned to pattern
80/// nodes `0..len`. `missing_edges` is 0 for an exact (induced-monomorphism)
81/// match and counts unsatisfied pattern edges for an approximate match.
82#[derive(Debug, Clone, Copy, PartialEq)]
83pub struct SubgraphMatch {
84    pub mapping: [u64; MAX_SUBGRAPH_PATTERN_NODES],
85    pub len: u16,
86    pub missing_edges: u8,
87}
88
89#[derive(Debug, Clone, Copy, PartialEq)]
90pub struct BoundedGraphAnalysisSummary {
91    pub density: f32,
92    pub node_count: u16,
93    pub edge_count: u16,
94    pub community_count: u16,
95    pub motif_count: u16,
96    pub top_node_count: u16,
97    pub graph_quin_count: u16,
98}
99
100#[derive(Debug, Clone)]
101struct BoundedQualiaGraph {
102    node_ids: [u64; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
103    centrality_scores: [f32; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
104    degrees: [u16; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
105    adjacency: [[u8; MAX_BOUNDED_GRAPH_ANALYSIS_NODES]; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
106    node_count: usize,
107    edge_count: usize,
108}
109
110impl BoundedQualiaGraph {
111    /// Build the bounded adjacency-matrix graph from `quins`: each quin's
112    /// `subject`→`object` becomes a directed edge (deduplicated, in-degree
113    /// counted on the source), with node ids in first-seen order.
114    /// `NodeCapacityExceeded` when distinct nodes exceed
115    /// `MAX_BOUNDED_GRAPH_ANALYSIS_NODES`. All state is stack arrays — no
116    /// heap, per the Tier-1 contract.
117    fn from_quins(quins: &[NQuin]) -> Result<Self, GraphAnalysisError> {
118        let mut graph = Self {
119            node_ids: [0; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
120            centrality_scores: [0.0; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
121            degrees: [0; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
122            adjacency: [[0; MAX_BOUNDED_GRAPH_ANALYSIS_NODES]; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
123            node_count: 0,
124            edge_count: 0,
125        };
126
127        for quin in quins {
128            let source = graph.get_or_insert_node(quin.subject)?;
129            let target = graph.get_or_insert_node(quin.object)?;
130            if graph.adjacency[source][target] == 0 {
131                graph.adjacency[source][target] = 1;
132                graph.degrees[source] = graph.degrees[source].saturating_add(1);
133                graph.edge_count += 1;
134            }
135        }
136
137        Ok(graph)
138    }
139
140    /// Map `node_id` to its dense index, inserting it if unseen. Linear
141    /// scan over `node_count` — O(n²) total for `from_quins`, acceptable
142    /// at the bounded node cap. `NodeCapacityExceeded` when full.
143    fn get_or_insert_node(&mut self, node_id: u64) -> Result<usize, GraphAnalysisError> {
144        for index in 0..self.node_count {
145            if self.node_ids[index] == node_id {
146                return Ok(index);
147            }
148        }
149
150        if self.node_count >= MAX_BOUNDED_GRAPH_ANALYSIS_NODES {
151            return Err(GraphAnalysisError::NodeCapacityExceeded);
152        }
153
154        let index = self.node_count;
155        self.node_ids[index] = node_id;
156        self.node_count += 1;
157        Ok(index)
158    }
159
160    /// Brandes' unweighted betweenness centrality, normalized by
161    /// `(n-1)(n-2)` for n > 2. Per-source BFS accumulation using
162    /// fixed-size sigma/distance/delta/queue/stack arrays — no
163    /// recursion, no heap.
164    fn calculate_betweenness_centrality(&mut self) {
165        let n = self.node_count;
166        if n < 2 {
167            return;
168        }
169
170        let mut scores = [0f32; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
171        let mut sigma = [0f32; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
172        let mut dist = [-1i16; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
173        let mut delta = [0f32; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
174        let mut queue = [0usize; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
175        let mut stack = [0usize; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
176
177        for source in 0..n {
178            sigma[..n].fill(0.0);
179            dist[..n].fill(-1);
180            delta[..n].fill(0.0);
181
182            let mut queue_head = 0usize;
183            let mut queue_tail = 0usize;
184            let mut stack_len = 0usize;
185
186            sigma[source] = 1.0;
187            dist[source] = 0;
188            queue[queue_tail] = source;
189            queue_tail += 1;
190
191            while queue_head < queue_tail {
192                let v = queue[queue_head];
193                queue_head += 1;
194                stack[stack_len] = v;
195                stack_len += 1;
196
197                for w in 0..n {
198                    if self.adjacency[v][w] == 0 {
199                        continue;
200                    }
201                    if dist[w] < 0 {
202                        dist[w] = dist[v] + 1;
203                        queue[queue_tail] = w;
204                        queue_tail += 1;
205                    }
206                    if dist[w] == dist[v] + 1 {
207                        sigma[w] += sigma[v];
208                    }
209                }
210            }
211
212            while stack_len > 0 {
213                stack_len -= 1;
214                let w = stack[stack_len];
215                for v in 0..n {
216                    if self.adjacency[v][w] == 0 || dist[v] != dist[w] - 1 || sigma[w] == 0.0 {
217                        continue;
218                    }
219                    delta[v] += (sigma[v] / sigma[w]) * (1.0 + delta[w]);
220                }
221                if w != source {
222                    scores[w] += delta[w];
223                }
224            }
225        }
226
227        let norm = if n > 2 {
228            ((n - 1) * (n - 2)) as f32
229        } else {
230            1.0
231        };
232        for (index, score) in scores.iter().take(n).enumerate() {
233            self.centrality_scores[index] = if norm > 0.0 { *score / norm } else { *score };
234        }
235    }
236
237    /// Directed-edge density `E / (N·(N-1))`; `0.0` for fewer than two
238    /// nodes.
239    fn density(&self) -> f32 {
240        if self.node_count < 2 {
241            return 0.0;
242        }
243        let possible_edges = (self.node_count * (self.node_count - 1)) as f32;
244        self.edge_count as f32 / possible_edges
245    }
246
247    /// Weakly-connected components via iterative DFS (either-direction
248    /// adjacency). Emits each component's node ids contiguously into
249    /// `community_nodes_out` with its `(start, len)` span in
250    /// `community_spans_out`; returns the community count or
251    /// `OutputBufferFull` when either buffer is too small.
252    fn write_communities(
253        &self,
254        community_nodes_out: &mut [u64],
255        community_spans_out: &mut [CommunitySpan],
256    ) -> Result<usize, GraphAnalysisError> {
257        let mut visited = [false; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
258        let mut stack = [0usize; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
259        let mut nodes_written = 0usize;
260        let mut communities_written = 0usize;
261
262        for start in 0..self.node_count {
263            if visited[start] {
264                continue;
265            }
266            if communities_written >= community_spans_out.len() {
267                return Err(GraphAnalysisError::OutputBufferFull);
268            }
269            let span_start = nodes_written;
270            let mut stack_len = 0usize;
271            stack[stack_len] = start;
272            stack_len += 1;
273            visited[start] = true;
274
275            while stack_len > 0 {
276                stack_len -= 1;
277                let node = stack[stack_len];
278                if nodes_written >= community_nodes_out.len() {
279                    return Err(GraphAnalysisError::OutputBufferFull);
280                }
281                community_nodes_out[nodes_written] = self.node_ids[node];
282                nodes_written += 1;
283
284                for neighbor in 0..self.node_count {
285                    let linked =
286                        self.adjacency[node][neighbor] != 0 || self.adjacency[neighbor][node] != 0;
287                    if linked && !visited[neighbor] {
288                        visited[neighbor] = true;
289                        stack[stack_len] = neighbor;
290                        stack_len += 1;
291                    }
292                }
293            }
294
295            community_spans_out[communities_written] = CommunitySpan {
296                start: span_start as u16,
297                len: (nodes_written - span_start) as u16,
298            };
299            communities_written += 1;
300        }
301
302        Ok(communities_written)
303    }
304
305    /// Enumerate directed 3-cycles (a→b→c→a), deduplicated by sorted
306    /// node-id triple so each triangle is emitted once regardless of
307    /// rotation. Returns the motif count or `OutputBufferFull`.
308    fn write_motifs(&self, motifs_out: &mut [MotifRecord]) -> Result<usize, GraphAnalysisError> {
309        let mut written = 0usize;
310
311        for a in 0..self.node_count {
312            for b in 0..self.node_count {
313                if self.adjacency[a][b] == 0 {
314                    continue;
315                }
316                for c in 0..self.node_count {
317                    if c == a || self.adjacency[b][c] == 0 || self.adjacency[c][a] == 0 {
318                        continue;
319                    }
320
321                    let mut canonical = [self.node_ids[a], self.node_ids[b], self.node_ids[c]];
322                    canonical.sort_unstable();
323                    if motifs_out[..written].iter().any(|m| {
324                        let mut existing = [m.node_a, m.node_b, m.node_c];
325                        existing.sort_unstable();
326                        existing == canonical
327                    }) {
328                        continue;
329                    }
330
331                    if written >= motifs_out.len() {
332                        return Err(GraphAnalysisError::OutputBufferFull);
333                    }
334                    motifs_out[written] = MotifRecord {
335                        pattern: MotifPattern::Triangle,
336                        node_a: self.node_ids[a],
337                        node_b: self.node_ids[b],
338                        node_c: self.node_ids[c],
339                        frequency: 1.0,
340                    };
341                    written += 1;
342                }
343            }
344        }
345
346        Ok(written)
347    }
348
349    /// Copy the `min(out.len(), node_count)` highest betweenness scores,
350    /// descending. Returns the count written.
351    fn write_top_nodes(&self, out: &mut [TopNodeScore]) -> usize {
352        let count = out.len().min(self.node_count);
353        if count == 0 {
354            return 0;
355        }
356
357        let mut scratch = [TopNodeScore {
358            node_id: 0,
359            centrality_score: f32::MIN,
360        }; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
361        for i in 0..self.node_count {
362            scratch[i] = TopNodeScore {
363                node_id: self.node_ids[i],
364                centrality_score: self.centrality_scores[i],
365            };
366        }
367        scratch[..self.node_count].sort_by(|a, b| {
368            b.centrality_score
369                .partial_cmp(&a.centrality_score)
370                .unwrap_or(std::cmp::Ordering::Equal)
371        });
372        out[..count].copy_from_slice(&scratch[..count]);
373        count
374    }
375
376    /// Emit one `NQuin` per node encoding its centrality (`has_centrality_score`
377    /// predicate, object = score × 1000 as u64, node degree in metadata)
378    /// under `context`. `out` must hold ≥ `node_count`; returns the count
379    /// written or `OutputBufferFull`.
380    fn write_graph_quins(
381        &self,
382        context: u64,
383        out: &mut [NQuin],
384    ) -> Result<usize, GraphAnalysisError> {
385        if out.len() < self.node_count {
386            return Err(GraphAnalysisError::OutputBufferFull);
387        }
388
389        for i in 0..self.node_count {
390            let mut quin = NQuin {
391                subject: self.node_ids[i],
392                predicate: crate::q_hash("has_centrality_score"),
393                object: (self.centrality_scores[i] as f64 * 1000.0) as u64,
394                context,
395                metadata: self.degrees[i] as u64,
396                parity: 0,
397            };
398            quin.parity = quin.subject ^ quin.predicate ^ quin.object ^ quin.context;
399            out[i] = quin;
400        }
401
402        Ok(self.node_count)
403    }
404
405    /// Zero-heap PageRank via power iteration over the bounded adjacency matrix.
406    ///
407    /// Google PageRank: `PR(v) = (1-d)/N + d·Σ_{u→v} PR(u)/outdeg(u)`, with the
408    /// mass held by dangling (out-degree-0) nodes redistributed uniformly so the
409    /// vector stays a probability distribution. Iterates until the L1 delta drops
410    /// below `tolerance` or `max_iters` is reached. Writes `min(out.len(), n)`
411    /// scores aligned to `self.node_ids` order and returns that count.
412    fn calculate_pagerank(
413        &self,
414        damping: f32,
415        max_iters: u32,
416        tolerance: f32,
417        out: &mut [f32],
418    ) -> usize {
419        let n = self.node_count;
420        if n == 0 {
421            return 0;
422        }
423        let count = out.len().min(n);
424
425        let mut rank = [0f32; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
426        let mut next = [0f32; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
427        let mut outdeg = [0u16; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
428
429        let init = 1.0 / n as f32;
430        rank[..n].fill(init);
431        for v in 0..n {
432            let mut d = 0u16;
433            for w in 0..n {
434                if self.adjacency[v][w] != 0 {
435                    d += 1;
436                }
437            }
438            outdeg[v] = d;
439        }
440
441        let base = (1.0 - damping) / n as f32;
442        for _ in 0..max_iters {
443            let mut dangling = 0f32;
444            for v in 0..n {
445                if outdeg[v] == 0 {
446                    dangling += rank[v];
447                }
448            }
449            let dangling_share = damping * dangling / n as f32;
450            next[..n].fill(base + dangling_share);
451
452            for v in 0..n {
453                if outdeg[v] == 0 {
454                    continue;
455                }
456                let share = damping * rank[v] / outdeg[v] as f32;
457                for w in 0..n {
458                    if self.adjacency[v][w] != 0 {
459                        next[w] += share;
460                    }
461                }
462            }
463
464            let mut delta = 0f32;
465            for v in 0..n {
466                delta += (next[v] - rank[v]).abs();
467                rank[v] = next[v];
468            }
469            if delta < tolerance {
470                break;
471            }
472        }
473
474        out[..count].copy_from_slice(&rank[..count]);
475        count
476    }
477
478    /// Exact / approximate subgraph isomorphism by bounded backtracking search.
479    ///
480    /// Finds injective mappings of the query `pattern` onto the data graph such
481    /// that every required pattern edge maps to a data edge (a directed
482    /// monomorphism). With `max_missing_edges > 0` the search also reports
483    /// approximate matches that miss up to that many required edges (recorded in
484    /// `SubgraphMatch::missing_edges`). Recursion depth is bounded by the pattern
485    /// size, so the call uses only fixed-size stack frames — no heap.
486    fn find_subgraph_isomorphisms(
487        &self,
488        pattern: &SubgraphPattern,
489        max_missing_edges: u8,
490        out: &mut [SubgraphMatch],
491    ) -> usize {
492        if pattern.node_count == 0
493            || pattern.node_count > MAX_SUBGRAPH_PATTERN_NODES
494            || pattern.node_count > self.node_count
495            || out.is_empty()
496        {
497            return 0;
498        }
499        let mut assign = [0usize; MAX_SUBGRAPH_PATTERN_NODES];
500        let mut used = [false; MAX_BOUNDED_GRAPH_ANALYSIS_NODES];
501        let mut written = 0usize;
502        self.match_subgraph(
503            pattern,
504            0,
505            0,
506            max_missing_edges,
507            &mut assign,
508            &mut used,
509            out,
510            &mut written,
511        );
512        written
513    }
514
515    /// Backtracking subgraph-isomorphism worker: assigns pattern node
516    /// `depth` to an unused graph node consistent with edges to
517    /// already-assigned nodes, tolerating up to `max_missing_edges`
518    /// absent edges (approximate matching). Stops when `out` is full.
519    /// Bounded by `MAX_SUBGRAPH_PATTERN_NODES` depth — iterative-ish
520    /// recursion over a tiny pattern cap, fixed scratch arrays only.
521    #[allow(clippy::too_many_arguments)]
522    fn match_subgraph(
523        &self,
524        pattern: &SubgraphPattern,
525        depth: usize,
526        missing: u8,
527        max_missing_edges: u8,
528        assign: &mut [usize; MAX_SUBGRAPH_PATTERN_NODES],
529        used: &mut [bool; MAX_BOUNDED_GRAPH_ANALYSIS_NODES],
530        out: &mut [SubgraphMatch],
531        written: &mut usize,
532    ) {
533        if *written >= out.len() {
534            return;
535        }
536        if depth == pattern.node_count {
537            let mut m = SubgraphMatch {
538                mapping: [0; MAX_SUBGRAPH_PATTERN_NODES],
539                len: pattern.node_count as u16,
540                missing_edges: missing,
541            };
542            for (p, slot) in m.mapping.iter_mut().take(pattern.node_count).enumerate() {
543                *slot = self.node_ids[assign[p]];
544            }
545            out[*written] = m;
546            *written += 1;
547            return;
548        }
549
550        for candidate in 0..self.node_count {
551            if used[candidate] {
552                continue;
553            }
554            // Edge-consistency against already-assigned pattern nodes.
555            let mut local_missing = 0u8;
556            for prev in 0..depth {
557                let pd = assign[prev];
558                if pattern.adjacency[prev][depth] != 0 && self.adjacency[pd][candidate] == 0 {
559                    local_missing += 1;
560                }
561                if pattern.adjacency[depth][prev] != 0 && self.adjacency[candidate][pd] == 0 {
562                    local_missing += 1;
563                }
564            }
565            if missing + local_missing > max_missing_edges {
566                continue;
567            }
568            assign[depth] = candidate;
569            used[candidate] = true;
570            self.match_subgraph(
571                pattern,
572                depth + 1,
573                missing + local_missing,
574                max_missing_edges,
575                assign,
576                used,
577                out,
578                written,
579            );
580            used[candidate] = false;
581            if *written >= out.len() {
582                return;
583            }
584        }
585    }
586}
587
588/// Zero-heap topology analysis aligned with the 10D tensor hot-path constraints.
589pub fn analyze_graph_topology_bounded(
590    quins: &[NQuin],
591    context: u64,
592    graph_quins_out: &mut [NQuin],
593    community_nodes_out: &mut [u64],
594    community_spans_out: &mut [CommunitySpan],
595    motifs_out: &mut [MotifRecord],
596    top_nodes_out: &mut [TopNodeScore],
597) -> Result<BoundedGraphAnalysisSummary, GraphAnalysisError> {
598    if quins.len() > MAX_HEAP_GRAPH_ANALYSIS_QUINS {
599        return Err(GraphAnalysisError::InputTooLarge);
600    }
601
602    let mut graph = BoundedQualiaGraph::from_quins(quins)?;
603    graph.calculate_betweenness_centrality();
604
605    let graph_quin_count = graph.write_graph_quins(context, graph_quins_out)?;
606    let community_count = graph.write_communities(community_nodes_out, community_spans_out)?;
607    let motif_count = graph.write_motifs(motifs_out)?;
608    let top_node_count = graph.write_top_nodes(top_nodes_out);
609
610    Ok(BoundedGraphAnalysisSummary {
611        density: graph.density(),
612        node_count: graph.node_count as u16,
613        edge_count: graph.edge_count as u16,
614        community_count: community_count as u16,
615        motif_count: motif_count as u16,
616        top_node_count: top_node_count as u16,
617        graph_quin_count: graph_quin_count as u16,
618    })
619}
620
621/// Zero-heap PageRank over an NQuin relation set (bounded path).
622///
623/// Builds the bounded adjacency from `quins`, runs power iteration with the given
624/// `damping` (typically 0.85), and writes node scores into `scores_out` aligned
625/// with first-seen subject/object order. Returns the number of scores written.
626/// `max_iters`/`tolerance` bound the iteration (e.g. 100 / 1e-6).
627pub fn pagerank_bounded(
628    quins: &[NQuin],
629    damping: f32,
630    max_iters: u32,
631    tolerance: f32,
632    node_ids_out: &mut [u64],
633    scores_out: &mut [f32],
634) -> Result<usize, GraphAnalysisError> {
635    if quins.len() > MAX_HEAP_GRAPH_ANALYSIS_QUINS {
636        return Err(GraphAnalysisError::InputTooLarge);
637    }
638    let graph = BoundedQualiaGraph::from_quins(quins)?;
639    let count = graph.calculate_pagerank(damping, max_iters, tolerance, scores_out);
640    if node_ids_out.len() < count {
641        return Err(GraphAnalysisError::OutputBufferFull);
642    }
643    node_ids_out[..count].copy_from_slice(&graph.node_ids[..count]);
644    Ok(count)
645}
646
647/// Zero-heap exact/approximate subgraph isomorphism over an NQuin relation set.
648///
649/// `max_missing_edges == 0` requires an exact directed monomorphism; a positive
650/// value also returns approximate matches missing up to that many pattern edges.
651/// Matches are written into `matches_out` (search stops when it fills). Returns
652/// the number of matches found.
653pub fn find_subgraph_isomorphisms_bounded(
654    quins: &[NQuin],
655    pattern: &SubgraphPattern,
656    max_missing_edges: u8,
657    matches_out: &mut [SubgraphMatch],
658) -> Result<usize, GraphAnalysisError> {
659    if quins.len() > MAX_HEAP_GRAPH_ANALYSIS_QUINS {
660        return Err(GraphAnalysisError::InputTooLarge);
661    }
662    let graph = BoundedQualiaGraph::from_quins(quins)?;
663    Ok(graph.find_subgraph_isomorphisms(pattern, max_missing_edges, matches_out))
664}
665
666/// Graph structure built from NQuin relations
667#[derive(Debug, Clone)]
668pub struct QualiaGraph {
669    pub nodes: HashMap<u64, GraphNode>,
670    pub edges: HashMap<(u64, u64), GraphEdge>,
671    pub adjacency_list: HashMap<u64, Vec<u64>>,
672}
673
674#[derive(Debug, Clone)]
675pub struct GraphNode {
676    pub id: u64,
677    pub degree: usize,
678    pub centrality_score: f64,
679    pub community_id: Option<usize>,
680}
681
682#[derive(Debug, Clone)]
683pub struct GraphEdge {
684    pub source: u64,
685    pub target: u64,
686    pub weight: f64,
687}
688
689impl QualiaGraph {
690    /// Create a new graph from NQuin relations
691    pub fn from_quins(quins: &[NQuin]) -> Self {
692        let mut nodes = HashMap::new();
693        let mut edges = HashMap::new();
694        let mut adjacency_list = HashMap::new();
695
696        // Build graph structure
697        for quin in quins {
698            // Add source node
699            nodes.entry(quin.subject).or_insert_with(|| GraphNode {
700                id: quin.subject,
701                degree: 0,
702                centrality_score: 0.0,
703                community_id: None,
704            });
705
706            // Add target node
707            nodes.entry(quin.object).or_insert_with(|| GraphNode {
708                id: quin.object,
709                degree: 0,
710                centrality_score: 0.0,
711                community_id: None,
712            });
713
714            // Add edge
715            let edge = GraphEdge {
716                source: quin.subject,
717                target: quin.object,
718                weight: 1.0, // Default weight
719            };
720            edges.insert((quin.subject, quin.object), edge);
721
722            // Update adjacency list
723            adjacency_list
724                .entry(quin.subject)
725                .or_insert_with(Vec::new)
726                .push(quin.object);
727
728            // Update degrees
729            if let Some(node) = nodes.get_mut(&quin.subject) {
730                node.degree += 1;
731            }
732        }
733
734        Self {
735            nodes,
736            edges,
737            adjacency_list,
738        }
739    }
740
741    /// Calculate betweenness centrality for all nodes
742    pub fn calculate_betweenness_centrality(&mut self) {
743        // Brandes' algorithm for betweenness centrality (directed graph)
744        // sigma[v] = number of shortest paths from source to v
745        // dist[v]  = BFS distance from source to v (-1 = unvisited)
746        // delta[v] = dependency of source on v
747        let node_ids: Vec<u64> = self.nodes.keys().cloned().collect();
748        let mut scores: HashMap<u64, f64> = node_ids.iter().map(|&id| (id, 0.0)).collect();
749
750        for &source in &node_ids {
751            let mut sigma: HashMap<u64, f64> = node_ids.iter().map(|&id| (id, 0.0)).collect();
752            let mut dist: HashMap<u64, i64> = node_ids.iter().map(|&id| (id, -1)).collect();
753            // predecessors[v] = list of nodes w on a shortest path to v
754            let mut pred: HashMap<u64, Vec<u64>> =
755                node_ids.iter().map(|&id| (id, Vec::new())).collect();
756            let mut stack: Vec<u64> = Vec::new();
757            // FIFO queue for BFS
758            let mut queue: std::collections::VecDeque<u64> = std::collections::VecDeque::new();
759
760            sigma.insert(source, 1.0);
761            dist.insert(source, 0);
762            queue.push_back(source);
763
764            // BFS phase
765            while let Some(v) = queue.pop_front() {
766                stack.push(v);
767                let v_dist = dist[&v];
768                if let Some(neighbors) = self.adjacency_list.get(&v) {
769                    for &w in neighbors {
770                        // First time visiting w?
771                        if dist[&w] < 0 {
772                            queue.push_back(w);
773                            dist.insert(w, v_dist + 1);
774                        }
775                        // Is v on a shortest path to w?
776                        if dist[&w] == v_dist + 1 {
777                            *sigma.get_mut(&w).unwrap() += sigma[&v];
778                            pred.get_mut(&w).unwrap().push(v);
779                        }
780                    }
781                }
782            }
783
784            // Accumulation phase (back-propagation)
785            let mut delta: HashMap<u64, f64> = node_ids.iter().map(|&id| (id, 0.0)).collect();
786            while let Some(w) = stack.pop() {
787                for &v in &pred[&w] {
788                    let coeff = (sigma[&v] / sigma[&w]) * (1.0 + delta[&w]);
789                    *delta.get_mut(&v).unwrap() += coeff;
790                }
791                if w != source {
792                    *scores.get_mut(&w).unwrap() += delta[&w];
793                }
794            }
795        }
796
797        // Normalize scores (directed graph: divide by (n-1)(n-2))
798        let n = self.nodes.len() as f64;
799        if n > 2.0 {
800            let norm = (n - 1.0) * (n - 2.0);
801            for score in scores.values_mut() {
802                *score /= norm;
803            }
804        }
805
806        // Update node centrality scores
807        for (node_id, score) in scores {
808            if let Some(node) = self.nodes.get_mut(&node_id) {
809                node.centrality_score = score;
810            }
811        }
812    }
813
814    /// Detect communities using simple modularity optimization
815    pub fn detect_communities(&mut self) -> Vec<Vec<u64>> {
816        let mut communities: Vec<Vec<u64>> =
817            self.nodes.keys().cloned().map(|id| vec![id]).collect();
818        let mut improved = true;
819
820        while improved {
821            improved = false;
822
823            for i in 0..communities.len() {
824                if i >= communities.len() {
825                    break;
826                }
827
828                let current_community = communities[i].clone();
829                let best_move = self.find_best_community_move(&current_community, &communities, i);
830
831                if let Some((target_community, modularity_gain)) = best_move {
832                    if modularity_gain > 0.0 {
833                        // Move nodes to target community
834                        communities[target_community].extend(&current_community);
835                        communities.remove(i);
836                        improved = true;
837                        break;
838                    }
839                }
840            }
841        }
842
843        // Update community IDs in nodes
844        for (community_id, community) in communities.iter().enumerate() {
845            for &node_id in community {
846                if let Some(node) = self.nodes.get_mut(&node_id) {
847                    node.community_id = Some(community_id);
848                }
849            }
850        }
851
852        communities
853    }
854
855    /// Find best community move for modularity optimization
856    fn find_best_community_move(
857        &self,
858        community: &[u64],
859        all_communities: &[Vec<u64>],
860        current_index: usize,
861    ) -> Option<(usize, f64)> {
862        let mut best_move = None;
863        let mut best_gain = 0.0;
864
865        for (i, other_community) in all_communities.iter().enumerate() {
866            if i == current_index {
867                continue;
868            }
869
870            let gain = self.calculate_modularity_gain(community, other_community);
871            if gain > best_gain {
872                best_gain = gain;
873                best_move = Some((i, gain));
874            }
875        }
876
877        best_move
878    }
879
880    /// Calculate modularity gain for merging two communities (Louvain delta-Q).
881    ///
882    /// ΔQ = e_ij/m  −  (a_i × a_j) / (2m²)
883    /// where e_ij = edges crossing between comm1 and comm2,
884    ///       a_x  = sum of degrees of nodes in community x,
885    ///       m    = total number of edges in the graph.
886    fn calculate_modularity_gain(&self, comm1: &[u64], comm2: &[u64]) -> f64 {
887        let m = self.edges.len() as f64;
888        if m == 0.0 {
889            return 0.0;
890        }
891
892        let set1: HashSet<u64> = comm1.iter().cloned().collect();
893        let set2: HashSet<u64> = comm2.iter().cloned().collect();
894
895        // Count edges crossing from comm1 to comm2 or comm2 to comm1
896        let mut e_ij = 0.0;
897        for &(source, target) in self.edges.keys() {
898            if (set1.contains(&source) && set2.contains(&target))
899                || (set2.contains(&source) && set1.contains(&target))
900            {
901                e_ij += 1.0;
902            }
903        }
904
905        // Degree sums
906        let a1: f64 = comm1
907            .iter()
908            .filter_map(|id| self.nodes.get(id))
909            .map(|n| n.degree as f64)
910            .sum();
911        let a2: f64 = comm2
912            .iter()
913            .filter_map(|id| self.nodes.get(id))
914            .map(|n| n.degree as f64)
915            .sum();
916
917        (e_ij / m) - (a1 * a2) / (2.0 * m * m)
918    }
919
920    /// Find common motifs (3-node patterns)
921    pub fn find_motifs(&self) -> Vec<Motif> {
922        // Deduplicate triangles by canonical sorted triple so that each
923        // undirected triangle (regardless of orientation in the directed graph)
924        // is reported exactly once.
925        let mut seen: HashSet<[u64; 3]> = HashSet::new();
926        let mut motifs = Vec::new();
927
928        for &node_a in self.nodes.keys() {
929            if let Some(neighbors_a) = self.adjacency_list.get(&node_a) {
930                for &node_b in neighbors_a {
931                    if let Some(neighbors_b) = self.adjacency_list.get(&node_b) {
932                        for &node_c in neighbors_b {
933                            if node_c != node_a {
934                                // Check if this forms a triangle motif (directed cycle a→b→c→a)
935                                if let Some(neighbors_c) = self.adjacency_list.get(&node_c) {
936                                    if neighbors_c.contains(&node_a) {
937                                        // Build canonical key: sorted triple
938                                        let mut key = [node_a, node_b, node_c];
939                                        key.sort_unstable();
940                                        if seen.insert(key) {
941                                            motifs.push(Motif {
942                                                pattern: MotifPattern::Triangle,
943                                                nodes: vec![node_a, node_b, node_c],
944                                                frequency: 1.0,
945                                            });
946                                        }
947                                    }
948                                }
949                            }
950                        }
951                    }
952                }
953            }
954        }
955
956        motifs
957    }
958
959    /// Get top nodes by centrality score
960    pub fn get_top_central_nodes(&self, top_n: usize) -> Vec<(u64, f64)> {
961        let mut nodes: Vec<(u64, f64)> = self
962            .nodes
963            .iter()
964            .map(|(id, node)| (*id, node.centrality_score))
965            .collect();
966
967        nodes.sort_by(|a, b| b.1.partial_cmp(&a.1).unwrap_or(std::cmp::Ordering::Equal));
968        nodes.truncate(top_n);
969        nodes
970    }
971
972    /// Calculate graph density
973    pub fn density(&self) -> f64 {
974        let n = self.nodes.len();
975        if n < 2 {
976            return 0.0;
977        }
978
979        let possible_edges = n * (n - 1);
980        self.edges.len() as f64 / possible_edges as f64
981    }
982
983    /// Convert graph state to NQuin for storage
984    pub fn to_quins(&self, context: u64) -> Vec<NQuin> {
985        let mut quins = Vec::new();
986
987        // Store node centrality scores
988        for (node_id, node) in &self.nodes {
989            let mut quin = NQuin {
990                subject: *node_id,
991                predicate: crate::q_hash("has_centrality_score"),
992                object: (node.centrality_score * 1000.0) as u64, // Store as scaled integer
993                context,
994                metadata: 0,
995                parity: 0,
996            };
997
998            // Store degree in metadata
999            quin.metadata = node.degree as u64;
1000            quin.parity = quin.subject ^ quin.predicate ^ quin.object ^ quin.context;
1001            quins.push(quin);
1002        }
1003
1004        quins
1005    }
1006}
1007
1008/// Motif pattern types
1009#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1010pub enum MotifPattern {
1011    Triangle,
1012    Chain,
1013    Star,
1014    Fork,
1015}
1016
1017/// Graph motif representation
1018#[derive(Debug, Clone)]
1019pub struct Motif {
1020    pub pattern: MotifPattern,
1021    pub nodes: Vec<u64>,
1022    pub frequency: f64,
1023}
1024
1025/// Analyze graph topology in a bounded, heap-backed batch.
1026pub fn analyze_graph_topology(
1027    quins: &[NQuin],
1028    context: u64,
1029) -> Result<GraphAnalysisResult, GraphAnalysisError> {
1030    if quins.len() > MAX_HEAP_GRAPH_ANALYSIS_QUINS {
1031        return Err(GraphAnalysisError::InputTooLarge);
1032    }
1033
1034    let mut graph = QualiaGraph::from_quins(quins);
1035
1036    // Calculate centrality
1037    graph.calculate_betweenness_centrality();
1038
1039    // Detect communities
1040    let communities = graph.detect_communities();
1041
1042    // Find motifs
1043    let motifs = graph.find_motifs();
1044
1045    // Get top central nodes
1046    let top_nodes = graph.get_top_central_nodes(10);
1047
1048    // Calculate density
1049    let density = graph.density();
1050
1051    // Convert to quins for storage
1052    let graph_quins = graph.to_quins(context);
1053
1054    Ok(GraphAnalysisResult {
1055        graph_quins,
1056        communities,
1057        motifs,
1058        top_nodes,
1059        density,
1060        node_count: graph.nodes.len(),
1061        edge_count: graph.edges.len(),
1062    })
1063}
1064
1065/// Result of graph analysis
1066#[derive(Debug, Clone)]
1067pub struct GraphAnalysisResult {
1068    pub graph_quins: Vec<NQuin>,
1069    pub communities: Vec<Vec<u64>>,
1070    pub motifs: Vec<Motif>,
1071    pub top_nodes: Vec<(u64, f64)>,
1072    pub density: f64,
1073    pub node_count: usize,
1074    pub edge_count: usize,
1075}
1076
1077#[cfg(test)]
1078mod tests {
1079    use super::*;
1080
1081    #[test]
1082    fn test_graph_creation() {
1083        let quins = vec![
1084            NQuin {
1085                subject: 1,
1086                predicate: crate::q_hash("connects_to"),
1087                object: 2,
1088                context: 100,
1089                metadata: 0,
1090                parity: 0,
1091            },
1092            NQuin {
1093                subject: 2,
1094                predicate: crate::q_hash("connects_to"),
1095                object: 3,
1096                context: 100,
1097                metadata: 0,
1098                parity: 0,
1099            },
1100            NQuin {
1101                subject: 1,
1102                predicate: crate::q_hash("connects_to"),
1103                object: 3,
1104                context: 100,
1105                metadata: 0,
1106                parity: 0,
1107            },
1108        ];
1109
1110        let graph = QualiaGraph::from_quins(&quins);
1111
1112        assert_eq!(graph.nodes.len(), 3);
1113        assert_eq!(graph.edges.len(), 3);
1114        assert_eq!(graph.adjacency_list.get(&1).unwrap().len(), 2);
1115    }
1116
1117    #[test]
1118    fn test_centrality_calculation() {
1119        let quins = vec![
1120            NQuin {
1121                subject: 1,
1122                predicate: 1,
1123                object: 2,
1124                context: 100,
1125                metadata: 0,
1126                parity: 0,
1127            },
1128            NQuin {
1129                subject: 2,
1130                predicate: 1,
1131                object: 3,
1132                context: 100,
1133                metadata: 0,
1134                parity: 0,
1135            },
1136        ];
1137
1138        let mut graph = QualiaGraph::from_quins(&quins);
1139        graph.calculate_betweenness_centrality();
1140
1141        // Node 2 should have highest betweenness because it is the only bridge from 1 to 3.
1142        let node2_centrality = graph.nodes.get(&2).unwrap().centrality_score;
1143        let node1_centrality = graph.nodes.get(&1).unwrap().centrality_score;
1144
1145        assert!(node2_centrality > node1_centrality);
1146    }
1147
1148    #[test]
1149    fn test_community_detection() {
1150        let quins = vec![
1151            NQuin {
1152                subject: 1,
1153                predicate: 1,
1154                object: 2,
1155                context: 100,
1156                metadata: 0,
1157                parity: 0,
1158            },
1159            NQuin {
1160                subject: 2,
1161                predicate: 1,
1162                object: 1,
1163                context: 100,
1164                metadata: 0,
1165                parity: 0,
1166            },
1167            NQuin {
1168                subject: 3,
1169                predicate: 1,
1170                object: 4,
1171                context: 100,
1172                metadata: 0,
1173                parity: 0,
1174            },
1175            NQuin {
1176                subject: 4,
1177                predicate: 1,
1178                object: 3,
1179                context: 100,
1180                metadata: 0,
1181                parity: 0,
1182            },
1183        ];
1184
1185        let mut graph = QualiaGraph::from_quins(&quins);
1186        let communities = graph.detect_communities();
1187
1188        // Should detect two separate communities
1189        assert_eq!(communities.len(), 2);
1190    }
1191
1192    #[test]
1193    fn test_motif_detection() {
1194        let quins = vec![
1195            NQuin {
1196                subject: 1,
1197                predicate: 1,
1198                object: 2,
1199                context: 100,
1200                metadata: 0,
1201                parity: 0,
1202            },
1203            NQuin {
1204                subject: 2,
1205                predicate: 1,
1206                object: 3,
1207                context: 100,
1208                metadata: 0,
1209                parity: 0,
1210            },
1211            NQuin {
1212                subject: 3,
1213                predicate: 1,
1214                object: 1,
1215                context: 100,
1216                metadata: 0,
1217                parity: 0,
1218            },
1219        ];
1220
1221        let graph = QualiaGraph::from_quins(&quins);
1222        let motifs = graph.find_motifs();
1223
1224        // Should detect one triangle motif
1225        assert_eq!(motifs.len(), 1);
1226        assert_eq!(motifs[0].pattern, MotifPattern::Triangle);
1227    }
1228
1229    #[test]
1230    fn test_graph_analysis() {
1231        let quins = vec![
1232            NQuin {
1233                subject: 1,
1234                predicate: 1,
1235                object: 2,
1236                context: 100,
1237                metadata: 0,
1238                parity: 0,
1239            },
1240            NQuin {
1241                subject: 2,
1242                predicate: 1,
1243                object: 3,
1244                context: 100,
1245                metadata: 0,
1246                parity: 0,
1247            },
1248            NQuin {
1249                subject: 3,
1250                predicate: 1,
1251                object: 1,
1252                context: 100,
1253                metadata: 0,
1254                parity: 0,
1255            },
1256        ];
1257
1258        let result = analyze_graph_topology(&quins, 100).unwrap();
1259
1260        assert_eq!(result.node_count, 3);
1261        assert_eq!(result.edge_count, 3);
1262        assert!(result.density > 0.0);
1263        assert!(!result.communities.is_empty());
1264    }
1265
1266    #[test]
1267    fn test_graph_analysis_rejects_oversized_batches() {
1268        let quins = vec![
1269            NQuin {
1270                subject: 1,
1271                predicate: 1,
1272                object: 2,
1273                context: 100,
1274                metadata: 0,
1275                parity: 0,
1276            };
1277            MAX_HEAP_GRAPH_ANALYSIS_QUINS + 1
1278        ];
1279
1280        let result = analyze_graph_topology(&quins, 100);
1281
1282        assert!(matches!(result, Err(GraphAnalysisError::InputTooLarge)));
1283    }
1284
1285    #[test]
1286    fn test_bounded_graph_analysis_zero_heap_path() {
1287        let quins = vec![
1288            NQuin {
1289                subject: 1,
1290                predicate: 1,
1291                object: 2,
1292                context: 100,
1293                metadata: 0,
1294                parity: 0,
1295            },
1296            NQuin {
1297                subject: 2,
1298                predicate: 1,
1299                object: 3,
1300                context: 100,
1301                metadata: 0,
1302                parity: 0,
1303            },
1304            NQuin {
1305                subject: 3,
1306                predicate: 1,
1307                object: 1,
1308                context: 100,
1309                metadata: 0,
1310                parity: 0,
1311            },
1312        ];
1313        let mut graph_quins = [NQuin::default(); 16];
1314        let mut community_nodes = [0u64; 16];
1315        let mut community_spans = [CommunitySpan { start: 0, len: 0 }; 8];
1316        let mut motifs = [MotifRecord {
1317            pattern: MotifPattern::Triangle,
1318            node_a: 0,
1319            node_b: 0,
1320            node_c: 0,
1321            frequency: 0.0,
1322        }; 8];
1323        let mut top_nodes = [TopNodeScore {
1324            node_id: 0,
1325            centrality_score: 0.0,
1326        }; 8];
1327
1328        let summary = analyze_graph_topology_bounded(
1329            &quins,
1330            100,
1331            &mut graph_quins,
1332            &mut community_nodes,
1333            &mut community_spans,
1334            &mut motifs,
1335            &mut top_nodes,
1336        )
1337        .unwrap();
1338
1339        assert_eq!(summary.node_count, 3);
1340        assert_eq!(summary.edge_count, 3);
1341        assert_eq!(summary.community_count, 1);
1342        assert_eq!(summary.motif_count, 1);
1343        assert!(summary.top_node_count >= 1);
1344        assert!(summary.density > 0.0);
1345    }
1346
1347    #[test]
1348    fn test_pagerank_sums_to_one_and_ranks_hub() {
1349        // Star: 1→3, 2→3, 4→3 (node 3 is the sink hub) plus 3→1 to avoid a pure dangling.
1350        let quins = vec![
1351            NQuin {
1352                subject: 1,
1353                predicate: 1,
1354                object: 3,
1355                context: 0,
1356                metadata: 0,
1357                parity: 0,
1358            },
1359            NQuin {
1360                subject: 2,
1361                predicate: 1,
1362                object: 3,
1363                context: 0,
1364                metadata: 0,
1365                parity: 0,
1366            },
1367            NQuin {
1368                subject: 4,
1369                predicate: 1,
1370                object: 3,
1371                context: 0,
1372                metadata: 0,
1373                parity: 0,
1374            },
1375            NQuin {
1376                subject: 3,
1377                predicate: 1,
1378                object: 1,
1379                context: 0,
1380                metadata: 0,
1381                parity: 0,
1382            },
1383        ];
1384        let mut ids = [0u64; 16];
1385        let mut scores = [0f32; 16];
1386        let count = pagerank_bounded(&quins, 0.85, 100, 1e-6, &mut ids, &mut scores).unwrap();
1387        assert_eq!(count, 4);
1388
1389        // Probability distribution: scores sum to ~1.
1390        let total: f32 = scores[..count].iter().sum();
1391        assert!(
1392            (total - 1.0).abs() < 1e-3,
1393            "pagerank should sum to 1, got {total}"
1394        );
1395
1396        // Node 3 (the hub everyone points at) must rank highest.
1397        let hub_pos = ids[..count].iter().position(|&id| id == 3).unwrap();
1398        let hub_score = scores[hub_pos];
1399        for i in 0..count {
1400            if i != hub_pos {
1401                assert!(
1402                    hub_score > scores[i],
1403                    "hub node 3 should outrank node {}",
1404                    ids[i]
1405                );
1406            }
1407        }
1408    }
1409
1410    #[test]
1411    fn test_subgraph_isomorphism_exact_triangle() {
1412        // Data graph contains a directed triangle 1→2→3→1 plus an extra edge.
1413        let quins = vec![
1414            NQuin {
1415                subject: 1,
1416                predicate: 1,
1417                object: 2,
1418                context: 0,
1419                metadata: 0,
1420                parity: 0,
1421            },
1422            NQuin {
1423                subject: 2,
1424                predicate: 1,
1425                object: 3,
1426                context: 0,
1427                metadata: 0,
1428                parity: 0,
1429            },
1430            NQuin {
1431                subject: 3,
1432                predicate: 1,
1433                object: 1,
1434                context: 0,
1435                metadata: 0,
1436                parity: 0,
1437            },
1438            NQuin {
1439                subject: 3,
1440                predicate: 1,
1441                object: 4,
1442                context: 0,
1443                metadata: 0,
1444                parity: 0,
1445            },
1446        ];
1447        // Pattern: directed 3-cycle a→b→c→a.
1448        let pattern = SubgraphPattern::new(3)
1449            .with_edge(0, 1)
1450            .with_edge(1, 2)
1451            .with_edge(2, 0);
1452        let mut matches = [SubgraphMatch {
1453            mapping: [0; MAX_SUBGRAPH_PATTERN_NODES],
1454            len: 0,
1455            missing_edges: 0,
1456        }; 16];
1457        let n = find_subgraph_isomorphisms_bounded(&quins, &pattern, 0, &mut matches).unwrap();
1458
1459        // The directed 3-cycle has exactly 3 rotations of the same triangle.
1460        assert_eq!(n, 3, "expected 3 rotations of the directed triangle");
1461        for m in &matches[..n] {
1462            assert_eq!(m.missing_edges, 0);
1463            assert_eq!(m.len, 3);
1464            // every matched node id is one of {1,2,3}, never the extra node 4
1465            for &id in &m.mapping[..3] {
1466                assert!(
1467                    id == 1 || id == 2 || id == 3,
1468                    "match included non-triangle node {id}"
1469                );
1470            }
1471        }
1472    }
1473
1474    #[test]
1475    fn test_subgraph_isomorphism_approximate_allows_missing_edge() {
1476        // Data graph has a path 1→2→3 but NOT the closing edge 3→1.
1477        let quins = vec![
1478            NQuin {
1479                subject: 1,
1480                predicate: 1,
1481                object: 2,
1482                context: 0,
1483                metadata: 0,
1484                parity: 0,
1485            },
1486            NQuin {
1487                subject: 2,
1488                predicate: 1,
1489                object: 3,
1490                context: 0,
1491                metadata: 0,
1492                parity: 0,
1493            },
1494        ];
1495        let triangle = SubgraphPattern::new(3)
1496            .with_edge(0, 1)
1497            .with_edge(1, 2)
1498            .with_edge(2, 0);
1499        let mut matches = [SubgraphMatch {
1500            mapping: [0; MAX_SUBGRAPH_PATTERN_NODES],
1501            len: 0,
1502            missing_edges: 0,
1503        }; 16];
1504
1505        // Exact: no triangle exists.
1506        let exact = find_subgraph_isomorphisms_bounded(&quins, &triangle, 0, &mut matches).unwrap();
1507        assert_eq!(exact, 0);
1508
1509        // Approximate (allow 1 missing edge): the open path 1→2→3 matches with the
1510        // 3→1 edge absent.
1511        let approx =
1512            find_subgraph_isomorphisms_bounded(&quins, &triangle, 1, &mut matches).unwrap();
1513        assert!(approx >= 1, "approximate match should find the open path");
1514        assert!(matches[..approx].iter().any(|m| {
1515            m.missing_edges == 1 && m.mapping[0] == 1 && m.mapping[1] == 2 && m.mapping[2] == 3
1516        }));
1517    }
1518}