ruvector_sparsifier/
traits.rs

1//! Trait definitions for the sparsifier framework.
2//!
3//! These traits allow pluggable strategies for backbone maintenance,
4//! importance scoring, and the sparsifier itself.
5
6use crate::error::Result;
7use crate::graph::SparseGraph;
8use crate::types::{AuditResult, EdgeImportance, SparsifierStats};
9
10// ---------------------------------------------------------------------------
11// Sparsifier trait
12// ---------------------------------------------------------------------------
13
14/// A dynamic spectral sparsifier that maintains a compressed shadow graph
15/// preserving the Laplacian energy of the original within `(1 +/- epsilon)`.
16pub trait Sparsifier: Send + Sync {
17    /// Insert an edge into the full graph and update the sparsifier.
18    fn insert_edge(&mut self, u: usize, v: usize, weight: f64) -> Result<()>;
19
20    /// Delete an edge from the full graph and update the sparsifier.
21    fn delete_edge(&mut self, u: usize, v: usize) -> Result<()>;
22
23    /// Run a spectral audit comparing the sparsifier against the full graph.
24    fn audit(&self) -> AuditResult;
25
26    /// Rebuild the sparsifier around specific vertices.
27    fn rebuild_local(&mut self, nodes: &[usize]) -> Result<()>;
28
29    /// Fully reconstruct the sparsifier from scratch.
30    fn rebuild_full(&mut self) -> Result<()>;
31
32    /// Return a reference to the current sparsifier graph.
33    fn sparsifier(&self) -> &SparseGraph;
34
35    /// Return the current compression ratio.
36    fn compression_ratio(&self) -> f64;
37
38    /// Return the current statistics.
39    fn stats(&self) -> &SparsifierStats;
40}
41
42// ---------------------------------------------------------------------------
43// Importance scorer trait
44// ---------------------------------------------------------------------------
45
46/// Strategy for scoring the importance of edges.
47///
48/// Higher importance means the edge is more critical for preserving
49/// spectral properties and should be sampled with higher probability.
50pub trait ImportanceScorer: Send + Sync {
51    /// Score a single edge.
52    fn score(&self, graph: &SparseGraph, u: usize, v: usize, weight: f64) -> EdgeImportance;
53
54    /// Score all edges in the graph, returning a vector of importance scores.
55    fn score_all(&self, graph: &SparseGraph) -> Vec<EdgeImportance>;
56}
57
58// ---------------------------------------------------------------------------
59// Backbone strategy trait
60// ---------------------------------------------------------------------------
61
62/// Strategy for maintaining a backbone (spanning forest) that ensures
63/// global connectivity in the sparsifier.
64pub trait BackboneStrategy: Send + Sync {
65    /// Insert an edge, potentially adding it to the backbone.
66    ///
67    /// Returns `true` if the edge was added to the backbone forest.
68    fn insert_edge(&mut self, u: usize, v: usize, weight: f64) -> bool;
69
70    /// Delete an edge, repairing the backbone if needed.
71    ///
72    /// Returns `true` if the backbone was modified.
73    fn delete_edge(&mut self, u: usize, v: usize, weight: f64) -> bool;
74
75    /// Check whether an edge is currently in the backbone.
76    fn is_backbone_edge(&self, u: usize, v: usize) -> bool;
77
78    /// Return the number of connected components.
79    fn num_components(&self) -> usize;
80
81    /// Check whether two vertices are in the same component.
82    fn connected(&mut self, u: usize, v: usize) -> bool;
83
84    /// Return the number of edges in the backbone.
85    fn backbone_edge_count(&self) -> usize;
86
87    /// Ensure the backbone can accommodate at least `n` vertices.
88    fn ensure_capacity(&mut self, n: usize);
89}
ruvector_sparsifier/traits.rs

ruvector_sparsifier/
traits.rs
