perspt_sdk/
spectral.rs

1//! Spectral energy-slope constant `mu` (PSP-8 System 2 / Gate G).
2//!
3//! For the quadratic residual energy `V(x) = x^T A x` with `A = B^T W B`, the
4//! energy-slope constant `mu = 2 * lambda_min+(A)` is combinatorial rather than
5//! embedding-dependent. In the identity-restriction case `A` reduces to the
6//! weighted Laplacian of the verification graph and `mu` is twice its algebraic
7//! connectivity (Fiedler value).
8//!
9//! `mu` is a diagnostic, not an input to the acceptance gate. It SHALL be
10//! computed off the critical path and SHALL NOT block dispatch or the gate.
11//! This module is therefore a pure, side-effect-free computation a runtime can
12//! schedule on graph-revision commit or asynchronously.
13
14use nalgebra::DMatrix;
15use serde::{Deserialize, Serialize};
16
17use crate::error::{check_positive_finite, Result, SdkError};
18
19/// One weighted edge of the verification graph. An edge `(i, j)` couples the
20/// local states of two nodes/verifiers; its weight is the residual weight
21/// `w_e > 0`.
22#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
23pub struct VerificationEdge {
24    pub src: usize,
25    pub dst: usize,
26    pub weight: f64,
27}
28
29impl VerificationEdge {
30    pub fn new(src: usize, dst: usize, weight: f64) -> Self {
31        Self { src, dst, weight }
32    }
33}
34
35/// A verification graph over `node_count` local-state components.
36#[derive(Debug, Clone, Default, PartialEq, Serialize, Deserialize)]
37pub struct VerificationGraph {
38    pub node_count: usize,
39    pub edges: Vec<VerificationEdge>,
40}
41
42impl VerificationGraph {
43    pub fn new(node_count: usize) -> Self {
44        Self {
45            node_count,
46            edges: Vec::new(),
47        }
48    }
49
50    pub fn with_edge(mut self, src: usize, dst: usize, weight: f64) -> Self {
51        self.edges.push(VerificationEdge::new(src, dst, weight));
52        self
53    }
54
55    pub fn add_edge(&mut self, src: usize, dst: usize, weight: f64) {
56        self.edges.push(VerificationEdge::new(src, dst, weight));
57    }
58
59    /// Build the weighted graph Laplacian `A = B^T W B` (identity-restriction
60    /// case), an `n x n` symmetric positive-semidefinite matrix.
61    fn laplacian(&self) -> Result<DMatrix<f64>> {
62        if self.node_count == 0 {
63            return Err(SdkError::Spectral("verification graph has no nodes".into()));
64        }
65        let n = self.node_count;
66        let mut a = DMatrix::<f64>::zeros(n, n);
67        for e in &self.edges {
68            if e.src >= n || e.dst >= n {
69                return Err(SdkError::Spectral(format!(
70                    "edge ({}, {}) out of range for {} nodes",
71                    e.src, e.dst, n
72                )));
73            }
74            if e.src == e.dst {
75                return Err(SdkError::Spectral(format!("self-loop at node {}", e.src)));
76            }
77            check_positive_finite(e.weight, "edge weight")?;
78            let w = e.weight;
79            a[(e.src, e.src)] += w;
80            a[(e.dst, e.dst)] += w;
81            a[(e.src, e.dst)] -= w;
82            a[(e.dst, e.src)] -= w;
83        }
84        Ok(a)
85    }
86
87    /// Sorted ascending eigenvalues of the Laplacian.
88    fn eigenvalues_sorted(&self) -> Result<Vec<f64>> {
89        let a = self.laplacian()?;
90        // The Laplacian is symmetric; use the symmetric eigensolver.
91        let mut eigs: Vec<f64> = a.symmetric_eigenvalues().iter().copied().collect();
92        eigs.sort_by(|x, y| x.partial_cmp(y).unwrap_or(std::cmp::Ordering::Equal));
93        Ok(eigs)
94    }
95
96    /// Smallest non-zero eigenvalue `lambda_min+(A)` of the Laplacian.
97    ///
98    /// Returns `None` when the graph is disconnected or empty of edges (the
99    /// spectral gap is then zero, so `mu` is not informative). Eigenvalues
100    /// within `tol` of zero are treated as zero.
101    pub fn smallest_nonzero_eigenvalue(&self, tol: f64) -> Result<Option<f64>> {
102        let eigs = self.eigenvalues_sorted()?;
103        Ok(eigs.into_iter().find(|&v| v > tol))
104    }
105
106    /// The spectral energy-slope constant `mu = 2 * lambda_min+(A)`.
107    ///
108    /// Returns `None` for a disconnected verification graph, where the gap is
109    /// zero and `mu` is uninformative (a disconnected verifier component cannot
110    /// be driven to consensus by the others).
111    pub fn mu(&self, tol: f64) -> Result<Option<f64>> {
112        Ok(self
113            .smallest_nonzero_eigenvalue(tol)?
114            .map(|lambda| 2.0 * lambda))
115    }
116
117    /// Algebraic connectivity (Fiedler value) — the smallest non-zero
118    /// eigenvalue; `mu = 2 * fiedler`.
119    pub fn fiedler_value(&self, tol: f64) -> Result<Option<f64>> {
120        self.smallest_nonzero_eigenvalue(tol)
121    }
122
123    /// Change in `mu` produced by adding a candidate verifier edge.
124    ///
125    /// An independent verifier that raises the spectral gap yields a positive
126    /// delta; a redundant verifier that does not yields ~0. Used to distinguish
127    /// independent from redundant verifiers (PSP-8 System 2).
128    pub fn edge_mu_sensitivity(
129        &self,
130        src: usize,
131        dst: usize,
132        weight: f64,
133        tol: f64,
134    ) -> Result<f64> {
135        let before = self.mu(tol)?.unwrap_or(0.0);
136        let mut candidate = self.clone();
137        candidate.add_edge(src, dst, weight);
138        let after = candidate.mu(tol)?.unwrap_or(0.0);
139        Ok(after - before)
140    }
141}
142
143#[cfg(test)]
144mod tests {
145    use super::*;
146
147    const TOL: f64 = 1e-9;
148
149    #[test]
150    fn path_graph_has_expected_fiedler_value() {
151        // Unweighted path on 3 nodes: Laplacian eigenvalues are 0, 1, 3.
152        let g = VerificationGraph::new(3)
153            .with_edge(0, 1, 1.0)
154            .with_edge(1, 2, 1.0);
155        let fiedler = g.fiedler_value(TOL).unwrap().unwrap();
156        assert!((fiedler - 1.0).abs() < 1e-6, "fiedler={fiedler}");
157        let mu = g.mu(TOL).unwrap().unwrap();
158        assert!((mu - 2.0).abs() < 1e-6, "mu={mu}");
159    }
160
161    #[test]
162    fn complete_triangle_connectivity() {
163        // Unweighted triangle: eigenvalues 0, 3, 3 -> fiedler = 3.
164        let g = VerificationGraph::new(3)
165            .with_edge(0, 1, 1.0)
166            .with_edge(1, 2, 1.0)
167            .with_edge(0, 2, 1.0);
168        let fiedler = g.fiedler_value(TOL).unwrap().unwrap();
169        assert!((fiedler - 3.0).abs() < 1e-6, "fiedler={fiedler}");
170    }
171
172    #[test]
173    fn disconnected_graph_has_no_spectral_gap() {
174        // Two isolated edges over 4 nodes -> two zero eigenvalues, but the
175        // second smallest is still 0 -> disconnected.
176        let g = VerificationGraph::new(4)
177            .with_edge(0, 1, 1.0)
178            .with_edge(2, 3, 1.0);
179        // smallest nonzero exists (the within-component value) but the graph is
180        // disconnected: there are two zero eigenvalues. We detect disconnection
181        // by counting zeros.
182        let eigs = g.eigenvalues_sorted().unwrap();
183        let zeros = eigs.iter().filter(|&&v| v.abs() <= TOL).count();
184        assert_eq!(
185            zeros, 2,
186            "disconnected graph has multiplicity-2 zero eigenvalue"
187        );
188    }
189
190    #[test]
191    fn independent_verifier_raises_mu_more_than_redundant() {
192        // Base: path 0-1-2.
193        let g = VerificationGraph::new(3)
194            .with_edge(0, 1, 1.0)
195            .with_edge(1, 2, 1.0);
196        // Adding the closing edge 0-2 (independent cross-check) raises the gap.
197        let independent = g.edge_mu_sensitivity(0, 2, 1.0, TOL).unwrap();
198        // Strengthening an existing coupling 0-1 (redundant) raises it less.
199        let redundant = g.edge_mu_sensitivity(0, 1, 1.0, TOL).unwrap();
200        assert!(independent > 0.0);
201        assert!(
202            independent >= redundant,
203            "independent={independent} redundant={redundant}"
204        );
205    }
206
207    #[test]
208    fn weighted_edges_scale_gap() {
209        let g1 = VerificationGraph::new(2).with_edge(0, 1, 1.0);
210        let g2 = VerificationGraph::new(2).with_edge(0, 1, 2.0);
211        let m1 = g1.mu(TOL).unwrap().unwrap();
212        let m2 = g2.mu(TOL).unwrap().unwrap();
213        assert!((m2 - 2.0 * m1).abs() < 1e-6);
214    }
215
216    #[test]
217    fn rejects_self_loop_and_out_of_range() {
218        assert!(VerificationGraph::new(2)
219            .with_edge(0, 0, 1.0)
220            .mu(TOL)
221            .is_err());
222        assert!(VerificationGraph::new(2)
223            .with_edge(0, 5, 1.0)
224            .mu(TOL)
225            .is_err());
226    }
227}
perspt_sdk/spectral.rs

perspt_sdk/
spectral.rs
