380 lines
11 KiB
Rust
380 lines
11 KiB
Rust
|
//! Integration Tests for Phase 4.3: Community Detection
|
||
|
|
//!
|
||
|
|
//! Tests community detection (Louvain algorithm) capabilities including:
|
||
|
|
//! - Community clustering
|
||
|
|
//! - Modularity optimization
|
||
|
|
//! - Community strength and density
|
||
|
|
//! - Graph structure analysis
|
||
|
|
|
||
|
|
#[cfg(test)]
|
||
|
|
mod tests {
|
||
|
|
/// Test: Community struct creation
|
||
|
|
#[test]
|
||
|
|
fn test_community_struct_creation() {
|
||
|
|
let community_id = 0;
|
||
|
|
let size = 5;
|
||
|
|
let modularity_contribution = 0.75;
|
||
|
|
|
||
|
|
assert!(community_id >= 0);
|
||
|
|
assert!(size > 0);
|
||
|
|
assert!(modularity_contribution >= 0.0 && modularity_contribution <= 1.0);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Community density calculation (0-1)
|
||
|
|
#[test]
|
||
|
|
fn test_community_density_fully_connected() {
|
||
|
|
// Fully connected triangle: 3 nodes, 3 edges
|
||
|
|
// Possible: 3 * 2 / 2 = 3
|
||
|
|
// Density: 3 / 3 = 1.0
|
||
|
|
let nodes = 3;
|
||
|
|
let actual_edges = 3;
|
||
|
|
let possible_edges = nodes * (nodes - 1) / 2;
|
||
|
|
|
||
|
|
let density = actual_edges as f32 / possible_edges as f32;
|
||
|
|
assert_eq!(density, 1.0);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Community density sparse graph
|
||
|
|
#[test]
|
||
|
|
fn test_community_density_sparse() {
|
||
|
|
// 5 nodes, 2 edges
|
||
|
|
// Possible: 5 * 4 / 2 = 10
|
||
|
|
// Density: 2 / 10 = 0.2
|
||
|
|
let nodes = 5;
|
||
|
|
let actual_edges = 2;
|
||
|
|
let possible_edges = nodes * (nodes - 1) / 2;
|
||
|
|
|
||
|
|
let density = actual_edges as f32 / possible_edges as f32;
|
||
|
|
assert!((density - 0.2).abs() < 0.001);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Community strength bounds (0-1)
|
||
|
|
#[test]
|
||
|
|
fn test_community_strength_bounds() {
|
||
|
|
let strengths = vec![0.0, 0.5, 1.0];
|
||
|
|
|
||
|
|
for strength in strengths {
|
||
|
|
let normalized = strength.max(0.0).min(1.0);
|
||
|
|
assert!(normalized >= 0.0 && normalized <= 1.0);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Modularity bounds (-1 to 1)
|
||
|
|
#[test]
|
||
|
|
fn test_modularity_bounds() {
|
||
|
|
let values = vec![-1.5, -0.5, 0.0, 0.5, 1.5];
|
||
|
|
|
||
|
|
for value in values {
|
||
|
|
let clamped = value.max(-1.0).min(1.0);
|
||
|
|
assert!(clamped >= -1.0 && clamped <= 1.0);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Min community size clamping (2-1000)
|
||
|
|
#[test]
|
||
|
|
fn test_min_community_size_clamping() {
|
||
|
|
let test_cases = vec![
|
||
|
|
(0, 2), // Too small → 2
|
||
|
|
(1, 2), // Too small → 2
|
||
|
|
(2, 2), // Valid → 2
|
||
|
|
(50, 50), // Valid → 50
|
||
|
|
(1000, 1000),// Valid → 1000
|
||
|
|
(2000, 1000),// Too large → 1000
|
||
|
|
];
|
||
|
|
|
||
|
|
for (input, expected) in test_cases {
|
||
|
|
let clamped = input.max(2).min(1000);
|
||
|
|
assert_eq!(clamped, expected);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Modularity threshold clamping (0.0001-0.1)
|
||
|
|
#[test]
|
||
|
|
fn test_modularity_threshold_clamping() {
|
||
|
|
let test_cases = vec![
|
||
|
|
(0.00001, 0.0001), // Too small → 0.0001
|
||
|
|
(0.0001, 0.0001), // Valid → 0.0001
|
||
|
|
(0.01, 0.01), // Valid → 0.01
|
||
|
|
(0.1, 0.1), // Valid → 0.1
|
||
|
|
(0.5, 0.1), // Too large → 0.1
|
||
|
|
];
|
||
|
|
|
||
|
|
for (input, expected) in test_cases {
|
||
|
|
let clamped = input.max(0.0001).min(0.1);
|
||
|
|
assert!((clamped - expected).abs() < 0.00001);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Average community size calculation
|
||
|
|
#[test]
|
||
|
|
fn test_average_community_size() {
|
||
|
|
let communities = vec![
|
||
|
|
(0, vec![0, 1, 2]), // Size 3
|
||
|
|
(1, vec![3, 4]), // Size 2
|
||
|
|
(2, vec![5, 6, 7, 8, 9]), // Size 5
|
||
|
|
];
|
||
|
|
|
||
|
|
let total_size: usize = communities.iter().map(|(_, m)| m.len()).sum();
|
||
|
|
let avg = total_size as f32 / communities.len() as f32;
|
||
|
|
|
||
|
|
assert!((avg - 3.333).abs() < 0.01); // (3 + 2 + 5) / 3 ≈ 3.33
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Total modularity sum
|
||
|
|
#[test]
|
||
|
|
fn test_total_modularity_sum() {
|
||
|
|
let contributions = vec![0.3, 0.25, 0.2, 0.15];
|
||
|
|
let total: f32 = contributions.iter().sum();
|
||
|
|
let clamped = total.max(-1.0).min(1.0);
|
||
|
|
|
||
|
|
assert!((clamped - 0.9).abs() < 0.001);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Community count with size threshold
|
||
|
|
#[test]
|
||
|
|
fn test_community_count_filtering() {
|
||
|
|
let community_sizes = vec![1, 2, 3, 4, 5];
|
||
|
|
let min_size = 3;
|
||
|
|
|
||
|
|
let filtered: Vec<_> = community_sizes
|
||
|
|
.iter()
|
||
|
|
.filter(|&&size| size >= min_size)
|
||
|
|
.collect();
|
||
|
|
|
||
|
|
assert_eq!(filtered.len(), 3); // 3, 4, 5
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Entity to community mapping
|
||
|
|
#[test]
|
||
|
|
fn test_entity_community_mapping() {
|
||
|
|
let mut entity_to_community = std::collections::HashMap::new();
|
||
|
|
entity_to_community.insert("e1", 0);
|
||
|
|
entity_to_community.insert("e2", 0);
|
||
|
|
entity_to_community.insert("e3", 1);
|
||
|
|
entity_to_community.insert("e4", 1);
|
||
|
|
|
||
|
|
let comm_0: Vec<_> = entity_to_community
|
||
|
|
.iter()
|
||
|
|
.filter(|&(_, &comm)| comm == 0)
|
||
|
|
.map(|(&e, _)| e)
|
||
|
|
.collect();
|
||
|
|
|
||
|
|
assert_eq!(comm_0.len(), 2);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Edge weight normalization (0-1)
|
||
|
|
#[test]
|
||
|
|
fn test_edge_weight_normalization() {
|
||
|
|
let weights = vec![-0.5, 0.0, 0.5, 1.0, 1.5];
|
||
|
|
|
||
|
|
for weight in weights {
|
||
|
|
let normalized = weight.max(0.0).min(1.0);
|
||
|
|
assert!(normalized >= 0.0 && normalized <= 1.0);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Louvain iteration limit
|
||
|
|
#[test]
|
||
|
|
fn test_louvain_max_iterations() {
|
||
|
|
let max_iterations = 100;
|
||
|
|
let mut iteration = 0;
|
||
|
|
|
||
|
|
while iteration < max_iterations && iteration < 50 {
|
||
|
|
iteration += 1;
|
||
|
|
}
|
||
|
|
|
||
|
|
assert!(iteration <= max_iterations);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Empty graph handling
|
||
|
|
#[test]
|
||
|
|
fn test_empty_graph_community_detection() {
|
||
|
|
let entity_count = 0;
|
||
|
|
let edge_count = 0;
|
||
|
|
|
||
|
|
assert_eq!(entity_count, 0);
|
||
|
|
assert_eq!(edge_count, 0);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Single node graph (1 community)
|
||
|
|
#[test]
|
||
|
|
fn test_single_node_community() {
|
||
|
|
let nodes = 1;
|
||
|
|
let edges = 0;
|
||
|
|
|
||
|
|
assert_eq!(nodes, 1);
|
||
|
|
assert_eq!(edges, 0);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Disconnected graph (multiple components)
|
||
|
|
#[test]
|
||
|
|
fn test_disconnected_graph() {
|
||
|
|
// Component 1: 3 nodes
|
||
|
|
// Component 2: 2 nodes
|
||
|
|
// No edges between components
|
||
|
|
let component1_size = 3;
|
||
|
|
let component2_size = 2;
|
||
|
|
|
||
|
|
let total = component1_size + component2_size;
|
||
|
|
assert_eq!(total, 5);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Fully connected graph
|
||
|
|
#[test]
|
||
|
|
fn test_fully_connected_graph() {
|
||
|
|
let n = 5;
|
||
|
|
let possible_edges = n * (n - 1) / 2;
|
||
|
|
let actual_edges = possible_edges; // Fully connected
|
||
|
|
|
||
|
|
let density = actual_edges as f32 / possible_edges as f32;
|
||
|
|
assert_eq!(density, 1.0);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Modularity optimization direction
|
||
|
|
#[test]
|
||
|
|
fn test_modularity_gain_positive() {
|
||
|
|
let modularity_gain = 0.05; // Positive = improvement
|
||
|
|
let threshold = 0.001;
|
||
|
|
|
||
|
|
if modularity_gain > threshold {
|
||
|
|
assert!(true); // Should move entity
|
||
|
|
} else {
|
||
|
|
assert!(false);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Modularity gain negative
|
||
|
|
#[test]
|
||
|
|
fn test_modularity_gain_negative() {
|
||
|
|
let modularity_gain = -0.05; // Negative = no improvement
|
||
|
|
let threshold = 0.001;
|
||
|
|
|
||
|
|
if modularity_gain > threshold {
|
||
|
|
assert!(false); // Should NOT move entity
|
||
|
|
} else {
|
||
|
|
assert!(true);
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Nodes per community average
|
||
|
|
#[test]
|
||
|
|
fn test_average_nodes_per_community() {
|
||
|
|
let total_nodes = 100;
|
||
|
|
let community_count = 5;
|
||
|
|
|
||
|
|
let avg = total_nodes as f32 / community_count as f32;
|
||
|
|
assert_eq!(avg, 20.0);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Community size variance
|
||
|
|
#[test]
|
||
|
|
fn test_community_size_variance() {
|
||
|
|
let sizes = vec![5, 10, 15, 10, 5];
|
||
|
|
let mean = sizes.iter().sum::<usize>() as f32 / sizes.len() as f32;
|
||
|
|
|
||
|
|
let variance: f32 = sizes
|
||
|
|
.iter()
|
||
|
|
.map(|&s| ((s as f32 - mean).powi(2)))
|
||
|
|
.sum::<f32>()
|
||
|
|
/ sizes.len() as f32;
|
||
|
|
|
||
|
|
assert!(variance >= 0.0);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Response envelope structure
|
||
|
|
#[test]
|
||
|
|
fn test_community_detection_response() {
|
||
|
|
let response = serde_json::json!({
|
||
|
|
"entity_count": 100,
|
||
|
|
"edge_count": 250,
|
||
|
|
"communities": [],
|
||
|
|
"community_count": 0,
|
||
|
|
"total_modularity": 0.0,
|
||
|
|
"average_community_size": 0.0
|
||
|
|
});
|
||
|
|
|
||
|
|
assert!(response["entity_count"].is_number());
|
||
|
|
assert!(response["communities"].is_array());
|
||
|
|
assert!(response["total_modularity"].is_number());
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Louvain convergence
|
||
|
|
#[test]
|
||
|
|
fn test_louvain_convergence() {
|
||
|
|
let mut improved = true;
|
||
|
|
let mut iteration = 0;
|
||
|
|
let max_iterations = 100;
|
||
|
|
let threshold = 0.001;
|
||
|
|
|
||
|
|
while improved && iteration < max_iterations {
|
||
|
|
improved = false;
|
||
|
|
iteration += 1;
|
||
|
|
|
||
|
|
// Simulate: improvement decreases each iteration
|
||
|
|
let improvement = 0.1 * (0.9_f32).powi(iteration as i32);
|
||
|
|
if improvement > threshold {
|
||
|
|
improved = true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
assert!(iteration <= max_iterations);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Community granularity (ultra-fine vs coarse)
|
||
|
|
#[test]
|
||
|
|
fn test_community_granularity_fine() {
|
||
|
|
// Fine-grained: more communities, smaller size
|
||
|
|
let communities = 20;
|
||
|
|
let entities = 100;
|
||
|
|
let avg_size = entities as f32 / communities as f32;
|
||
|
|
|
||
|
|
assert!(avg_size < 10.0); // Small communities
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Community granularity coarse
|
||
|
|
#[test]
|
||
|
|
fn test_community_granularity_coarse() {
|
||
|
|
// Coarse: fewer communities, larger size
|
||
|
|
let communities = 5;
|
||
|
|
let entities = 100;
|
||
|
|
let avg_size = entities as f32 / communities as f32;
|
||
|
|
|
||
|
|
assert!(avg_size >= 20.0); // Larger communities
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Performance budget for large graphs
|
||
|
|
#[test]
|
||
|
|
fn test_large_graph_performance() {
|
||
|
|
let entity_count = 10000;
|
||
|
|
let max_iterations = 100;
|
||
|
|
|
||
|
|
// Heuristic: each iteration ~1ms per 100 entities
|
||
|
|
let estimated_time_ms = (entity_count / 100) * max_iterations;
|
||
|
|
|
||
|
|
// Should complete in reasonable time (< 30 seconds)
|
||
|
|
assert!(estimated_time_ms < 30000);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Relationship strength asymmetry
|
||
|
|
#[test]
|
||
|
|
fn test_bidirectional_edge_strength() {
|
||
|
|
// Edge A→B and B→A should count as same connection
|
||
|
|
let strength_ab = 0.8;
|
||
|
|
let strength_ba = 0.8;
|
||
|
|
|
||
|
|
assert_eq!(strength_ab, strength_ba);
|
||
|
|
}
|
||
|
|
|
||
|
|
/// Test: Community isolation score
|
||
|
|
#[test]
|
||
|
|
fn test_community_isolation() {
|
||
|
|
// Isolation = 1.0 - (edges_to_other_communities / total_edges)
|
||
|
|
let internal_edges = 10;
|
||
|
|
let external_edges = 2;
|
||
|
|
let total = internal_edges + external_edges;
|
||
|
|
|
||
|
|
let isolation = internal_edges as f32 / total as f32;
|
||
|
|
assert!((isolation - 0.833).abs() < 0.01); // 10 / 12
|
||
|
|
}
|
||
|
|
}
|