#[must_use]
pub fn graph_laplacian(adjacency: &[f64], n: usize) -> Vec<f64> {
let mut laplacian = vec![0.0; n * n];
for i in 0..n {
let degree: f64 = (0..n).map(|j| adjacency[i * n + j]).sum();
laplacian[i * n + i] = degree;
for j in 0..n {
laplacian[i * n + j] -= adjacency[i * n + j];
}
}
laplacian
}
#[must_use]
pub fn belief_propagation_chain(
input_dist: &[f64],
transition_matrices: &[&[f64]],
layer_dims: &[usize],
) -> Vec<Vec<f64>> {
let mut distributions = Vec::with_capacity(layer_dims.len() + 1);
distributions.push(input_dist.to_vec());
let mut current = input_dist.to_vec();
for (k, trans) in transition_matrices.iter().enumerate() {
let in_dim = if k == 0 {
input_dist.len()
} else {
layer_dims[k - 1]
};
let out_dim = layer_dims[k];
let mut next = vec![0.0; out_dim];
for j in 0..out_dim {
for i in 0..in_dim {
next[j] = current[i].mul_add(trans[i * out_dim + j], next[j]);
}
}
let sum: f64 = next.iter().sum();
if sum > 1e-300 {
for v in &mut next {
*v /= sum;
}
}
distributions.push(next.clone());
current = next;
}
distributions
}
#[must_use]
pub fn disordered_laplacian(
laplacian: &[f64],
n: usize,
heterogeneity: &[f64],
disorder_strength: f64,
) -> Vec<f64> {
let mean: f64 = heterogeneity.iter().sum::<f64>() / n as f64;
let mut result = laplacian.to_vec();
for i in 0..n {
result[i * n + i] = disorder_strength.mul_add(heterogeneity[i] - mean, result[i * n + i]);
}
result
}
#[must_use]
pub fn effective_rank(eigenvalues: &[f64]) -> f64 {
let abs_vals: Vec<f64> = eigenvalues.iter().map(|&ev| ev.abs()).collect();
let total: f64 = abs_vals.iter().sum();
if total < 1e-300 {
return 0.0;
}
let mut entropy = 0.0;
for &v in &abs_vals {
let p = v / total;
if p > 1e-300 {
entropy = p.mul_add(-p.ln(), entropy);
}
}
entropy.exp()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_graph_laplacian_row_sums_zero() {
let adj = vec![0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0, 1.0, 0.0];
let l = graph_laplacian(&adj, 3);
for i in 0..3 {
let row_sum: f64 = (0..3).map(|j| l[i * 3 + j]).sum();
assert!(row_sum.abs() < 1e-14, "row {i} sum = {row_sum}, expected 0");
}
}
#[test]
fn test_graph_laplacian_identity() {
let adj = vec![0.0, 1.0, 1.0, 0.0];
let l = graph_laplacian(&adj, 2);
assert!((l[0] - 1.0).abs() < 1e-14);
assert!((l[1] - (-1.0)).abs() < 1e-14);
assert!((l[2] - (-1.0)).abs() < 1e-14);
assert!((l[3] - 1.0).abs() < 1e-14);
}
#[test]
fn test_graph_laplacian_empty() {
let adj = vec![0.0, 0.0, 0.0, 0.0];
let l = graph_laplacian(&adj, 2);
assert_eq!(l, vec![0.0, 0.0, 0.0, 0.0]);
}
#[test]
fn test_effective_rank_full() {
let ev = vec![1.0, 1.0, 1.0, 1.0];
let r = effective_rank(&ev);
assert!((r - 4.0).abs() < 1e-10, "expected 4, got {r}");
}
#[test]
fn test_effective_rank_single() {
let ev = vec![1.0, 0.0, 0.0];
let r = effective_rank(&ev);
assert!((r - 1.0).abs() < 1e-10, "expected 1, got {r}");
}
#[test]
fn test_effective_rank_zero() {
let ev = vec![0.0, 0.0, 0.0];
let r = effective_rank(&ev);
assert!((r - 0.0).abs() < 1e-14, "expected 0, got {r}");
}
#[test]
fn test_belief_propagation_identity() {
let input = vec![0.5, 0.3, 0.2];
let identity = vec![1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0];
let trans = [identity.as_slice()];
let layer_dims = [3];
let dists = belief_propagation_chain(&input, &trans, &layer_dims);
assert_eq!(dists.len(), 2);
for (a, b) in dists[1].iter().zip(input.iter()) {
assert!(
(a - b).abs() < 1e-14,
"identity should preserve: {:?} vs {:?}",
dists[1],
input
);
}
}
#[test]
fn test_belief_propagation_two_layers() {
let input = vec![1.0, 0.0]; let t1 = vec![0.5, 0.5, 0.5, 0.5]; let t2 = vec![1.0, 0.0, 0.0, 1.0]; let trans = [t1.as_slice(), t2.as_slice()];
let layer_dims = [2, 2];
let dists = belief_propagation_chain(&input, &trans, &layer_dims);
assert_eq!(dists.len(), 3);
for d in &dists {
let sum: f64 = d.iter().sum();
assert!(
(sum - 1.0).abs() < 1e-14,
"distribution should sum to 1: {d:?} sum={sum}"
);
}
}
#[test]
fn test_belief_propagation_normalization() {
let input = vec![0.25, 0.25, 0.25, 0.25];
let t = vec![0.25; 16]; let trans = [t.as_slice()];
let layer_dims = [4];
let dists = belief_propagation_chain(&input, &trans, &layer_dims);
for d in &dists {
let sum: f64 = d.iter().sum();
assert!(
(sum - 1.0).abs() < 1e-14,
"distribution should sum to 1: {d:?} sum={sum}"
);
}
}
#[test]
fn test_disordered_laplacian_zero_strength() {
let l = vec![1.0, -1.0, -1.0, 1.0];
let h = vec![0.5, 1.5];
let result = disordered_laplacian(&l, 2, &h, 0.0);
assert_eq!(result, l);
}
#[test]
fn test_disordered_laplacian_symmetry() {
let l = vec![2.0, -1.0, 0.0, -1.0, 2.0, -1.0, 0.0, -1.0, 2.0];
let h = vec![0.1, 0.2, 0.3];
let result = disordered_laplacian(&l, 3, &h, 1.0);
assert!((result[1] - l[1]).abs() < 1e-14);
assert!((result[2] - l[2]).abs() < 1e-14);
assert!((result[3] - l[3]).abs() < 1e-14);
assert!((result[5] - l[5]).abs() < 1e-14);
assert!((result[6] - l[6]).abs() < 1e-14);
assert!((result[7] - l[7]).abs() < 1e-14);
}
#[test]
fn test_disordered_laplacian_centered() {
let l = vec![1.0, 0.0, 0.0, 1.0];
let h = [1.0, 2.0, 3.0]; let result = disordered_laplacian(&l, 2, &h[..2], 1.0);
let diag_adds: Vec<f64> = (0..2).map(|i| result[i * 2 + i] - l[i * 2 + i]).collect();
let sum_adds: f64 = diag_adds.iter().sum();
assert!(
sum_adds.abs() < 1e-14,
"centered disorder: diagonal additions should sum to 0, got {sum_adds}"
);
}
}