//! Numerical validation tests for community detection algorithms
//!
//! These tests ensure that community detection algorithms produce numerically
//! accurate and consistent results by comparing with known community structures
//! and validating algorithmic properties.

use approx::{assert_abs_diff_eq, assert_relative_eq};
use scirs2_graph::{
    algorithms::community::{
        greedy_modularity_optimization_result, louvain_communities_result, modularity,
        modularity_optimization_result, parallel_louvain_communities_result, CommunityResult,
    },
    generators, Graph,
};
use std::collections::{HashMap, HashSet};

#[test]
#[allow(dead_code)]
fn test_modularity_calculation_accuracy() {
    // Test case 1: Simple graph with known modularity
    let mut graph = Graph::new();

    // Create two clear communities: {0,1} and {2,3}
    for i in 0..4 {
        graph.add_node(i).unwrap();
    }

    // Intra-community edges (strong)
    graph.add_edge(0, 1, 1.0).unwrap();
    graph.add_edge(2, 3, 1.0).unwrap();

    // Inter-community edge (weak)
    graph.add_edge(1, 2, 0.1).unwrap();

    // Perfect community assignment
    let mut perfect_communities = HashMap::new();
    perfect_communities.insert(0, 0);
    perfect_communities.insert(1, 0);
    perfect_communities.insert(2, 1);
    perfect_communities.insert(3, 1);

    let perfect_modularity = modularity(&graph, &perfect_communities).unwrap();

    // Random community assignment (should be worse)
    let mut random_communities = HashMap::new();
    random_communities.insert(0, 0);
    random_communities.insert(1, 1);
    random_communities.insert(2, 0);
    random_communities.insert(3, 1);

    let random_modularity = modularity(&graph, &random_communities).unwrap();

    // Perfect assignment should have higher modularity
    assert!(
        perfect_modularity > random_modularity,
        "Perfect community structure should have higher modularity"
    );

    // Modularity should be positive for good community structure
    assert!(
        perfect_modularity > 0.0,
        "Well-structured communities should have positive modularity"
    );
}

#[test]
#[allow(dead_code)]
fn test_louvain_algorithm_accuracy() {
    // Test case: Two clear communities connected by a single bridge
    let mut graph = Graph::new();

    // Community 1: nodes 0-2 (complete subgraph)
    for i in 0..6 {
        graph.add_node(i).unwrap();
    }

    // Strong intra-community connections
    for i in 0..3 {
        for j in (i + 1)..3 {
            graph.add_edge(i, j, 2.0).unwrap();
        }
    }

    for i in 3..6 {
        for j in (i + 1)..6 {
            graph.add_edge(i, j, 2.0).unwrap();
        }
    }

    // Weak inter-community bridge
    graph.add_edge(1, 4, 0.1).unwrap();

    let result = louvain_communities_result(&graph);

    // Should detect exactly 2 communities
    assert_eq!(
        result.num_communities, 2,
        "Should detect exactly 2 communities"
    );

    // Check that nodes 0,1,2 are in the same community
    let comm_0 = result.get_community(&0).unwrap();
    let comm_1 = result.get_community(&1).unwrap();
    let comm_2 = result.get_community(&2).unwrap();

    assert_eq!(comm_0, comm_1, "Nodes 0 and 1 should be in same community");
    assert_eq!(comm_1, comm_2, "Nodes 1 and 2 should be in same community");

    // Check that nodes 3,4,5 are in the same community
    let comm_3 = result.get_community(&3).unwrap();
    let comm_4 = result.get_community(&4).unwrap();
    let comm_5 = result.get_community(&5).unwrap();

    assert_eq!(comm_3, comm_4, "Nodes 3 and 4 should be in same community");
    assert_eq!(comm_4, comm_5, "Nodes 4 and 5 should be in same community");

    // The two groups should be in different communities
    assert_ne!(
        comm_0, comm_3,
        "The two groups should be in different communities"
    );

    // Modularity should be reasonably high
    if let Some(quality) = result.quality_score {
        assert!(
            quality > 0.3,
            "Modularity should be reasonably high for clear community structure"
        );
    }
}

#[test]
#[allow(dead_code)]
fn test_modularity_optimization_consistency() {
    // Test that different optimization algorithms produce reasonable results
    let graph = create_test_graph_with_communities(50, 2);

    let louvain_result = louvain_communities_result(&graph);
    let greedy_result = greedy_modularity_optimization_result(&graph, 100);
    let simulated_annealing_result = modularity_optimization_result(&graph, 1.0, 0.95, 500);

    // All should detect similar number of communities (within reasonable range)
    let min_communities = louvain_result
        .num_communities
        .min(greedy_result.num_communities)
        .min(simulated_annealing_result.num_communities);
    let max_communities = louvain_result
        .num_communities
        .max(greedy_result.num_communities)
        .max(simulated_annealing_result.num_communities);

    assert!(
        max_communities <= min_communities * 2,
        "Different algorithms should find similar number of communities (max: {}, min: {})",
        max_communities,
        min_communities
    );

    // All should have positive modularity
    for (name, result) in [
        ("Louvain", &louvain_result),
        ("Greedy", &greedy_result),
        ("Simulated Annealing", &simulated_annealing_result),
    ] {
        if let Some(quality) = result.quality_score {
            assert!(
                quality > 0.0,
                "{} algorithm should produce positive modularity, got {}",
                name,
                quality
            );
        }
    }
}

