xgraph 3.0.0

//! Module for detecting communities in heterogeneous multigraphs using the Leiden algorithm.
//!
//! This module implements the Leiden algorithm tailored for heterogeneous multigraphs, allowing
//! community detection across all edges or filtered by specific edge types. The algorithm optimizes
//! modularity to identify densely connected groups of nodes, supporting both deterministic and
//! non-deterministic runs with configurable parameters.

// Error handling additions

#[cfg(feature = "hgraph")]
use crate::core::view::NodeId;
#[cfg(feature = "hgraph")]
use crate::hgraph::h_graph::HeterogeneousGraph;
#[cfg(feature = "hgraph")]
use std::collections::HashMap;

/// Error type for community detection failures.
///
/// Re-exported from the shared implementation so that the two graph types report the same
/// error.
#[cfg(feature = "hgraph")]
pub use crate::core::algo::community::{CommunityConfig, CommunityDetectionError};

/// Result type alias for community detection operations.
#[cfg(feature = "hgraph")]
pub type Result<T> = std::result::Result<T, CommunityDetectionError>;

#[cfg(feature = "hgraph")]
/// Trait for detecting communities in a heterogeneous multigraph.
#[deprecated(
    since = "3.0.0",
    note = "superseded by `xgraph::core::CommunityDetection`; `detect_communities_by_types` \
            becomes `graph.of_edge_data(&[..])` followed by the ordinary method"
)]
pub trait HeteroCommunityDetection<W, N, E>
where
    W: Copy + Into<f64> + Default + PartialEq + std::fmt::Debug,
    N: Clone + Eq + std::hash::Hash + std::fmt::Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + std::fmt::Debug + PartialEq + crate::hgraph::h_edge::EdgeType,
{
    /// Detects communities with the given resolution.
    fn detect_communities(&self, gamma: f64) -> Result<HashMap<usize, Vec<NodeId>>>;

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

    /// Detects communities using only edges whose data appears in `allowed_edge_types`.
    ///
    /// An empty slice admits every edge. Nodes left without any admitted edge are excluded
    /// from the result entirely.
    fn detect_communities_by_types(
        &self,
        allowed_edge_types: &[E],
        config: CommunityConfig,
    ) -> Result<HashMap<usize, Vec<NodeId>>>;
}

#[cfg(feature = "hgraph")]
#[allow(deprecated)]
impl<W, N, E> HeteroCommunityDetection<W, N, E> for HeterogeneousGraph<W, N, E>
where
    W: Copy + Into<f64> + Default + PartialEq + std::fmt::Debug,
    N: Clone + Eq + std::hash::Hash + std::fmt::Debug + crate::hgraph::h_node::NodeType,
    E: Clone + Default + std::fmt::Debug + PartialEq + crate::hgraph::h_edge::EdgeType,
{
    fn detect_communities(&self, gamma: f64) -> Result<HashMap<usize, Vec<NodeId>>> {
        self.detect_communities_with_config(CommunityConfig {
            gamma,
            ..CommunityConfig::default()
        })
    }

    fn detect_communities_with_config(
        &self,
        config: CommunityConfig,
    ) -> Result<HashMap<usize, Vec<NodeId>>> {
        self.detect_communities_by_types(&[], config)
    }

    fn detect_communities_by_types(
        &self,
        allowed_edge_types: &[E],
        config: CommunityConfig,
    ) -> Result<HashMap<usize, Vec<NodeId>>> {
        // Nodes left with no admitted edge have always been dropped from the result rather
        // than reported as singleton communities. A node filter composed onto the edge
        // filter says that directly, in place of the manual index compaction this used to
        // do by hand.
        let by_data = self.of_edge_data(allowed_edge_types);
        let connected: std::collections::HashSet<NodeId> =
            crate::core::GraphView::node_ids(&by_data)
                .filter(|&node| {
                    crate::core::GraphView::links(&by_data, node)
                        .next()
                        .is_some()
                })
                .collect();
        let induced =
            crate::core::NodeFiltered::new(&by_data, move |node| connected.contains(&node));

        crate::core::CommunityDetection::detect_communities_with_config(&induced, config)
    }
}

#[cfg(test)]
#[allow(deprecated)]
#[cfg(feature = "hgraph")]
mod tests {
    use super::*;
    use crate::core::view::NodeId;
    use crate::hgraph::h_edge::EdgeType;
    use crate::hgraph::h_node::NodeType;

    #[derive(Clone, Eq, PartialEq, Hash, Debug)]
    struct TestNode(String);
    impl NodeType for TestNode {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    #[derive(Clone, Debug, Default, PartialEq)]
    struct TestEdge(String);
    impl EdgeType for TestEdge {
        fn as_string(&self) -> String {
            self.0.clone()
        }
    }

    /// Creates a test graph with two distinct communities.
    fn create_test_graph() -> HeterogeneousGraph<f64, TestNode, TestEdge> {
        let mut graph = HeterogeneousGraph::new(false);
        let node0 = graph.add_node(TestNode("Node0".to_string()));
        let node1 = graph.add_node(TestNode("Node1".to_string()));
        let node2 = graph.add_node(TestNode("Node2".to_string()));
        let node3 = graph.add_node(TestNode("Node3".to_string()));
        let node4 = graph.add_node(TestNode("Node4".to_string()));

        // Community 1: clique of nodes 0, 1, 2
        graph
            .add_edge(node0, node1, 1.0, TestEdge("friend".to_string()))
            .unwrap();
        graph
            .add_edge(node1, node2, 1.0, TestEdge("friend".to_string()))
            .unwrap();
        graph
            .add_edge(node0, node2, 1.0, TestEdge("friend".to_string()))
            .unwrap();

        // Community 2: pair of nodes 3, 4
        graph
            .add_edge(node3, node4, 1.0, TestEdge("friend".to_string()))
            .unwrap();

        graph
    }

