uni_algo/algo/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4//! Graph Algorithm Engine
5//!
6//! This module provides native graph algorithm implementations for Uni.
7//!
8//! # Architecture
9//!
10//! Two execution paths are supported:
11//!
12//! - **DirectTraversal**: Zero-copy traversal on `AdjacencyManager` + `L0Buffer`.
13//!   Best for light algorithms (BFS, single shortest path).
14//!
15//! - **GraphProjection**: Materialized dense CSR for heavy algorithms.
16//!   Best for iterative algorithms (PageRank, WCC, Louvain).
17//!
18//! # Example
19//!
20//! ```ignore
21//! use uni_db::algo::{ProjectionBuilder, PageRank, Algorithm};
22//!
23//! // Build projection
24//! let projection = ProjectionBuilder::new(storage, cache, l0)
25//!     .node_labels(&["Person"])
26//!     .edge_types(&["KNOWS"])
27//!     .include_reverse(true)
28//!     .build()
29//!     .await?;
30//!
31//! // Run algorithm
32//! let result = PageRank::run(&projection, Default::default());
33//! ```
34
35mod id_map;
36pub mod projection;
37mod traversal;
38
39pub mod algorithms;
40pub mod cypher;
41pub mod procedure_template;
42pub mod procedures;
43
44pub use id_map::IdMap;
45pub use projection::{GraphProjection, ProjectionBuilder, ProjectionConfig};
46pub use traversal::{BfsIterator, DirectTraversal, Path};
47
48#[cfg(test)]
49pub mod test_utils;
50
51use std::collections::HashMap;
52use std::sync::Arc;
53
54/// Algorithm registry for procedure dispatch
55pub struct AlgorithmRegistry {
56    procedures: HashMap<String, Arc<dyn procedures::AlgoProcedure>>,
57}
58
59impl AlgorithmRegistry {
60    pub fn new() -> Self {
61        let mut registry = Self {
62            procedures: HashMap::default(),
63        };
64
65        // Register built-in algorithms
66        registry.register(cypher::PageRankProcedure::default());
67        registry.register(cypher::WccProcedure::default());
68        registry.register(cypher::ShortestPathProcedure);
69        registry.register(cypher::LouvainProcedure::default());
70        registry.register(cypher::LabelPropagationProcedure::default());
71        registry.register(cypher::BetweennessProcedure::default());
72        registry.register(cypher::NodeSimilarityProcedure::default());
73        registry.register(cypher::ClosenessProcedure::default());
74        registry.register(cypher::TriangleCountProcedure::default());
75        registry.register(cypher::KCoreProcedure::default());
76        registry.register(cypher::RandomWalkProcedure::default());
77        registry.register(cypher::AllPairsShortestPathProcedure::default());
78        registry.register(cypher::SccProcedure::default());
79        registry.register(cypher::TopologicalSortProcedure::default());
80        registry.register(cypher::CycleDetectionProcedure::default());
81        registry.register(cypher::BipartiteCheckProcedure::default());
82        registry.register(cypher::BridgesProcedure::default());
83        registry.register(cypher::ArticulationPointsProcedure::default());
84        registry.register(cypher::AStarProcedure);
85        registry.register(cypher::BellmanFordProcedure::default());
86        registry.register(cypher::BidirectionalDijkstraProcedure::default());
87        registry.register(cypher::KShortestPathsProcedure::default());
88        registry.register(cypher::MstProcedure::default());
89        registry.register(cypher::MaxMatchingProcedure::default());
90        registry.register(cypher::DinicProcedure::default());
91        registry.register(cypher::FordFulkersonProcedure::default());
92        registry.register(cypher::GraphMetricsProcedure::default());
93        registry.register(cypher::DiameterProcedure::default());
94        registry.register(cypher::DegreeCentralityProcedure::default());
95        registry.register(cypher::HarmonicCentralityProcedure::default());
96        registry.register(cypher::EigenvectorCentralityProcedure::default());
97        registry.register(cypher::KatzCentralityProcedure::default());
98        registry.register(cypher::MaximalCliquesProcedure::default());
99        registry.register(cypher::AllSimplePathsProcedure);
100        registry.register(cypher::ElementaryCircuitsProcedure::default());
101        registry.register(cypher::GraphColoringProcedure::default());
102
103        registry
104    }
105
106    pub fn register<P: procedures::AlgoProcedure + 'static>(&mut self, proc: P) {
107        self.procedures
108            .insert(proc.name().to_string(), Arc::new(proc));
109    }
110
111    pub fn get(&self, name: &str) -> Option<Arc<dyn procedures::AlgoProcedure>> {
112        self.procedures.get(name).cloned()
113    }
114
115    pub fn list(&self) -> Vec<&str> {
116        self.procedures.keys().map(|s| s.as_str()).collect()
117    }
118}
119
120impl Default for AlgorithmRegistry {
121    fn default() -> Self {
122        Self::new()
123    }
124}
125
126/// Configuration for algorithm execution
127#[derive(Debug, Clone)]
128pub struct AlgorithmConfig {
129    /// Maximum memory for all projections (bytes)
130    pub max_projection_memory: usize,
131    /// Maximum vertices per projection
132    pub max_vertices: usize,
133    /// Warn if L0 exceeds this fraction of graph
134    pub l0_warning_threshold: f64,
135}
136
137impl Default for AlgorithmConfig {
138    fn default() -> Self {
139        Self {
140            max_projection_memory: 1 << 30, // 1 GB
141            max_vertices: 100_000_000,      // 100M
142            l0_warning_threshold: 0.1,      // 10%
143        }
144    }
145}
uni_algo/algo/mod.rs

uni_algo/algo/
mod.rs
