1use super::*;
2
3impl RedDBRuntime {
4 pub fn graph_neighborhood(
5 &self,
6 node: &str,
7 direction: RuntimeGraphDirection,
8 max_depth: usize,
9 edge_labels: Option<Vec<String>>,
10 projection: Option<RuntimeGraphProjection>,
11 ) -> RedDBResult<RuntimeGraphNeighborhoodResult> {
12 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
13 let node = resolve_graph_node_id(&graph, node)?;
14 let edge_filters = merge_edge_filters(edge_labels, projection.as_ref());
15
16 let mut visited: HashMap<String, usize> = HashMap::new();
17 let mut queue = VecDeque::new();
18 let mut nodes = Vec::new();
19 let mut edges = Vec::new();
20 let mut seen_edges = HashSet::new();
21
22 visited.insert(node.clone(), 0);
23 queue.push_back((node.clone(), 0usize));
24
25 while let Some((current, depth)) = queue.pop_front() {
26 if let Some(stored) = graph.get_node(¤t) {
27 nodes.push(RuntimeGraphVisit {
28 depth,
29 node: stored_node_to_runtime(stored),
30 });
31 }
32
33 if depth >= max_depth {
34 continue;
35 }
36
37 let mut adjacent =
38 graph_adjacent_edges(&graph, ¤t, direction, edge_filters.as_ref());
39 adjacent.sort_by(|left, right| left.0.cmp(&right.0));
40
41 for (neighbor, edge) in adjacent {
42 push_runtime_edge(&mut edges, &mut seen_edges, edge);
43 if let std::collections::hash_map::Entry::Vacant(slot) = visited.entry(neighbor) {
45 let next_depth = depth + 1;
46 queue.push_back((slot.key().clone(), next_depth));
47 slot.insert(next_depth);
48 }
49 }
50 }
51
52 Ok(RuntimeGraphNeighborhoodResult {
53 source: node,
54 direction,
55 max_depth,
56 nodes,
57 edges,
58 })
59 }
60
61 pub fn graph_traverse(
62 &self,
63 source: &str,
64 direction: RuntimeGraphDirection,
65 max_depth: usize,
66 strategy: RuntimeGraphTraversalStrategy,
67 edge_labels: Option<Vec<String>>,
68 projection: Option<RuntimeGraphProjection>,
69 ) -> RedDBResult<RuntimeGraphTraversalResult> {
70 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
71 let source = resolve_graph_node_id(&graph, source)?;
72 let edge_filters = merge_edge_filters(edge_labels, projection.as_ref());
73
74 let mut visits = Vec::new();
75 let mut edges = Vec::new();
76 let mut seen_nodes = HashSet::new();
77 let mut seen_edges = HashSet::new();
78
79 match strategy {
80 RuntimeGraphTraversalStrategy::Bfs => {
81 let mut queue = VecDeque::new();
82 queue.push_back((source.clone(), 0usize));
83 seen_nodes.insert(source.clone());
84
85 while let Some((current, depth)) = queue.pop_front() {
86 if let Some(stored) = graph.get_node(¤t) {
87 visits.push(RuntimeGraphVisit {
88 depth,
89 node: stored_node_to_runtime(stored),
90 });
91 }
92
93 if depth >= max_depth {
94 continue;
95 }
96
97 let mut adjacent =
98 graph_adjacent_edges(&graph, ¤t, direction, edge_filters.as_ref());
99 adjacent.sort_by(|left, right| left.0.cmp(&right.0));
100 for (neighbor, edge) in adjacent {
101 push_runtime_edge(&mut edges, &mut seen_edges, edge);
102 if seen_nodes.insert(neighbor.clone()) {
103 queue.push_back((neighbor, depth + 1));
104 }
105 }
106 }
107 }
108 RuntimeGraphTraversalStrategy::Dfs => {
109 let mut stack = vec![(source.clone(), 0usize)];
110 while let Some((current, depth)) = stack.pop() {
111 if !seen_nodes.insert(current.clone()) {
112 continue;
113 }
114
115 if let Some(stored) = graph.get_node(¤t) {
116 visits.push(RuntimeGraphVisit {
117 depth,
118 node: stored_node_to_runtime(stored),
119 });
120 }
121
122 if depth >= max_depth {
123 continue;
124 }
125
126 let mut adjacent =
127 graph_adjacent_edges(&graph, ¤t, direction, edge_filters.as_ref());
128 adjacent.sort_by(|left, right| right.0.cmp(&left.0));
129 for (neighbor, edge) in adjacent {
130 push_runtime_edge(&mut edges, &mut seen_edges, edge);
131 if !seen_nodes.contains(&neighbor) {
132 stack.push((neighbor, depth + 1));
133 }
134 }
135 }
136 }
137 }
138
139 Ok(RuntimeGraphTraversalResult {
140 source,
141 direction,
142 strategy,
143 max_depth,
144 visits,
145 edges,
146 })
147 }
148
149 pub fn graph_shortest_path(
150 &self,
151 source: &str,
152 target: &str,
153 direction: RuntimeGraphDirection,
154 algorithm: RuntimeGraphPathAlgorithm,
155 edge_labels: Option<Vec<String>>,
156 projection: Option<RuntimeGraphProjection>,
157 ) -> RedDBResult<RuntimeGraphPathResult> {
158 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
159 let source_owned = resolve_graph_node_id(&graph, source)?;
160 let target_owned = resolve_graph_node_id(&graph, target)?;
161 let source = source_owned.as_str();
162 let target = target_owned.as_str();
163
164 let merged_edge_filters = merge_edge_filters(edge_labels, projection.as_ref());
165 let path = match (direction, merged_edge_filters.as_ref()) {
166 (RuntimeGraphDirection::Outgoing, None) => match algorithm {
167 RuntimeGraphPathAlgorithm::Bfs => {
168 let result = BFS::shortest_path(&graph, source, target);
169 RuntimeGraphPathResult {
170 source: source.to_string(),
171 target: target.to_string(),
172 direction,
173 algorithm,
174 nodes_visited: result.nodes_visited,
175 negative_cycle_detected: None,
176 path: result.path.map(|path| path_to_runtime(&graph, &path)),
177 }
178 }
179 RuntimeGraphPathAlgorithm::Dijkstra => {
180 let result = Dijkstra::shortest_path(&graph, source, target);
181 RuntimeGraphPathResult {
182 source: source.to_string(),
183 target: target.to_string(),
184 direction,
185 algorithm,
186 nodes_visited: result.nodes_visited,
187 negative_cycle_detected: None,
188 path: result.path.map(|path| path_to_runtime(&graph, &path)),
189 }
190 }
191 RuntimeGraphPathAlgorithm::AStar => {
192 let result = AStar::shortest_path_no_heuristic(&graph, source, target);
193 RuntimeGraphPathResult {
194 source: source.to_string(),
195 target: target.to_string(),
196 direction,
197 algorithm,
198 nodes_visited: result.nodes_visited,
199 negative_cycle_detected: None,
200 path: result.path.map(|path| path_to_runtime(&graph, &path)),
201 }
202 }
203 RuntimeGraphPathAlgorithm::BellmanFord => {
204 let result = BellmanFord::shortest_path(&graph, source, target);
205 RuntimeGraphPathResult {
206 source: source.to_string(),
207 target: target.to_string(),
208 direction,
209 algorithm,
210 nodes_visited: result.nodes_visited,
211 negative_cycle_detected: Some(result.has_negative_cycle),
212 path: result.path.map(|path| path_to_runtime(&graph, &path)),
213 }
214 }
215 },
216 _ => shortest_path_runtime(
217 &graph,
218 source,
219 target,
220 direction,
221 algorithm,
222 merged_edge_filters.as_ref(),
223 )?,
224 };
225
226 Ok(path)
227 }
228
229 pub fn graph_components(
230 &self,
231 mode: RuntimeGraphComponentsMode,
232 min_size: usize,
233 projection: Option<RuntimeGraphProjection>,
234 ) -> RedDBResult<RuntimeGraphComponentsResult> {
235 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
236 let min_size = min_size.max(1);
237 let components = match mode {
238 RuntimeGraphComponentsMode::Connected => ConnectedComponents::find(&graph)
239 .components
240 .into_iter()
241 .filter(|component| component.size >= min_size)
242 .map(|component| RuntimeGraphComponent {
243 id: component.id,
244 size: component.size,
245 nodes: component.nodes,
246 })
247 .collect::<Vec<_>>(),
248 RuntimeGraphComponentsMode::Weak => WeaklyConnectedComponents::find(&graph)
249 .components
250 .into_iter()
251 .filter(|component| component.len() >= min_size)
252 .enumerate()
253 .map(|(index, nodes)| RuntimeGraphComponent {
254 id: format!("wcc:{index}"),
255 size: nodes.len(),
256 nodes,
257 })
258 .collect::<Vec<_>>(),
259 RuntimeGraphComponentsMode::Strong => StronglyConnectedComponents::find(&graph)
260 .components
261 .into_iter()
262 .filter(|component| component.len() >= min_size)
263 .enumerate()
264 .map(|(index, nodes)| RuntimeGraphComponent {
265 id: format!("scc:{index}"),
266 size: nodes.len(),
267 nodes,
268 })
269 .collect::<Vec<_>>(),
270 };
271
272 Ok(RuntimeGraphComponentsResult {
273 mode,
274 count: components.len(),
275 components,
276 })
277 }
278
279 pub fn graph_centrality(
280 &self,
281 algorithm: RuntimeGraphCentralityAlgorithm,
282 top_k: usize,
283 normalize: bool,
284 max_iterations: Option<usize>,
285 epsilon: Option<f64>,
286 alpha: Option<f64>,
287 projection: Option<RuntimeGraphProjection>,
288 ) -> RedDBResult<RuntimeGraphCentralityResult> {
289 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
290 let top_k = top_k.max(1);
291
292 match algorithm {
293 RuntimeGraphCentralityAlgorithm::Degree => {
294 let result = DegreeCentrality::compute(&graph);
295 let mut degree_scores = Vec::new();
296 let mut pairs: Vec<_> = result
297 .total_degree
298 .iter()
299 .map(|(node_id, total_degree)| (node_id.clone(), *total_degree))
300 .collect();
301 pairs
302 .sort_by(|left, right| right.1.cmp(&left.1).then_with(|| left.0.cmp(&right.0)));
303 pairs.truncate(top_k);
304
305 for (node_id, total_degree) in pairs {
306 if let Some(node) = graph.get_node(&node_id) {
307 degree_scores.push(RuntimeGraphDegreeScore {
308 node: stored_node_to_runtime(node),
309 in_degree: result.in_degree.get(&node_id).copied().unwrap_or(0),
310 out_degree: result.out_degree.get(&node_id).copied().unwrap_or(0),
311 total_degree,
312 });
313 }
314 }
315
316 Ok(RuntimeGraphCentralityResult {
317 algorithm,
318 normalized: None,
319 iterations: None,
320 converged: None,
321 scores: Vec::new(),
322 degree_scores,
323 })
324 }
325 RuntimeGraphCentralityAlgorithm::Closeness => {
326 let result = ClosenessCentrality::compute(&graph);
327 Ok(RuntimeGraphCentralityResult {
328 algorithm,
329 normalized: None,
330 iterations: None,
331 converged: None,
332 scores: top_runtime_scores(&graph, result.scores, top_k),
333 degree_scores: Vec::new(),
334 })
335 }
336 RuntimeGraphCentralityAlgorithm::Betweenness => {
337 let result = BetweennessCentrality::compute(&graph, normalize);
338 Ok(RuntimeGraphCentralityResult {
339 algorithm,
340 normalized: Some(result.normalized),
341 iterations: None,
342 converged: None,
343 scores: top_runtime_scores(&graph, result.scores, top_k),
344 degree_scores: Vec::new(),
345 })
346 }
347 RuntimeGraphCentralityAlgorithm::Eigenvector => {
348 let mut runner = EigenvectorCentrality::new();
349 if let Some(max_iterations) = max_iterations {
350 runner.max_iterations = max_iterations.max(1);
351 }
352 if let Some(epsilon) = epsilon {
353 runner.epsilon = epsilon.max(0.0);
354 }
355 let result = runner.compute(&graph);
356 Ok(RuntimeGraphCentralityResult {
357 algorithm,
358 normalized: None,
359 iterations: Some(result.iterations),
360 converged: Some(result.converged),
361 scores: top_runtime_scores(&graph, result.scores, top_k),
362 degree_scores: Vec::new(),
363 })
364 }
365 RuntimeGraphCentralityAlgorithm::PageRank => {
366 let mut runner = PageRank::new();
367 if let Some(max_iterations) = max_iterations {
368 runner = runner.max_iterations(max_iterations.max(1));
369 }
370 if let Some(alpha) = alpha {
371 runner = runner.alpha(alpha);
372 }
373 if let Some(epsilon) = epsilon {
374 runner = runner.epsilon(epsilon);
375 }
376 let result = runner.run(&graph);
377 Ok(RuntimeGraphCentralityResult {
378 algorithm,
379 normalized: None,
380 iterations: Some(result.iterations),
381 converged: Some(result.converged),
382 scores: top_runtime_scores(&graph, result.scores, top_k),
383 degree_scores: Vec::new(),
384 })
385 }
386 }
387 }
388
389 pub fn graph_communities(
390 &self,
391 algorithm: RuntimeGraphCommunityAlgorithm,
392 min_size: usize,
393 max_iterations: Option<usize>,
394 resolution: Option<f64>,
395 projection: Option<RuntimeGraphProjection>,
396 ) -> RedDBResult<RuntimeGraphCommunityResult> {
397 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
398 let min_size = min_size.max(1);
399
400 match algorithm {
401 RuntimeGraphCommunityAlgorithm::LabelPropagation => {
402 let mut runner = LabelPropagation::new();
403 if let Some(max_iterations) = max_iterations {
404 runner = runner.max_iterations(max_iterations.max(1));
405 }
406 let result = runner.run(&graph);
407 let communities = result
408 .communities
409 .into_iter()
410 .filter(|community| community.size >= min_size)
411 .map(|community| RuntimeGraphCommunity {
412 id: community.label,
413 size: community.size,
414 nodes: community.nodes,
415 })
416 .collect::<Vec<_>>();
417 Ok(RuntimeGraphCommunityResult {
418 algorithm,
419 count: communities.len(),
420 iterations: Some(result.iterations),
421 converged: Some(result.converged),
422 modularity: None,
423 passes: None,
424 communities,
425 })
426 }
427 RuntimeGraphCommunityAlgorithm::Louvain => {
428 let mut runner = Louvain::new();
429 if let Some(max_iterations) = max_iterations {
430 runner = runner.max_iterations(max_iterations.max(1));
431 }
432 if let Some(resolution) = resolution {
433 runner = runner.resolution(resolution.max(0.0));
434 }
435 let result = runner.run(&graph);
436 let mut communities = result
437 .community_sizes()
438 .into_iter()
439 .filter(|(_, size)| *size >= min_size)
440 .map(|(id, size)| RuntimeGraphCommunity {
441 id: format!("community:{id}"),
442 size,
443 nodes: result.get_community(id),
444 })
445 .collect::<Vec<_>>();
446 communities.sort_by(|left, right| {
447 right
448 .size
449 .cmp(&left.size)
450 .then_with(|| left.id.cmp(&right.id))
451 });
452 Ok(RuntimeGraphCommunityResult {
453 algorithm,
454 count: communities.len(),
455 iterations: None,
456 converged: None,
457 modularity: Some(result.modularity),
458 passes: Some(result.passes),
459 communities,
460 })
461 }
462 }
463 }
464
465 pub fn graph_clustering(
466 &self,
467 top_k: usize,
468 include_triangles: bool,
469 projection: Option<RuntimeGraphProjection>,
470 ) -> RedDBResult<RuntimeGraphClusteringResult> {
471 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
472 let top_k = top_k.max(1);
473 let result = ClusteringCoefficient::compute(&graph);
474 let triangle_count = if include_triangles {
475 Some(crate::storage::engine::TriangleCounting::count(&graph).count)
476 } else {
477 None
478 };
479
480 Ok(RuntimeGraphClusteringResult {
481 global: result.global,
482 local: top_runtime_scores(&graph, result.local, top_k),
483 triangle_count,
484 })
485 }
486
487 pub fn graph_personalized_pagerank(
488 &self,
489 seeds: Vec<String>,
490 top_k: usize,
491 alpha: Option<f64>,
492 epsilon: Option<f64>,
493 max_iterations: Option<usize>,
494 projection: Option<RuntimeGraphProjection>,
495 ) -> RedDBResult<RuntimeGraphCentralityResult> {
496 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
497 if seeds.is_empty() {
498 return Err(RedDBError::Query(
499 "personalized pagerank requires at least one seed".to_string(),
500 ));
501 }
502 for seed in &seeds {
503 ensure_graph_node(&graph, seed)?;
504 }
505
506 let mut runner = PersonalizedPageRank::new(seeds);
507 if let Some(alpha) = alpha {
508 runner = runner.alpha(alpha);
509 }
510 if let Some(epsilon) = epsilon {
511 runner = runner.epsilon(epsilon);
512 }
513 if let Some(max_iterations) = max_iterations {
514 runner = runner.max_iterations(max_iterations.max(1));
515 }
516 let result = runner.run(&graph);
517
518 Ok(RuntimeGraphCentralityResult {
519 algorithm: RuntimeGraphCentralityAlgorithm::PageRank,
520 normalized: None,
521 iterations: Some(result.iterations),
522 converged: Some(result.converged),
523 scores: top_runtime_scores(&graph, result.scores, top_k.max(1)),
524 degree_scores: Vec::new(),
525 })
526 }
527
528 pub fn graph_hits(
529 &self,
530 top_k: usize,
531 epsilon: Option<f64>,
532 max_iterations: Option<usize>,
533 projection: Option<RuntimeGraphProjection>,
534 ) -> RedDBResult<RuntimeGraphHitsResult> {
535 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
536 let mut runner = HITS::new();
537 if let Some(epsilon) = epsilon {
538 runner.epsilon = epsilon.max(0.0);
539 }
540 if let Some(max_iterations) = max_iterations {
541 runner.max_iterations = max_iterations.max(1);
542 }
543 let result = runner.compute(&graph);
544
545 Ok(RuntimeGraphHitsResult {
546 iterations: result.iterations,
547 converged: result.converged,
548 hubs: top_runtime_scores(&graph, result.hub_scores, top_k.max(1)),
549 authorities: top_runtime_scores(&graph, result.authority_scores, top_k.max(1)),
550 })
551 }
552
553 pub fn graph_cycles(
554 &self,
555 max_length: usize,
556 max_cycles: usize,
557 projection: Option<RuntimeGraphProjection>,
558 ) -> RedDBResult<RuntimeGraphCyclesResult> {
559 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
560 let result = CycleDetector::new()
561 .max_length(max_length.max(2))
562 .max_cycles(max_cycles.max(1))
563 .find(&graph);
564
565 Ok(RuntimeGraphCyclesResult {
566 limit_reached: result.limit_reached,
567 cycles: result
568 .cycles
569 .into_iter()
570 .map(|cycle| cycle_to_runtime(&graph, cycle))
571 .collect(),
572 })
573 }
574
575 pub fn graph_topological_sort(
576 &self,
577 projection: Option<RuntimeGraphProjection>,
578 ) -> RedDBResult<RuntimeGraphTopologicalSortResult> {
579 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
580 let ordered_nodes = match DFS::topological_sort(&graph) {
581 Some(order) => order
582 .into_iter()
583 .filter_map(|id| graph.get_node(&id))
584 .map(stored_node_to_runtime)
585 .collect(),
586 None => Vec::new(),
587 };
588
589 Ok(RuntimeGraphTopologicalSortResult {
590 acyclic: !ordered_nodes.is_empty() || graph.node_count() == 0,
591 ordered_nodes,
592 })
593 }
594
595 pub fn graph_properties(
596 &self,
597 projection: Option<RuntimeGraphProjection>,
598 ) -> RedDBResult<RuntimeGraphPropertiesResult> {
599 let graph = materialize_graph_with_projection(self, projection.as_ref())?;
600 let node_count = graph.node_count() as usize;
601 let edges = graph.iter_all_edges();
602 let edge_count = edges.len();
603
604 let connected = ConnectedComponents::find(&graph);
605 let weak = WeaklyConnectedComponents::find(&graph);
606 let strong = StronglyConnectedComponents::find(&graph);
607 let cycle_result = CycleDetector::new()
608 .max_length(node_count.max(2))
609 .max_cycles(1)
610 .find(&graph);
611
612 let mut self_loop_count = 0usize;
613 let mut negative_edge_count = 0usize;
614 let mut directed_pairs = HashSet::new();
615 let mut undirected_pairs = HashSet::new();
616
617 for edge in &edges {
618 if edge.weight < 0.0 {
619 negative_edge_count += 1;
620 }
621 if edge.source_id == edge.target_id {
622 self_loop_count += 1;
623 continue;
624 }
625
626 directed_pairs.insert((edge.source_id.clone(), edge.target_id.clone()));
627 let (left, right) = if edge.source_id <= edge.target_id {
628 (edge.source_id.clone(), edge.target_id.clone())
629 } else {
630 (edge.target_id.clone(), edge.source_id.clone())
631 };
632 undirected_pairs.insert((left, right));
633 }
634
635 let expected_undirected_pairs = node_count.saturating_mul(node_count.saturating_sub(1)) / 2;
636 let expected_directed_pairs = node_count.saturating_mul(node_count.saturating_sub(1));
637 let density = if expected_undirected_pairs == 0 {
638 0.0
639 } else {
640 undirected_pairs.len() as f64 / expected_undirected_pairs as f64
641 };
642 let density_directed = if expected_directed_pairs == 0 {
643 0.0
644 } else {
645 directed_pairs.len() as f64 / expected_directed_pairs as f64
646 };
647
648 let is_empty = node_count == 0;
649 let is_connected = node_count <= 1 || connected.count == 1;
650 let is_weakly_connected = node_count <= 1 || weak.count == 1;
651 let is_strongly_connected = node_count <= 1 || strong.count == 1;
652 let is_cyclic = !cycle_result.cycles.is_empty();
653
654 Ok(RuntimeGraphPropertiesResult {
655 node_count,
656 edge_count,
657 self_loop_count,
658 negative_edge_count,
659 connected_component_count: connected.count,
660 weak_component_count: weak.count,
661 strong_component_count: strong.count,
662 is_empty,
663 is_connected,
664 is_weakly_connected,
665 is_strongly_connected,
666 is_complete: node_count <= 1 || undirected_pairs.len() == expected_undirected_pairs,
667 is_complete_directed: node_count <= 1
668 || directed_pairs.len() == expected_directed_pairs,
669 is_cyclic,
670 is_circular: is_cyclic,
671 is_acyclic: !is_cyclic,
672 is_tree: node_count > 0 && is_connected && undirected_pairs.len() + 1 == node_count,
673 density,
674 density_directed,
675 })
676 }
677}