xgraph 3.0.0

//! Community detection using the Leiden algorithm
//!
//! This module implements the Leiden algorithm for community detection in graphs,
//! an improvement over the Louvain method that guarantees well-connected communities.
//! It provides flexible configuration options and handles both directed and undirected graphs.
//!
//! # Features
//! - Detects communities optimizing modularity
//! - Supports deterministic and randomized execution
//! - Handles graph aggregation and refinement
//! - Ensures community connectivity
//!
//! # Examples
//!
//! Basic usage:
//! ```rust
//! use xgraph::graph::graph::Graph;
//! use xgraph::graph::algorithms::leiden_clustering::{CommunityDetection, CommunityConfig};
//!
//! let mut graph = Graph::<f64, (), ()>::new(false);
//! let n0 = graph.add_node(()); let n1 = graph.add_node(()); let n2 = graph.add_node(());
//! graph.add_edge(n0, n1, 1.0, ()).unwrap();
//! graph.add_edge(n1, n2, 1.0, ()).unwrap();
//! graph.add_edge(n0, n2, 1.0, ()).unwrap();
//!
//! let communities = graph.detect_communities(1.0).unwrap();
//! println!("Detected {} communities", communities.len());
//! ```

use crate::core::view::NodeId;
use crate::graph::graph::Graph;
use std::collections::HashMap;
use std::fmt::Debug;
use std::hash::Hash;

pub use crate::core::algo::community::{CommunityConfig, CommunityDetectionError};

/// Trait for detecting communities in a graph using the Leiden algorithm.
///
/// # Type Parameters
/// - `W`: Edge weight type, must be convertible to `f64`.
/// - `N`: Node data type, must be clonable, equatable, hashable, and debuggable.
/// - `E`: Edge data type, must be clonable and debuggable.
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::CommunityDetection`, which is implemented for \
            every graph view — including filtered ones — and carries no unused type \
            parameters"
)]
pub trait CommunityDetection<W, N, E>
where
    W: Copy + Into<f64> + Default + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    /// Detects communities with the given resolution.
    ///
    /// # Examples
    /// ```rust
    /// use xgraph::core::CommunityDetection;
    /// use xgraph::graph::graph::Graph;
    ///
    /// let mut graph = Graph::<f64, (), ()>::new(false);
    /// let n0 = graph.add_node(());
    /// let n1 = graph.add_node(());
    /// graph.add_edge(n0, n1, 1.0, ()).unwrap();
    ///
    /// let communities = graph.detect_communities(1.0).unwrap();
    /// assert!(!communities.is_empty());
    /// ```
    fn detect_communities(
        &self,
        gamma: f64,
    ) -> Result<HashMap<usize, Vec<NodeId>>, CommunityDetectionError>;

    /// Detects communities with full control over the algorithm's settings.
    fn detect_communities_with_config(
        &self,
        config: CommunityConfig,
    ) -> Result<HashMap<usize, Vec<NodeId>>, CommunityDetectionError>;
}

#[allow(deprecated)]
impl<W, N, E> CommunityDetection<W, N, E> for Graph<W, N, E>
where
    W: Copy + Into<f64> + Default + PartialEq,
    N: Clone + Eq + Hash + Debug,
    E: Clone + Default + Debug,
{
    fn detect_communities(
        &self,
        gamma: f64,
    ) -> Result<HashMap<usize, Vec<NodeId>>, CommunityDetectionError> {
        crate::core::CommunityDetection::detect_communities(self, gamma)
    }

    fn detect_communities_with_config(
        &self,
        config: CommunityConfig,
    ) -> Result<HashMap<usize, Vec<NodeId>>, CommunityDetectionError> {
        crate::core::CommunityDetection::detect_communities_with_config(self, config)
    }
}

#[cfg(test)]
#[allow(deprecated)]
mod tests {
    use super::*;
    use crate::core::view::NodeId;