#[test]
#[allow(dead_code)]
fn test_parallel_vs_sequential_consistency() {
    // Test that parallel and sequential algorithms produce similar results
    let graph = create_test_graph_with_communities(100, 3);

    let sequential_result = louvain_communities_result(&graph);
    let parallel_result = parallel_louvain_communities_result(&graph, 50);

    // Results should be deterministic and consistent
    // (Note: exact equality might not hold due to implementation differences,
    // but modularity should be very similar)

    if let (Some(seq_quality), Some(par_quality)) = (
        sequential_result.quality_score,
        parallel_result.quality_score,
    ) {
        assert_relative_eq!(
            seq_quality,
            par_quality,
            epsilon = 0.1,
            max_relative = 0.2,
            "Sequential and parallel algorithms should produce similar modularity scores"
        );
    }

    // Both should find reasonable number of communities
    assert!(
        sequential_result.num_communities >= 1 && sequential_result.num_communities <= 10,
        "Sequential algorithm should find reasonable number of communities"
    );
    assert!(
        parallel_result.num_communities >= 1 && parallel_result.num_communities <= 10,
        "Parallel algorithm should find reasonable number of communities"
    );
}

#[test]
#[allow(dead_code)]
fn test_community_result_api_consistency() {
    // Test that the standardized CommunityResult API works consistently
    let graph = create_test_graph_with_communities(20, 2);

    let result = louvain_communities_result(&graph);

    // Test that node count matches
    assert_eq!(
        result.node_communities.len(),
        graph.node_count(),
        "All nodes should be assigned to communities"
    );

    // Test that community sets and node mapping are consistent
    let mut nodes_in_sets = HashSet::new();
    for community in &result.communities {
        for node in community {
            nodes_in_sets.insert(*node);
        }
    }

    let nodes_in_mapping: HashSet<_> = result.node_communities.keys().cloned().collect();

    assert_eq!(
        nodes_in_sets, nodes_in_mapping,
        "Community sets and node mapping should be consistent"
    );

    // Test community ID assignment consistency
    for (node, &community_id) in &result.node_communities {
        assert!(
            community_id < result.num_communities,
            "Community ID should be valid (node {}, community {}, max {})",
            node,
            community_id,
            result.num_communities
        );

        assert!(
            result.communities[community_id].contains(node),
            "Node should be in the community it's assigned to"
        );
    }

    // Test helper methods
    for node in 0..graph.node_count() {
        let community_id = result.get_community(&node).unwrap();
        let community_members = result.get_community_members(community_id).unwrap();
        assert!(
            community_members.contains(&node),
            "Helper methods should be consistent"
        );
    }
}

#[test]
#[allow(dead_code)]
fn test_edge_cases() {
    // Test case 1: Empty graph
    let empty_graph = Graph::new();
    let empty_result = louvain_communities_result(&empty_graph);
    assert_eq!(
        empty_result.num_communities, 0,
        "Empty graph should have 0 communities"
    );
    assert_eq!(
        empty_result.communities.len(),
        0,
        "Empty graph should have no community sets"
    );

    // Test case 2: Single node
    let mut single_node = Graph::new();
    single_node.add_node(0).unwrap();

    let single_result = louvain_communities_result(&single_node);
    assert_eq!(
        single_result.num_communities, 1,
        "Single node should form 1 community"
    );
    assert_eq!(
        single_result.communities[0].len(),
        1,
        "Single community should have 1 node"
    );
    assert!(
        single_result.communities[0].contains(&0),
        "Single node should be in the community"
    );

    // Test case 3: Disconnected graph
    let mut disconnected = Graph::new();
    for i in 0..6 {
        disconnected.add_node(i).unwrap();
    }

    // Two disconnected triangles
    for i in 0..3 {
        for j in (i + 1)..3 {
            disconnected.add_edge(i, j, 1.0).unwrap();
        }
    }

    for i in 3..6 {
        for j in (i + 1)..6 {
            disconnected.add_edge(i, j, 1.0).unwrap();
        }
    }

    let disconnected_result = louvain_communities_result(&disconnected);
    assert!(
        disconnected_result.num_communities >= 2,
        "Disconnected components should form separate communities"
    );
}

