//! Numerical validation tests comparing scirs2-graph results with reference implementations
//!
//! These tests ensure that our algorithms produce numerically accurate results
//! by comparing with known correct values and other implementations.
use approx::{assert_abs_diff_eq, assert_relative_eq};
use rand::{rng, Rng};
use scirs2_core::error::CoreResult;
use scirs2_graph::{algorithms, generators, measures, spectral, DiGraph, Graph};
use std::collections::HashMap;
#[test]
#[allow(dead_code)]
fn test_pagerank_accuracy() -> CoreResult<()> {
// Test case 1: Simple graph with known PageRank values
let mut graph = DiGraph::new();
// Create a simple 4-node graph
// 0 -> 1, 2
// 1 -> 2
// 2 -> 0
// 3 -> 0, 1, 2
for i in 0..4 {
graph.add_node(i);
}
graph
.add_edge(0, 1, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(0, 2, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(1, 2, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(2, 0, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(3, 0, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(3, 1, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(3, 2, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
// Known PageRank values for damping factor 0.85
// Computed using NetworkX as reference
let expected_pagerank = vec![
0.3278149, // node 0
0.2645834, // node 1
0.3723684, // node 2
0.0352333, // node 3
];
let pagerank = algorithms::pagerank(&graph, 0.85, 1e-6, 100);
for (node, &expected) in expected_pagerank.iter().enumerate() {
let actual = pagerank[&node];
let diff = (actual - expected).abs();
assert!(
diff < 1e-5,
"PageRank for node {} differs from reference: expected {}, got {}, diff {}",
node,
expected,
actual,
diff
);
}
// Test case 2: Complete graph (all nodes should have equal PageRank)
let complete = generators::complete_graph(10)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
// Convert to DiGraph for pagerank
let mut complete_digraph = DiGraph::new();
for i in 0..10 {
complete_digraph.add_node(i);
}
for i in 0..10 {
for j in 0..10 {
if i != j {
complete_digraph
.add_edge(i, j, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
}
}
}
let pr_complete = algorithms::pagerank(&complete_digraph, 0.85, 1e-6, 100);
let expected_value = 1.0 / 10.0;
for i in 0..10 {
let actual = pr_complete[&i];
let diff = (actual - expected_value).abs();
assert!(
diff < 1e-6,
"Complete graph PageRank should be uniform: expected {}, got {}, diff {}",
expected_value,
actual,
diff
);
}
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_betweenness_centrality_accuracy() -> CoreResult<()> {
// Test case: Path graph
// In a path graph, the betweenness centrality follows a specific pattern
let path = generators::path_graph(5);
let bc = algorithms::betweenness_centrality(&path)?;
// Expected values for path graph of length 5
// Nodes: 0 -- 1 -- 2 -- 3 -- 4
let expected_bc = vec![
0.0, // node 0 (endpoint)
3.0, // node 1
4.0, // node 2 (center)
3.0, // node 3
0.0, // node 4 (endpoint)
];
for (node, &expected) in expected_bc.iter().enumerate() {
assert_abs_diff_eq!(
bc[&node],
expected,
epsilon = 1e-10,
"Betweenness centrality for node {} in path graph",
node
);
}
// Test case: Star graph
// Center node has maximum betweenness
let star = generators::star_graph(6);
let bc_star = algorithms::betweenness_centrality(&star)?;
// Center node (0) should have betweenness = (n-1)(n-2)/2
let n = 6;
let expected_center = ((n - 1) * (n - 2)) as f64 / 2.0;
assert_abs_diff_eq!(
bc_star[&0],
expected_center,
epsilon = 1e-10,
"Star graph center betweenness"
);
// All other nodes should have 0 betweenness
for i in 1..n {
assert_abs_diff_eq!(
bc_star[&i],
0.0,
epsilon = 1e-10,
"Star graph leaf betweenness"
);
}
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_clustering_coefficient_accuracy() -> CoreResult<()> {
// Test case 1: Complete graph (clustering coefficient = 1)
let complete = generators::complete_graph(5);
let cc = measures::clustering_coefficient(&complete)?;
assert_abs_diff_eq!(
cc,
1.0,
epsilon = 1e-10,
"Complete graph should have clustering coefficient of 1"
);
// Test case 2: Tree (clustering coefficient = 0)
let mut tree = Graph::new();
for i in 0..6 {
tree.add_node(i);
}
tree.add_edge(0, 1, 1.0)?;
tree.add_edge(0, 2, 1.0)?;
tree.add_edge(1, 3, 1.0)?;
tree.add_edge(1, 4, 1.0)?;
tree.add_edge(2, 5, 1.0)?;
let cc_tree = measures::clustering_coefficient(&tree)?;
assert_abs_diff_eq!(
cc_tree,
0.0,
epsilon = 1e-10,
"Tree should have clustering coefficient of 0"
);
// Test case 3: Specific graph with known clustering
let mut graph = Graph::new();
for i in 0..4 {
graph.add_node(i);
}
// Create a triangle with one additional edge
graph
.add_edge(0, 1, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(1, 2, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(2, 0, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(2, 3, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
let coefficients = measures::clustering_coefficient(&graph)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
let local_cc = coefficients.get(&2).copied().unwrap_or(0.0);
// Node 2 has 3 neighbors, with 1 triangle among them
// CC = 2 * triangles / (degree * (degree - 1)) = 2 * 1 / (3 * 2) = 1/3
let expected = 1.0 / 3.0;
let diff = (local_cc - expected).abs();
assert!(
diff < 1e-10,
"Local clustering coefficient calculation: expected {}, got {}, diff {}",
expected,
local_cc,
diff
);
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_shortest_path_accuracy() -> CoreResult<()> {
// Test weighted shortest paths
let mut graph = Graph::new();
for i in 0..5 {
graph.add_node(i);
}
// Create a graph where the shortest path is not the path with fewest edges
graph
.add_edge(0, 1, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(1, 2, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(2, 4, 1.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?; // Path 0->1->2->4 has length 3
graph
.add_edge(0, 3, 2.0)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
graph
.add_edge(3, 4, 0.5)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?; // Path 0->3->4 has length 2.5 (shorter)
let path_result = algorithms::dijkstra_path(&graph, &0, &4)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
let path = path_result.unwrap();
let expected_path = vec![0, 3, 4];
assert_eq!(
path.nodes, expected_path,
"Shortest path should choose lower weight path"
);
// Test all-pairs shortest paths
let distances = algorithms::floyd_warshall(&graph)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
let expected = 2.5;
let actual = distances[(0, 4)];
let diff = (actual - expected).abs();
assert!(
diff < 1e-10,
"Floyd-Warshall distance calculation: expected {}, got {}, diff {}",
expected,
actual,
diff
);
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_eigenvector_centrality_accuracy() -> CoreResult<()> {
// Test on a simple graph with known eigenvector centrality
let mut graph = Graph::new();
for i in 0..4 {
graph.add_node(i);
}
// Create a simple connected graph
graph.add_edge(0, 1, 1.0)?;
graph.add_edge(1, 2, 1.0)?;
graph.add_edge(2, 3, 1.0)?;
graph.add_edge(3, 0, 1.0)?;
graph.add_edge(1, 3, 1.0)?;
let ec = algorithms::eigenvector_centrality(&graph, Some(100), Some(1e-6))?;
// Verify properties of eigenvector centrality
// 1. All values should be positive for connected graph
for &value in ec.values() {
assert!(value > 0.0, "Eigenvector centrality should be positive");
}
// 2. Nodes 1 and 3 should have higher centrality (degree 3) than 0 and 2 (degree 2)
assert!(
ec[&1] > ec[&0] && ec[&3] > ec[&0],
"Higher degree nodes should have higher eigenvector centrality"
);
// 3. Sum of squares should be 1 (normalized)
let sum_squares: f64 = ec.values().map(|&v| v * v).sum();
assert_relative_eq!(
sum_squares,
1.0,
epsilon = 1e-6,
"Eigenvector centrality should be normalized"
);
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_spectral_calculations_accuracy() -> CoreResult<()> {
// Test Laplacian matrix calculation
let graph = generators::cycle_graph(4);
let laplacian = spectral::laplacian(&graph)?;
// For a cycle graph, the Laplacian should have specific structure
// Diagonal elements = 2 (degree of each node)
// Off-diagonal = -1 for connected nodes, 0 otherwise
for i in 0..4 {
assert_abs_diff_eq!(
laplacian[(i, i)],
2.0,
epsilon = 1e-10,
"Laplacian diagonal elements"
);
}
// Check off-diagonal elements
assert_abs_diff_eq!(laplacian[(0, 1)], -1.0, epsilon = 1e-10);
assert_abs_diff_eq!(laplacian[(1, 2)], -1.0, epsilon = 1e-10);
assert_abs_diff_eq!(laplacian[(2, 3)], -1.0, epsilon = 1e-10);
assert_abs_diff_eq!(laplacian[(3, 0)], -1.0, epsilon = 1e-10);
assert_abs_diff_eq!(laplacian[(0, 2)], 0.0, epsilon = 1e-10);
assert_abs_diff_eq!(laplacian[(1, 3)], 0.0, epsilon = 1e-10);
// Test spectral radius
let complete = generators::complete_graph(5);
let radius = spectral::spectral_radius(&complete)?;
// For complete graph K_n, the spectral radius is n-1
assert_abs_diff_eq!(
radius,
4.0,
epsilon = 1e-6,
"Complete graph spectral radius"
);
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_connected_components_accuracy() -> CoreResult<()> {
// Create a graph with known components
let mut graph = Graph::new();
for i in 0..8 {
graph.add_node(i);
}
// Component 1: {0, 1, 2}
graph.add_edge(0, 1, 1.0)?;
graph.add_edge(1, 2, 1.0)?;
// Component 2: {3, 4}
graph.add_edge(3, 4, 1.0)?;
// Component 3: {5}
// Node 5 is isolated
// Component 4: {6, 7}
graph.add_edge(6, 7, 1.0)?;
let components = algorithms::connected_components(&graph)?;
assert_eq!(components.len(), 4, "Should have 4 connected components");
// Verify component sizes
let mut sizes: Vec<usize> = components.iter().map(|c| c.len()).collect();
sizes.sort();
assert_eq!(sizes, vec![1, 2, 2, 3], "Component sizes should match");
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_minimum_spanning_tree_accuracy() -> CoreResult<()> {
// Create a weighted graph with known MST
let mut graph = Graph::new();
for i in 0..4 {
graph.add_node(i);
}
// Add edges with specific weights
graph.add_edge(0, 1, 1.0)?;
graph.add_edge(0, 2, 3.0)?;
graph.add_edge(0, 3, 4.0)?;
graph.add_edge(1, 2, 2.0)?;
graph.add_edge(2, 3, 5.0)?;
let mst = algorithms::minimum_spanning_tree(&graph)?;
// MST should have n-1 edges
assert_eq!(mst.len(), 3, "MST should have n-1 edges");
// Total weight of MST should be 1 + 2 + 4 = 7
let total_weight: f64 = mst.iter().map(|&(_, _, w)| w).sum();
assert_abs_diff_eq!(total_weight, 7.0, epsilon = 1e-10, "MST total weight");
// Verify specific edges are in MST
let mst_edges: Vec<(usize, usize)> = mst
.iter()
.map(|&(u, v, _)| if u < v { (u, v) } else { (v, u) })
.collect();
assert!(mst_edges.contains(&(0, 1)), "Edge (0,1) should be in MST");
assert!(mst_edges.contains(&(1, 2)), "Edge (1,2) should be in MST");
assert!(mst_edges.contains(&(0, 3)), "Edge (0,3) should be in MST");
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_max_flow_accuracy() -> CoreResult<()> {
// Create a flow network with known maximum flow
let mut graph = DiGraph::new();
for i in 0..6 {
graph.add_node(i);
}
// Classic example network
// Source: 0, Sink: 5
graph.add_edge(0, 1, 10.0)?;
graph.add_edge(0, 2, 10.0)?;
graph.add_edge(1, 2, 2.0)?;
graph.add_edge(1, 3, 4.0)?;
graph.add_edge(1, 4, 8.0)?;
graph.add_edge(2, 4, 9.0)?;
graph.add_edge(3, 5, 10.0)?;
graph.add_edge(4, 3, 6.0)?;
graph.add_edge(4, 5, 10.0)?;
// Maximum flow from 0 to 5 should be 19
let (max_flow, _) = algorithms::dinic_max_flow(&graph, 0, 5)?;
assert_abs_diff_eq!(max_flow, 19.0, epsilon = 1e-10, "Maximum flow value");
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_graph_density_accuracy() -> CoreResult<()> {
// Test various graph densities
// Complete graph: density = 1
let complete = generators::complete_graph(5);
let density_complete = measures::graph_density(&complete);
assert_abs_diff_eq!(
density_complete,
1.0,
epsilon = 1e-10,
"Complete graph density"
);
// Empty graph: density = 0
let mut empty = Graph::new();
for i in 0..5 {
empty.add_node(i);
}
let density_empty = measures::graph_density(&empty);
assert_abs_diff_eq!(density_empty, 0.0, epsilon = 1e-10, "Empty graph density");
// Cycle graph: density = n / (n(n-1)/2) = 2/n-1
let cycle = generators::cycle_graph(10);
let density_cycle = measures::graph_density(&cycle);
let expected_density = 2.0 / 9.0; // For n=10
assert_abs_diff_eq!(
density_cycle,
expected_density,
epsilon = 1e-10,
"Cycle graph density"
);
Ok(())
}
#[test]
#[allow(dead_code)]
fn test_katz_centrality_accuracy() -> CoreResult<()> {
// Test Katz centrality on a simple graph
let mut graph = Graph::new();
for i in 0..4 {
graph.add_node(i);
}
// Linear graph: 0 -- 1 -- 2 -- 3
graph.add_edge(0, 1, 1.0)?;
graph.add_edge(1, 2, 1.0)?;
graph.add_edge(2, 3, 1.0)?;
let alpha = 0.1; // Attenuation factor
let beta = 1.0; // Base centrality
let katz = measures::katz_centrality(&graph, alpha, beta)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
// Verify Katz centrality properties
// Central nodes (1, 2) should have higher centrality than endpoints (0, 3)
assert!(
katz[&1] > katz[&0] && katz[&2] > katz[&3],
"Central nodes should have higher Katz centrality"
);
// Due to symmetry, nodes 1 and 2 should have equal centrality
let diff = (katz[&1] - katz[&2]).abs();
assert!(
diff < 1e-6,
"Symmetric nodes should have equal Katz centrality: node 1 = {}, node 2 = {}, diff = {}",
katz[&1],
katz[&2],
diff
);
Ok(())
}
/// Test numerical stability for large graphs
#[test]
#[ignore] // Run with --ignored flag
#[allow(dead_code)]
fn test_large_graph_numerical_stability() -> CoreResult<()> {
// Generate a large random graph
let n = 1000;
let p = 0.01;
let mut rng = rng();
let graph = generators::erdos_renyi_graph(n, p, &mut rng)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
// Convert to DiGraph for pagerank
let mut digraph = DiGraph::new();
for i in 0..n {
digraph.add_node(i);
}
// Add edges from undirected graph as bidirectional edges
for edge in graph.edges() {
digraph
.add_edge(edge.source, edge.target, edge.weight)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
digraph
.add_edge(edge.target, edge.source, edge.weight)
.map_err(|e| scirs2_core::error::CoreError::from(e.to_string()))?;
}
// Test PageRank convergence
let pr1 = algorithms::pagerank(&digraph, 0.85, 1e-6, 50);
let pr2 = algorithms::pagerank(&digraph, 0.85, 1e-6, 100);
// Check that PageRank values are stable
let mut max_diff: f64 = 0.0;
for i in 0..n {
let diff = (pr1[&i] - pr2[&i]).abs();
max_diff = max_diff.max(diff);
}
assert!(
max_diff < 1e-6,
"PageRank should converge to stable values, max diff: {}",
max_diff
);
// Test that sum of PageRank values equals 1
let sum: f64 = pr2.values().sum();
assert_relative_eq!(
sum,
1.0,
epsilon = 1e-6,
"Sum of PageRank values should be 1"
);
Ok(())
}