Struct SpectralSampler 

pub struct SpectralSampler {
    pub epsilon: f64,
}

Samples edges from a graph proportional to their spectral importance.

The sampling probability for edge e = (u, v, w) is:

p(e) = min(1, C * score(e) * log(n) / epsilon^2)

where C is a normalisation constant chosen so the expected number of sampled edges matches budget. Kept edges are reweighted by w / p(e) to make the sparsifier an unbiased estimator of the Laplacian.

Fields

epsilon: f64

Approximation parameter.

Implementations

impl SpectralSampler

pub fn new(epsilon: f64) -> Self

Create a new sampler with the given epsilon.

pub fn sample_edges( &self, scores: &[EdgeImportance], budget: usize, backbone_edges: &HashSet<(usize, usize)>, ) -> SparseGraph

Sample edges from graph using the provided importance scores, returning a new SparseGraph with at most budget edges.

Backbone edges (if any) should be marked in backbone_edges; they are always included and reweighted to weight * 1.0 (kept as-is).

pub fn sample_single_edge( &self, importance: &EdgeImportance, n_vertices: usize, total_importance: f64, budget: usize, ) -> Option<(usize, usize, f64)>

Incrementally add a single edge to the sparsifier, deciding whether to keep it based on its importance.

Trait Implementations

impl Clone for SpectralSampler

fn clone(&self) -> SpectralSampler

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SpectralSampler

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SpectralSampler

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Serialize for SpectralSampler

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.