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(&self, profile: &SparsityProfile, n: usize) -> ComplexityEstimate;
43
44    /// Return the algorithm identifier for this engine.
45    fn algorithm(&self) -> Algorithm;
46}
47
48/// Extended trait for solvers that operate on graph Laplacian systems.
49///
50/// A graph Laplacian `L = D - A` arises naturally in spectral graph theory.
51/// Solvers implementing this trait can exploit Laplacian structure (e.g.
52/// guaranteed positive semi-definiteness, kernel spanned by the all-ones
53/// vector) for faster convergence.
54pub trait SparseLaplacianSolver: SolverEngine {
55    /// Solve `L x = b` where `L` is a graph Laplacian.
56    ///
57    /// The solver may add a small regulariser to handle the rank-deficient
58    /// case (connected component with zero eigenvalue).
59    ///
60    /// # Errors
61    ///
62    /// Returns [`SolverError`] on failure.
63    fn solve_laplacian(
64        &self,
65        laplacian: &CsrMatrix<f64>,
66        rhs: &[f64],
67        budget: &ComputeBudget,
68    ) -> Result<SolverResult, SolverError>;
69
70    /// Compute the effective resistance between two nodes.
71    ///
72    /// Effective resistance `R(s, t) = (e_s - e_t)^T L^+ (e_s - e_t)` is
73    /// a fundamental quantity in spectral graph theory.
74    fn effective_resistance(
75        &self,
76        laplacian: &CsrMatrix<f64>,
77        source: usize,
78        target: usize,
79        budget: &ComputeBudget,
80    ) -> Result<f64, SolverError>;
81}
82
83/// Trait for sublinear-time Personalized PageRank (PPR) algorithms.
84///
85/// PPR is central to nearest-neighbour search in large graphs. Algorithms
86/// implementing this trait run in time proportional to the output size
87/// rather than the full graph size.
88pub trait SublinearPageRank: Send + Sync {
89    /// Compute a sparse approximate PPR vector from a single source node.
90    ///
91    /// # Arguments
92    ///
93    /// * `matrix` - column-stochastic transition matrix (or CSR adjacency).
94    /// * `source` - index of the source (seed) node.
95    /// * `alpha` - teleportation probability (typically 0.15).
96    /// * `epsilon` - approximation tolerance; controls output sparsity.
97    ///
98    /// # Returns
99    ///
100    /// A vector of `(node_index, ppr_value)` pairs whose values sum to
101    /// approximately 1.
102    ///
103    /// # Errors
104    ///
105    /// Returns [`SolverError`] on invalid input or budget exhaustion.
106    fn ppr(
107        &self,
108        matrix: &CsrMatrix<f64>,
109        source: usize,
110        alpha: f64,
111        epsilon: f64,
112    ) -> Result<Vec<(usize, f64)>, SolverError>;
113
114    /// Compute PPR from a distribution over seed nodes rather than a single
115    /// source.
116    ///
117    /// # Arguments
118    ///
119    /// * `matrix` - column-stochastic transition matrix.
120    /// * `seeds` - `(node_index, weight)` pairs forming the seed distribution.
121    /// * `alpha` - teleportation probability.
122    /// * `epsilon` - approximation tolerance.
123    ///
124    /// # Errors
125    ///
126    /// Returns [`SolverError`] on invalid input or budget exhaustion.
127    fn ppr_multi_seed(
128        &self,
129        matrix: &CsrMatrix<f64>,
130        seeds: &[(usize, f64)],
131        alpha: f64,
132        epsilon: f64,
133    ) -> Result<Vec<(usize, f64)>, SolverError>;
134}
ruvector_solver/traits.rs

ruvector_solver/
traits.rs
