1use crate::NQuin;
11use std::collections::{HashMap, HashSet};
12
13pub 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
24pub 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
48pub const MAX_SUBGRAPH_PATTERN_NODES: usize = 8;
51
52#[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 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 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#[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 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 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 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 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 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 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 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 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 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 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 #[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 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
588pub 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
621pub 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
647pub 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#[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 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 for quin in quins {
698 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 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 let edge = GraphEdge {
716 source: quin.subject,
717 target: quin.object,
718 weight: 1.0, };
720 edges.insert((quin.subject, quin.object), edge);
721
722 adjacency_list
724 .entry(quin.subject)
725 .or_insert_with(Vec::new)
726 .push(quin.object);
727
728 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 pub fn calculate_betweenness_centrality(&mut self) {
743 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 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 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 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 if dist[&w] < 0 {
772 queue.push_back(w);
773 dist.insert(w, v_dist + 1);
774 }
775 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 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 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 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 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(¤t_community, &communities, i);
830
831 if let Some((target_community, modularity_gain)) = best_move {
832 if modularity_gain > 0.0 {
833 communities[target_community].extend(¤t_community);
835 communities.remove(i);
836 improved = true;
837 break;
838 }
839 }
840 }
841 }
842
843 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 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 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 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 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 pub fn find_motifs(&self) -> Vec<Motif> {
922 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 if let Some(neighbors_c) = self.adjacency_list.get(&node_c) {
936 if neighbors_c.contains(&node_a) {
937 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 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 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 pub fn to_quins(&self, context: u64) -> Vec<NQuin> {
985 let mut quins = Vec::new();
986
987 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, context,
994 metadata: 0,
995 parity: 0,
996 };
997
998 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#[derive(Debug, Clone, Copy, PartialEq, Eq)]
1010pub enum MotifPattern {
1011 Triangle,
1012 Chain,
1013 Star,
1014 Fork,
1015}
1016
1017#[derive(Debug, Clone)]
1019pub struct Motif {
1020 pub pattern: MotifPattern,
1021 pub nodes: Vec<u64>,
1022 pub frequency: f64,
1023}
1024
1025pub 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 graph.calculate_betweenness_centrality();
1038
1039 let communities = graph.detect_communities();
1041
1042 let motifs = graph.find_motifs();
1044
1045 let top_nodes = graph.get_top_central_nodes(10);
1047
1048 let density = graph.density();
1050
1051 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#[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 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 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 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 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 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 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 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 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 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 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 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 let exact = find_subgraph_isomorphisms_bounded(&quins, &triangle, 0, &mut matches).unwrap();
1507 assert_eq!(exact, 0);
1508
1509 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}