    #[test]
    fn test_community_detection_basic() {
        let graph = create_test_graph();
        let config = CommunityConfig {
            gamma: 0.2,
            deterministic: true,
            seed: Some(42),
            ..CommunityConfig::default()
        };
        let communities = graph.detect_communities_with_config(config).unwrap();

        assert_eq!(communities.len(), 2, "Should detect exactly 2 communities");
        let mut found_clique = false;
        let mut found_pair = false;
        for nodes in communities.values() {
            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() == 2
                && nodes.contains(&NodeId::from_index(3))
                && nodes.contains(&NodeId::from_index(4))
            {
                found_pair = true;
            }
        }
        assert!(
            found_clique,
            "Clique community (0, 1, 2) not found: {:?}",
            communities
        );
        assert!(
            found_pair,
            "Pair community (3, 4) not found: {:?}",
            communities
        );
    }

    #[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,
            "Deterministic runs should match"
        );
        assert_eq!(communities1.len(), 2, "Should detect 2 communities");
        let mut found_clique = false;
        let mut found_pair = false;
        for nodes in communities1.values() {
            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() == 2
                && nodes.contains(&NodeId::from_index(3))
                && nodes.contains(&NodeId::from_index(4))
            {
                found_pair = true;
            }
        }
        assert!(
            found_clique,
            "Clique community (0, 1, 2) not found: {:?}",
            communities1
        );
        assert!(
            found_pair,
            "Pair community (3, 4) not found: {:?}",
            communities1
        );
    }

    #[test]
    fn test_empty_graph() {
        let graph: HeterogeneousGraph<f64, TestNode, TestEdge> = HeterogeneousGraph::new(false);
        let communities = graph.detect_communities(1.0).unwrap();
        assert!(
            communities.is_empty(),
            "Empty graph should have no communities"
        );
    }

    #[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_multiple_edges() {
        let mut graph = create_test_graph();
        graph
            .add_edge(
                NodeId::from_index(0),
                NodeId::from_index(1),
                2.0,
                TestEdge("colleague".to_string()),
            )
            .unwrap();

        let config = CommunityConfig {
            gamma: 0.2,
            deterministic: true,
            seed: Some(42),
            ..CommunityConfig::default()
        };
        let communities = graph.detect_communities_with_config(config).unwrap();
        assert_eq!(
            communities.len(),
            2,
            "Should detect 2 communities with multiple edges"
        );
        let mut found_clique = false;
        let mut found_pair = false;
        for nodes in communities.values() {
            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() == 2
                && nodes.contains(&NodeId::from_index(3))
                && nodes.contains(&NodeId::from_index(4))
            {
                found_pair = true;
            }
        }
        assert!(
            found_clique,
            "Clique community (0, 1, 2) not found: {:?}",
            communities
        );
        assert!(
            found_pair,
            "Pair community (3, 4) not found: {:?}",
            communities
        );
    }

    #[test]
    fn test_community_detection_by_types() {
        let graph = create_test_graph();
        let config = CommunityConfig {
            deterministic: true,
            seed: Some(42),
            ..CommunityConfig::default()
        };
        let allowed_edge_types = vec![TestEdge("friend".to_string())];
        let communities = graph
            .detect_communities_by_types(&allowed_edge_types, config)
            .unwrap();

        assert_eq!(communities.len(), 2, "Should detect 2 communities");
        let mut found_clique = false;
        let mut found_pair = false;
        for nodes in communities.values() {
            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() == 2
                && nodes.contains(&NodeId::from_index(3))
                && nodes.contains(&NodeId::from_index(4))
            {
                found_pair = true;
            }
        }
        assert!(
            found_clique,
            "Clique community (0, 1, 2) not found: {:?}",
            communities
        );
        assert!(
            found_pair,
            "Pair community (3, 4) not found: {:?}",
            communities
        );
    }

    #[test]
    fn test_community_detection_by_types_isolated() {
        let mut graph = create_test_graph();
        graph
            .add_edge(
                NodeId::from_index(1),
                NodeId::from_index(2),
                1.0,
                TestEdge("colleague".to_string()),
            )
            .unwrap();

        let config = CommunityConfig {
            deterministic: true,
            seed: Some(42),
            ..CommunityConfig::default()
        };
        let allowed_edge_types = vec![TestEdge("friend".to_string())];
        let communities = graph
            .detect_communities_by_types(&allowed_edge_types, config)
            .unwrap();

        assert_eq!(communities.len(), 2, "Should detect 2 communities");
        let mut found_clique = false;
        let mut found_pair = false;
        for nodes in communities.values() {
            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() == 2
                && nodes.contains(&NodeId::from_index(3))
                && nodes.contains(&NodeId::from_index(4))
            {
                found_pair = true;
            }
        }
        assert!(
            found_clique,
            "Clique community (0, 1, 2) not found: {:?}",
            communities
        );
        assert!(
            found_pair,
            "Pair community (3, 4) not found: {:?}",
            communities
        );
    }
}