    fn create_test_graph() -> Graph<f64, String, String> {
        let mut graph = Graph::new(false);
        let node0 = graph.add_node("Node0".to_string());
        let node1 = graph.add_node("Node1".to_string());
        let node2 = graph.add_node("Node2".to_string());
        let _node3 = graph.add_node("Node3".to_string());

        graph
            .add_edge(node0, node1, 1.0, "e01".to_string())
            .unwrap();
        graph
            .add_edge(node1, node2, 1.0, "e12".to_string())
            .unwrap();
        graph
            .add_edge(node0, node2, 1.0, "e02".to_string())
            .unwrap();

        graph
    }

    #[test]
    fn test_community_detection_basic() {
        let graph = create_test_graph();
        let config = CommunityConfig {
            gamma: 1.0,
            deterministic: true,
            seed: Some(42),
            ..CommunityConfig::default()
        };
        let communities = graph.detect_communities_with_config(config).unwrap();
        assert_eq!(communities.len(), 2);
        let mut found_clique = false;
        let mut found_isolated = false;
        for (_, nodes) in communities {
            if nodes.len() == 3
                && nodes.contains(&NodeId::from_index(0))
                && nodes.contains(&NodeId::from_index(1))
                && nodes.contains(&NodeId::from_index(2))
            {
                found_clique = true;
            }
            if nodes.len() == 1 && nodes.contains(&NodeId::from_index(3)) {
                found_isolated = true;
            }
        }
        assert!(found_clique);
        assert!(found_isolated);
    }

    #[test]
    fn test_deterministic_behavior() {
        let graph = create_test_graph();
        let config = CommunityConfig {
            deterministic: true,
            seed: Some(42),
            ..CommunityConfig::default()
        };
        let communities1 = graph
            .detect_communities_with_config(config.clone())
            .unwrap();
        let communities2 = graph.detect_communities_with_config(config).unwrap();
        assert_eq!(communities1, communities2);
    }

    #[test]
    fn test_empty_graph() {
        let graph: Graph<f64, String, String> = Graph::new(false);
        let communities = graph.detect_communities(1.0).unwrap();
        assert!(communities.is_empty());
    }

    #[test]
    fn test_single_node() {
        let mut graph: Graph<f64, String, String> = Graph::new(false);
        let node = graph.add_node("Single".to_string());
        let communities = graph.detect_communities(1.0).unwrap();
        assert_eq!(communities.len(), 1);
        assert_eq!(communities.get(&node.index()), Some(&vec![node]));
    }

    #[test]
    fn test_every_node_lands_in_exactly_one_community() {
        let graph = create_test_graph();
        let communities = graph.detect_communities(1.0).unwrap();

        let mut members: Vec<NodeId> = communities.values().flatten().copied().collect();
        members.sort_unstable();
        let mut expected: Vec<NodeId> = graph.node_ids().collect();
        expected.sort_unstable();
        assert_eq!(members, expected);
    }

    #[test]
    fn test_directed_graph() {
        let mut graph = Graph::new(true);
        let node0 = graph.add_node("Node0".to_string());
        let node1 = graph.add_node("Node1".to_string());
        let node2 = graph.add_node("Node2".to_string());

        graph
            .add_edge(node0, node1, 1.0, "e01".to_string())
            .unwrap();
        graph
            .add_edge(node1, node2, 1.0, "e12".to_string())
            .unwrap();
        graph
            .add_edge(node2, node0, 1.0, "e20".to_string())
            .unwrap();

        let config = CommunityConfig {
            gamma: 1.0,
            deterministic: true,
            seed: Some(42),
            ..CommunityConfig::default()
        };
        let communities = graph.detect_communities_with_config(config).unwrap();
        assert_eq!(communities.len(), 1);
        let nodes = communities.values().next().unwrap();
        assert_eq!(nodes.len(), 3);
        assert!(nodes.contains(&node0) && nodes.contains(&node1) && nodes.contains(&node2));
    }
}