#[test]
#[allow(dead_code)]
fn test_modularity_bounds() {
    // Test that modularity is within expected bounds
    let graphs = vec![
        ("Complete graph", generators::complete_graph(10).unwrap()),
        ("Path graph", generators::path_graph(10).unwrap()),
        ("Star graph", generators::star_graph(10).unwrap()),
        (
            "Random graph",
            generators::erdos_renyi_graph(20, 0.1, None).unwrap(),
        ),
    ];

    for (name, graph) in graphs {
        let result = louvain_communities_result(&graph);

        if let Some(quality) = result.quality_score {
            // Modularity should be between -0.5 and 1.0 (theoretical bounds)
            assert!(
                quality >= -0.5 && quality <= 1.0,
                "Modularity for {} should be within bounds [-0.5, 1.0], got {}",
                name,
                quality
            );
        }

        // Should always assign all nodes to communities
        assert_eq!(
            result.node_communities.len(),
            graph.node_count(),
            "All nodes in {} should be assigned to communities",
            name
        );
    }
}

#[test]
#[allow(dead_code)]
fn test_algorithm_convergence() {
    // Test that iterative algorithms converge to stable solutions
    let graph = create_test_graph_with_communities(30, 2);

    // Run greedy optimization multiple times with different iteration limits
    let result_10 = greedy_modularity_optimization_result(&graph, 10);
    let result_50 = greedy_modularity_optimization_result(&graph, 50);
    let result_100 = greedy_modularity_optimization_result(&graph, 100);

    // Modularity should not decrease with more iterations
    if let (Some(q10), Some(q50), Some(q100)) = (
        result_10.quality_score,
        result_50.quality_score,
        result_100.quality_score,
    ) {
        assert!(
            q50 >= q10 - 1e-6,
            "More iterations should not significantly decrease modularity"
        );
        assert!(
            q100 >= q50 - 1e-6,
            "More iterations should not significantly decrease modularity"
        );
    }
}

/// Helper function to create a test graph with known community structure
#[allow(dead_code)]
fn create_test_graph_with_communities(
    nodes_per_community: usize,
    num_communities: usize,
) -> Graph<usize, f64> {
    let mut graph = Graph::new();

    let total_nodes = nodes_per_community * num_communities;

    // Add all nodes
    for i in 0..total_nodes {
        graph.add_node(i).unwrap();
    }

    // Add strong intra-community edges
    for community in 0..num_communities {
        let start = community * nodes_per_community;
        let end = start + nodes_per_community;

        for i in start..end {
            for j in (i + 1)..end {
                if (i + j) % 3 == 0 {
                    // Add edges with some randomness but high density
                    graph.add_edge(i, j, 2.0).unwrap();
                }
            }
        }
    }

    // Add weak inter-community edges
    for community in 0..(num_communities - 1) {
        let node1 = community * nodes_per_community;
        let node2 = (community + 1) * nodes_per_community;
        graph.add_edge(node1, node2, 0.1).unwrap();
    }

    graph
}

#[test]
#[allow(dead_code)]
    #[ignore] // FIXME: Potentially slow or hanging test - needs investigationfn test_known_benchmark_graphs() {
    // Test on Zachary's Karate Club-like structure (simplified version)
    let karate_club = create_karate_club_graph();
    let result = louvain_communities_result(&karate_club);

    // Should detect approximately 2 main communities
    assert!(
        result.num_communities >= 2 && result.num_communities <= 4,
        "Karate club should have 2-4 communities, found {}",
        result.num_communities
    );

    // Should have reasonable modularity
    if let Some(quality) = result.quality_score {
        assert!(
            quality > 0.2,
            "Karate club should have reasonable modularity structure"
        );
    }
}

/// Create a simplified version of Zachary's Karate Club network
#[allow(dead_code)]
fn create_karate_club_graph() -> Graph<usize, f64> {
    let mut graph = Graph::new();

    // Create 34 nodes (like the original)
    for i in 0..34 {
        graph.add_node(i).unwrap();
    }

    // Add some edges to create two main groups with some bridge connections
    // Group 1: 0-16
    let group1_edges = vec![
        (0, 1),
        (0, 2),
        (0, 3),
        (0, 4),
        (0, 5),
        (0, 6),
        (0, 7),
        (0, 8),
        (1, 2),
        (1, 3),
        (1, 7),
        (2, 3),
        (2, 7),
        (3, 7),
        (4, 6),
        (4, 10),
        (5, 6),
        (5, 10),
        (5, 16),
        (6, 16),
        (8, 30),
        (8, 32),
        (8, 33),
    ];

    // Group 2: 17-33
    let group2_edges = vec![
        (17, 18),
        (17, 19),
        (17, 20),
        (17, 21),
        (18, 19),
        (18, 20),
        (19, 20),
        (19, 21),
        (20, 21),
        (22, 23),
        (22, 24),
        (23, 24),
        (24, 25),
        (24, 27),
        (25, 27),
        (26, 27),
        (26, 28),
        (27, 28),
        (28, 29),
        (29, 30),
        (29, 31),
        (30, 31),
        (31, 32),
        (32, 33),
    ];

    // Bridge edges
    let bridge_edges = vec![(0, 17), (16, 17), (8, 29)];

    // Add all edges
    for (u, v) in group1_edges
        .into_iter()
        .chain(group2_edges)
        .chain(bridge_edges)
    {
        graph.add_edge(u, v, 1.0).unwrap();
    }

    graph
}
