ruvector_solver/
traits.rs

1//! Solver trait hierarchy.
2//!
3//! All solver algorithms implement [`SolverEngine`]. Specialised traits
4//! ([`SparseLaplacianSolver`], [`SublinearPageRank`]) extend it with
5//! domain-specific operations.
6
7use crate::error::SolverError;
8use crate::types::{
9    Algorithm, ComplexityEstimate, ComputeBudget, CsrMatrix, SolverResult, SparsityProfile,
10};
11
12/// Core trait that every solver algorithm must implement.
13///
14/// A `SolverEngine` accepts a sparse matrix system and a compute budget,
15/// returning either a [`SolverResult`] or a structured [`SolverError`].
16pub trait SolverEngine: Send + Sync {
17    /// Solve the linear system `A x = b` (or the equivalent iterative
18    /// problem) subject to the given compute budget.
19    ///
20    /// # Arguments
21    ///
22    /// * `matrix` - the sparse coefficient matrix.
23    /// * `rhs` - the right-hand side vector `b`.
24    /// * `budget` - resource limits for this invocation.
25    ///
26    /// # Errors
27    ///
28    /// Returns [`SolverError`] on non-convergence, numerical issues, budget
29    /// exhaustion, or invalid input.
30    fn solve(
31        &self,
32        matrix: &CsrMatrix<f64>,
33        rhs: &[f64],
34        budget: &ComputeBudget,
35    ) -> Result<SolverResult, SolverError>;
36
37    /// Estimate the computational cost of solving the given system without
38    /// actually performing the solve.
39    ///
40    /// Implementations should use the [`SparsityProfile`] to make a fast,
41    /// heuristic prediction.
42    fn estimate_complexity(
43        &self,
44        profile: &SparsityProfile,
45        n: usize,
46    ) -> ComplexityEstimate;
47
48    /// Return the algorithm identifier for this engine.
49    fn algorithm(&self) -> Algorithm;
50}
51
52/// Extended trait for solvers that operate on graph Laplacian systems.
53///
54/// A graph Laplacian `L = D - A` arises naturally in spectral graph theory.
55/// Solvers implementing this trait can exploit Laplacian structure (e.g.
56/// guaranteed positive semi-definiteness, kernel spanned by the all-ones
57/// vector) for faster convergence.
58pub trait SparseLaplacianSolver: SolverEngine {
59    /// Solve `L x = b` where `L` is a graph Laplacian.
60    ///
61    /// The solver may add a small regulariser to handle the rank-deficient
62    /// case (connected component with zero eigenvalue).
63    ///
64    /// # Errors
65    ///
66    /// Returns [`SolverError`] on failure.
67    fn solve_laplacian(
68        &self,
69        laplacian: &CsrMatrix<f64>,
70        rhs: &[f64],
71        budget: &ComputeBudget,
72    ) -> Result<SolverResult, SolverError>;
73
74    /// Compute the effective resistance between two nodes.
75    ///
76    /// Effective resistance `R(s, t) = (e_s - e_t)^T L^+ (e_s - e_t)` is
77    /// a fundamental quantity in spectral graph theory.
78    fn effective_resistance(
79        &self,
80        laplacian: &CsrMatrix<f64>,
81        source: usize,
82        target: usize,
83        budget: &ComputeBudget,
84    ) -> Result<f64, SolverError>;
85}
86
87/// Trait for sublinear-time Personalized PageRank (PPR) algorithms.
88///
89/// PPR is central to nearest-neighbour search in large graphs. Algorithms
90/// implementing this trait run in time proportional to the output size
91/// rather than the full graph size.
92pub trait SublinearPageRank: Send + Sync {
93    /// Compute a sparse approximate PPR vector from a single source node.
94    ///
95    /// # Arguments
96    ///
97    /// * `matrix` - column-stochastic transition matrix (or CSR adjacency).
98    /// * `source` - index of the source (seed) node.
99    /// * `alpha` - teleportation probability (typically 0.15).
100    /// * `epsilon` - approximation tolerance; controls output sparsity.
101    ///
102    /// # Returns
103    ///
104    /// A vector of `(node_index, ppr_value)` pairs whose values sum to
105    /// approximately 1.
106    ///
107    /// # Errors
108    ///
109    /// Returns [`SolverError`] on invalid input or budget exhaustion.
110    fn ppr(
111        &self,
112        matrix: &CsrMatrix<f64>,
113        source: usize,
114        alpha: f64,
115        epsilon: f64,
116    ) -> Result<Vec<(usize, f64)>, SolverError>;
117
118    /// Compute PPR from a distribution over seed nodes rather than a single
119    /// source.
120    ///
121    /// # Arguments
122    ///
123    /// * `matrix` - column-stochastic transition matrix.
124    /// * `seeds` - `(node_index, weight)` pairs forming the seed distribution.
125    /// * `alpha` - teleportation probability.
126    /// * `epsilon` - approximation tolerance.
127    ///
128    /// # Errors
129    ///
130    /// Returns [`SolverError`] on invalid input or budget exhaustion.
131    fn ppr_multi_seed(
132        &self,
133        matrix: &CsrMatrix<f64>,
134        seeds: &[(usize, f64)],
135        alpha: f64,
136        epsilon: f64,
137    ) -> Result<Vec<(usize, f64)>, SolverError>;
138}
ruvector_solver/traits.rs

ruvector_solver/
traits.rs
