Struct SparseGraph 

pub struct SparseGraph { /* private fields */ }

A weighted undirected graph with dynamic edge support.

Internally stores adjacency lists keyed by vertex index. Vertices are implicitly numbered 0..num_vertices. When an edge (u, v) is inserted with max(u, v) >= num_vertices, the vertex count grows automatically.

Thread safety

SparseGraph is not internally synchronised. Wrap it in parking_lot::RwLock for concurrent access (the sparsifier does this).

Implementations

impl SparseGraph

pub fn new() -> Self

Create an empty graph with no vertices.

pub fn with_capacity(n: usize) -> Self

Create an empty graph pre-allocated for n vertices.

pub fn from_edges(edges: &[(usize, usize, f64)]) -> Self

Build a graph from a list of weighted edges (u, v, weight).

Duplicate edges are silently overwritten with the last weight.

pub fn ensure_capacity(&mut self, n: usize)

Ensure the graph can represent at least n vertices.

pub fn num_vertices(&self) -> usize

Number of vertices (equal to the length of the adjacency array).

pub fn num_edges(&self) -> usize

Number of undirected edges.

pub fn total_weight(&self) -> f64

Sum of all edge weights (each undirected edge counted once).

pub fn degree(&self, u: usize) -> usize

Degree of vertex u (number of neighbours).

Returns 0 if u is out of bounds.

pub fn weighted_degree(&self, u: usize) -> f64

Weighted degree of vertex u (sum of incident edge weights).

Note: This iterates incident edges each call. For hot-path usage, consider caching the result externally.

pub fn neighbors(&self, u: usize) -> impl Iterator<Item = (usize, f64)> + '_

Iterator over neighbours of u yielding (v, weight).

Panics

Panics if u >= num_vertices().

pub fn edge_weight(&self, u: usize, v: usize) -> Option<f64>

Weight of the edge (u, v), or None if it does not exist.

pub fn has_edge(&self, u: usize, v: usize) -> bool

Check whether edge (u, v) exists.

pub fn edges(&self) -> impl Iterator<Item = (usize, usize, f64)> + '_

Iterate over all edges yielding (u, v, weight) with u < v.

pub fn insert_edge(&mut self, u: usize, v: usize, weight: f64) -> Result<()>

Insert an undirected edge (u, v) with the given weight.

The vertex set is automatically expanded if necessary.

Errors

• SparsifierError::InvalidWeight if weight is not positive/finite.
• SparsifierError::EdgeAlreadyExists if the edge is present.

pub fn insert_or_update_edge( &mut self, u: usize, v: usize, weight: f64, ) -> Result<Option<f64>>

Insert or overwrite an edge without returning an error on duplicates.

Returns the old weight if the edge already existed.

pub fn delete_edge(&mut self, u: usize, v: usize) -> Result<f64>

Delete the undirected edge (u, v).

Errors

Returns SparsifierError::EdgeNotFound if the edge does not exist.

pub fn update_weight( &mut self, u: usize, v: usize, new_weight: f64, ) -> Result<f64>

Update the weight of edge (u, v).

Errors

Returns an error if the edge does not exist or the weight is invalid.

pub fn clear(&mut self)

Remove all edges and vertices.

pub fn laplacian_quadratic_form(&self, x: &[f64]) -> f64

Compute the Laplacian quadratic form x^T L x.

For each edge (u, v, w): sum += w * (x[u] - x[v])^2

Panics

Panics if x.len() < num_vertices().

pub fn to_csr(&self) -> (Vec<usize>, Vec<usize>, Vec<f64>, usize)

Export to compressed sparse row (CSR) format.

Returns (row_ptr, col_indices, values, n) where n is the number of vertices. The CSR matrix represents the weighted adjacency matrix (symmetric, both directions stored).

pub fn from_csr( row_ptr: &[usize], col_indices: &[usize], values: &[f64], n: usize, ) -> Self

Import from compressed sparse row (CSR) format.

The CSR data is interpreted as a symmetric adjacency matrix. Only entries with col >= row are inserted to avoid double-counting.

Trait Implementations

impl Clone for SparseGraph

fn clone(&self) -> SparseGraph

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for SparseGraph

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

Formats the value using the given formatter.

impl Default for SparseGraph

fn default() -> Self

Returns the “default value” for a type.

impl<'de> Deserialize<'de> for SparseGraph

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

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Serialize for SparseGraph

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

where __S: Serializer,

Serialize this value into the given Serde serializer.