xgraph 3.0.0

//! Community detection with the Leiden algorithm, written once against [`GraphView`].
//!
//! Leiden improves on Louvain by guaranteeing that the communities it reports are
//! internally connected. The implementation works on contiguous indices `0..n`, so the
//! entry point below translates node IDs — which may be sparse after removals — into
//! positions on the way in and back again on the way out.

use crate::core::view::{GraphView, NodeId};
use rand::rngs::StdRng;
use rand::seq::SliceRandom;
use rand::{Rng, SeedableRng};
use std::collections::hash_map::DefaultHasher;
use std::collections::{HashMap, HashSet, VecDeque};
use std::hash::Hasher;

/// Error type for community detection failures.
#[derive(Debug, Clone, PartialEq, thiserror::Error)]
pub enum CommunityDetectionError {
    /// A node referenced during the computation does not exist.
    #[error("Invalid node reference: node ID {0} not found")]
    InvalidNode(NodeId),
    /// A floating-point result was NaN or infinite, which would corrupt the partition.
    #[error("Invalid floating-point result in community detection: {0}")]
    InvalidFloatResult(String),
    /// The algorithm's own bookkeeping became inconsistent.
    ///
    /// This reports a bug in the library rather than a problem with the input. The Leiden
    /// implementation works on positional indices of its own, distinct from the graph's
    /// node identifiers, and this is what a mismatch between them surfaces as.
    #[error("Internal inconsistency in community detection: {0}")]
    Internal(String),
}

/// Configuration for the Leiden community detection algorithm.
#[derive(Debug, Clone)]
pub struct CommunityConfig {
    /// Resolution parameter controlling community granularity: higher values yield more,
    /// smaller communities.
    pub gamma: f64,
    /// Scaling factor applied to modularity.
    pub resolution: f64,
    /// Maximum number of passes.
    pub iterations: usize,
    /// Whether to run reproducibly. With a `seed` this is redundant; without one it fixes
    /// the seed so that repeated runs agree.
    pub deterministic: bool,
    /// Seed for the random number generator.
    pub seed: Option<u64>,
    /// Communities smaller than this are merged into a neighbour where possible.
    pub min_community_size: usize,
}

impl Default for CommunityConfig {
    fn default() -> Self {
        Self {
            gamma: 1.0,
            resolution: 1.0,
            iterations: 10,
            deterministic: false,
            seed: None,
            min_community_size: 2,
        }
    }
}

/// Community detection available on every [`GraphView`] whose weights convert to `f64`.
pub trait CommunityDetection: GraphView {
    /// Detects communities with the given resolution and otherwise default settings.
    ///
    /// # Returns
    /// A map from community ID to the node IDs belonging to it.
    fn detect_communities(
        &self,
        gamma: f64,
    ) -> Result<HashMap<usize, Vec<NodeId>>, CommunityDetectionError>
    where
        Self::Weight: Into<f64>,
    {
        self.detect_communities_with_config(CommunityConfig {
            gamma,
            ..CommunityConfig::default()
        })
    }

    /// Detects communities with full control over the algorithm's settings.
    fn detect_communities_with_config(
        &self,
        config: CommunityConfig,
    ) -> Result<HashMap<usize, Vec<NodeId>>, CommunityDetectionError>
    where
        Self::Weight: Into<f64>,
    {
        // Node IDs may be sparse, so the algorithm runs over positions and the results are
        // translated back at the end.
        let index_to_id = self.node_id_vec();
        let id_to_index: HashMap<NodeId, usize> = index_to_id
            .iter()
            .enumerate()
            .map(|(index, &id)| (id, index))
            .collect();

        // Parallel edges between the same pair are summed into a single weighted
        // adjacency entry, which is what modularity treats them as anyway.
        let adjacency_list: Vec<Vec<(usize, f64)>> = index_to_id
            .iter()
            .map(|&id| {
                let mut totals: HashMap<usize, f64> = HashMap::new();
                for link in self.links(id) {
                    let Some(&index) = id_to_index.get(&link.target) else {
                        continue;
                    };
                    *totals.entry(index).or_insert(0.0) += link.weight.into();
                }
                totals.into_iter().collect()
            })
            .collect();

        let mut state = LeidenState::initialize(&adjacency_list, config)?;
        let mut previous = state.node_to_community.clone();

        for _ in 0..state.config.iterations {
            state.fast_louvain_move_nodes()?;
            state.refine_partition()?;
            state.enforce_gamma_properties()?;

            if state.node_to_community == previous {
                break;
            }
            previous = state.node_to_community.clone();

            if state.should_aggregate() {
                state.aggregate_graph()?;
            }
        }

        // Resolve first: merging undersized communities has to see original nodes and the
        // original adjacency, or it merges into communities it is not adjacent to.
        state.resolve_hierarchy()?;
        state.merge_small_communities(state.config.min_community_size)?;

        Ok(state
            .get_communities()
            .into_iter()
            .map(|(community, members)| {
                let members = members
                    .into_iter()
                    .filter_map(|index| index_to_id.get(index).copied())
                    .collect();
                (community, members)
            })
            .collect())
    }
}

impl<G: GraphView + ?Sized> CommunityDetection for G {}

/// Internal state for the Leiden clustering algorithm.
///
/// Manages graph structure, community assignments, and weights during clustering.
///
/// # Fields
/// - `adjacency_list`: Graph representation as adjacency list
/// - `node_to_community`: Current community assignments
/// - `community_weights`: Total edge weights per community
/// - `total_weight`: Sum of all edge weights
/// - `hierarchy`: Tracks community assignments across levels
/// - `original_size`: Original number of nodes
/// - `config`: Algorithm configuration
/// - `rng`: Random number generator
struct LeidenState {
    adjacency_list: Vec<Vec<(usize, f64)>>,
    /// The adjacency as first supplied, in original node indices.
    ///
    /// `adjacency_list` is replaced by the aggregated graph as the algorithm coarsens the
    /// partition, so anything that has to reason about original nodes — merging undersized
    /// communities, in particular — needs this to stay correct.
    original_adjacency: Vec<Vec<(usize, f64)>>,
    node_to_community: HashMap<usize, usize>,
    community_weights: HashMap<usize, f64>,
    total_weight: f64,
    /// One entry per aggregation step, mapping an index of the level below to the index of
    /// the coarser node that absorbed it.
    ///
    /// Composing them carries an original node down to its index in the current graph;
    /// `node_to_community` then gives the community it currently belongs to. Keeping the
    /// two separate is what stops the index spaces from being mixed.
    hierarchy: Vec<HashMap<usize, usize>>,
    original_size: usize,
    config: CommunityConfig,
    rng: StdRng,
}

#[allow(dead_code)]
impl LeidenState {
    fn initialize(
        adjacency_list: &[Vec<(usize, f64)>],
        config: CommunityConfig,
    ) -> Result<Self, CommunityDetectionError> {
        let mut node_to_community = HashMap::new();
        let mut community_weights = HashMap::new();
        let mut total_weight = 0.0;

        for (node, neighbors) in adjacency_list.iter().enumerate() {
            node_to_community.insert(node, node);
            let weight = neighbors.iter().map(|(_, w)| w).sum::<f64>();
            community_weights.insert(node, weight);
            total_weight += weight;
        }

        let rng = if config.deterministic {
            StdRng::seed_from_u64(config.seed.unwrap_or(42))
        } else {
            StdRng::seed_from_u64(config.seed.unwrap_or_else(rand::random))
        };

        Ok(Self {
            adjacency_list: adjacency_list.to_vec(),
            original_adjacency: adjacency_list.to_vec(),
            node_to_community,
            community_weights,
            total_weight,
            hierarchy: Vec::new(),
            original_size: adjacency_list.len(),
            config,
            rng,
        })
    }

    fn fast_louvain_move_nodes(&mut self) -> Result<(), CommunityDetectionError> {
        let mut nodes: Vec<usize> = (0..self.adjacency_list.len()).collect();
        if self.config.deterministic {
            nodes.sort_unstable();
        } else {
            nodes.shuffle(&mut self.rng);
        }

        let mut queue: VecDeque<usize> = nodes.into_iter().collect();
        let mut processed = HashSet::new();

        while let Some(node) = queue.pop_front() {
            if processed.contains(&node) {
                continue;
            }
            processed.insert(node);

            let current_comm = *self.node_to_community.get(&node).ok_or_else(|| {
                CommunityDetectionError::Internal(format!("index {} has no community", node))
            })?;
            let mut eligible_communities = self.find_eligible_communities(node, current_comm);
            if self.config.deterministic {
                eligible_communities.sort_unstable();
            }

            let mut best_comm = current_comm;
            let mut best_delta = f64::MIN;

            for comm in &eligible_communities {
                let delta = self.calculate_move_delta(node, *comm)?;
                if delta > best_delta {
                    best_delta = delta;
                    best_comm = *comm;
                }
            }

            if best_delta > 0.0 && best_comm != current_comm {
                self.move_node(node, best_comm)?;

                let mut neighbors: Vec<usize> = self.adjacency_list[node]
                    .iter()
                    .map(|&(n, _)| n)
                    .filter(|n| !processed.contains(n))
                    .collect();
                if self.config.deterministic {
                    neighbors.sort_unstable();
                }
                for neighbor in neighbors {
                    queue.push_back(neighbor);
                }
            }

            if queue.len() > self.original_size * 2 {
                break;
            }
        }
        Ok(())
    }

    fn generate_order_key(&mut self, node: usize) -> u64 {
        let mut hasher = DefaultHasher::new();
        hasher.write_u64(self.rng.random::<u64>());
        hasher.write_usize(node);
        hasher.finish()
    }

    fn refine_partition(&mut self) -> Result<(), CommunityDetectionError> {
        let mut singleton_partition = self.create_singleton_partition();

        let mut communities: Vec<usize> = self
            .node_to_community
            .values()
            .copied()
            .collect::<HashSet<_>>()
            .into_iter()
            .collect();
        if self.config.deterministic {
            communities.sort_unstable();
        }

        for comm in communities {
            self.refine_community_subset(comm, &mut singleton_partition)?;
        }

        self.node_to_community = singleton_partition;
        self.hierarchy.push(self.node_to_community.clone());
        Ok(())
    }

    /// Collapses the level hierarchy into one final assignment of original nodes to
    /// communities, and returns the state to original-node indices.
    ///
    /// Everything that runs after this point — merging undersized communities, reading the
    /// result — then speaks a single index space. Mixing the aggregated indices with the
    /// original ones is what used to let an undersized community merge into a community it
    /// shares no edge with, producing a disconnected community on a graph whose components
    /// are disjoint.
    fn resolve_hierarchy(&mut self) -> Result<(), CommunityDetectionError> {
        let final_communities: HashMap<usize, usize> = (0..self.original_size)
            .map(|node| (node, self.community_of_original(node)))
            .collect();

        self.node_to_community = final_communities;
        self.adjacency_list = self.original_adjacency.clone();
        self.hierarchy.clear();
        self.recompute_community_weights();
        Ok(())
    }

    /// Recomputes each community's total incident weight from the current adjacency.
    fn recompute_community_weights(&mut self) {
        let mut weights: HashMap<usize, f64> = HashMap::new();
        let mut total = 0.0;

        for (node, neighbors) in self.adjacency_list.iter().enumerate() {
            let weight: f64 = neighbors.iter().map(|(_, w)| w).sum();
            // `move_node` reads a node's own weight under its node key and the community
            // totals under community keys, so both are recorded.
            weights.insert(node, weight);
            total += weight;
        }
        for (&node, &community) in &self.node_to_community {
            if node == community {
                continue;
            }
            let node_weight = self
                .adjacency_list
                .get(node)
                .map(|neighbors| neighbors.iter().map(|(_, w)| w).sum::<f64>())
                .unwrap_or(0.0);
            *weights.entry(community).or_insert(0.0) += node_weight;
        }

        self.community_weights = weights;
        self.total_weight = total;
    }

    fn should_aggregate(&self) -> bool {
        let current_modularity = self.calculate_modularity().unwrap_or(0.0);
        let communities = self.get_communities();
        communities.values().any(|nodes| nodes.len() > 1) && current_modularity > 0.0
    }

    pub fn get_communities(&self) -> HashMap<usize, Vec<usize>> {
        let mut final_mapping: HashMap<usize, Vec<usize>> = HashMap::new();
        for node in 0..self.original_size {
            final_mapping
                .entry(self.community_of_original(node))
                .or_default()
                .push(node);
        }
        for nodes in final_mapping.values_mut() {
            nodes.sort_unstable();
        }
        final_mapping
    }

    /// Follows an original node down through every aggregation step and reports the
    /// community it currently sits in.
    fn community_of_original(&self, node: usize) -> usize {
        let mut current = node;
        for level in &self.hierarchy {
            current = level.get(&current).copied().unwrap_or(current);
        }
        self.node_to_community
            .get(&current)
            .copied()
            .unwrap_or(current)
    }

    fn find_eligible_communities(&self, node: usize, original_comm: usize) -> Vec<usize> {
        let mut comms: Vec<usize> = self.adjacency_list[node]
            .iter()
            .map(|(n, _)| self.node_to_community.get(n).copied().unwrap_or(*n))
            .filter(|&comm| comm != original_comm)
            .collect();
        comms.sort_unstable();
        comms.dedup();
        comms
    }

    fn calculate_move_delta(
        &self,
        node: usize,
        new_community: usize,
    ) -> Result<f64, CommunityDetectionError> {
        let old_community = self.node_to_community.get(&node).copied().unwrap_or(node);
        if old_community == new_community {
            return Ok(0.0);
        }

        let k_i = self.community_weights.get(&node).copied().unwrap_or(0.0);
        let sum_tot_new = self
            .community_weights
            .get(&new_community)
            .copied()
            .unwrap_or(0.0);
        let sum_tot_old = self
            .community_weights
            .get(&old_community)
            .copied()
            .unwrap_or(0.0);
        let m = self.total_weight.max(f64::EPSILON);

        let sum_in_new: f64 = self.adjacency_list[node]
            .iter()
            .filter(|(n, _)| self.node_to_community.get(n).copied().unwrap_or(*n) == new_community)
            .map(|(_, w)| w)
            .sum();
        let sum_in_old: f64 = self.adjacency_list[node]
            .iter()
            .filter(|(n, _)| self.node_to_community.get(n).copied().unwrap_or(*n) == old_community)
            .map(|(_, w)| w)
            .sum();

        let delta_new = sum_in_new - self.config.resolution * (sum_tot_new + k_i) * k_i / (2.0 * m);
        let delta_old = sum_in_old - self.config.resolution * (sum_tot_old) * k_i / (2.0 * m);

        let result = delta_new - delta_old;
        if result.is_nan() || result.is_infinite() {
            return Err(CommunityDetectionError::InvalidFloatResult(format!(
                "Delta calculation resulted in {} for node {}",
                if result.is_nan() { "NaN" } else { "infinity" },
                node
            )));
        }
        Ok(result)
    }

    fn move_node(
        &mut self,
        node: usize,
        new_community: usize,
    ) -> Result<(), CommunityDetectionError> {
        let old_community = self.node_to_community.get(&node).copied().unwrap_or(node);
        let node_weight = self.community_weights.get(&node).copied().unwrap_or(0.0);

        let old_weight = self
            .community_weights
            .get_mut(&old_community)
            .ok_or_else(|| {
                CommunityDetectionError::Internal(format!(
                    "community {} has no recorded weight",
                    old_community
                ))
            })?;
        *old_weight -= node_weight;
        *self.community_weights.entry(new_community).or_insert(0.0) += node_weight;

        self.node_to_community.insert(node, new_community);
        Ok(())
    }

    fn create_singleton_partition(&self) -> HashMap<usize, usize> {
        (0..self.adjacency_list.len()).map(|n| (n, n)).collect()
    }

    /// Collapses each community of the current graph into a single node.
    ///
    /// Everything here is expressed in the *current* index space. Building the coarser
    /// graph from original node indices instead — which is what this used to do from the
    /// second aggregation onwards — reads the wrong rows of the adjacency list and silently
    /// drops the rest, which is how communities spanning disconnected components appeared.
    fn aggregate_graph(&mut self) -> Result<(), CommunityDetectionError> {
        let size = self.adjacency_list.len();

        // Community labels are numbered in ascending order, so the coarser graph does not
        // depend on hash iteration order.
        let mut labels: Vec<usize> = (0..size)
            .map(|node| self.node_to_community.get(&node).copied().unwrap_or(node))
            .collect::<HashSet<_>>()
            .into_iter()
            .collect();
        labels.sort_unstable();
        let coarse_of_label: HashMap<usize, usize> = labels
            .iter()
            .enumerate()
            .map(|(coarse, &label)| (label, coarse))
            .collect();

        let level: HashMap<usize, usize> = (0..size)
            .map(|node| {
                let label = self.node_to_community.get(&node).copied().unwrap_or(node);
                (node, coarse_of_label[&label])
            })
            .collect();

        let mut aggregated: Vec<HashMap<usize, f64>> = vec![HashMap::new(); labels.len()];
        for node in 0..size {
            let from = level[&node];
            for (neighbor, weight) in &self.adjacency_list[node] {
                if let Some(&to) = level.get(neighbor) {
                    *aggregated[from].entry(to).or_insert(0.0) += weight;
                }
            }
        }

        self.adjacency_list = aggregated
            .into_iter()
            .map(|edges| edges.into_iter().collect())
            .collect();
        // Every coarse node starts in a community of its own again.
        self.node_to_community = (0..labels.len()).map(|node| (node, node)).collect();
        self.hierarchy.push(level);
        self.community_weights = self.calculate_new_community_weights()?;
        self.total_weight = self.community_weights.values().sum();
        Ok(())
    }

    fn calculate_new_community_weights(
        &self,
    ) -> Result<HashMap<usize, f64>, CommunityDetectionError> {
        Ok(self
            .adjacency_list
            .iter()
            .enumerate()
            .map(|(node, edges)| (node, edges.iter().map(|(_, w)| w).sum()))
            .collect())
    }

    fn calculate_modularity(&self) -> Result<f64, CommunityDetectionError> {
        let mut modularity = 0.0;
        let m = self.total_weight.max(f64::EPSILON);

        for (node, &community) in &self.node_to_community {
            let node_weight = self.community_weights.get(node).copied().unwrap_or(0.0);
            if *node < self.adjacency_list.len() {
                for (neighbor, weight) in &self.adjacency_list[*node] {
                    if community == *self.node_to_community.get(neighbor).unwrap() {
                        let neighbor_weight =
                            self.community_weights.get(neighbor).copied().unwrap_or(0.0);
                        let term = *weight
                            - self.config.resolution
                                * self.config.gamma
                                * (node_weight * neighbor_weight)
                                / (2.0 * m);
                        if term.is_nan() || term.is_infinite() {
                            return Err(CommunityDetectionError::InvalidFloatResult(format!(
                                "Modularity term resulted in {} for node {}",
                                if term.is_nan() { "NaN" } else { "infinity" },
                                node
                            )));
                        }
                        modularity += term;
                    }
                }
            }
        }
        let result = modularity / (2.0 * m);
        if result.is_nan() || result.is_infinite() {
            return Err(CommunityDetectionError::InvalidFloatResult(format!(
                "Modularity resulted in {}",
                if result.is_nan() { "NaN" } else { "infinity" }
            )));
        }
        Ok(result)
    }

    fn get_nodes_in_community(&self, comm: usize) -> Vec<usize> {
        let mut nodes: Vec<usize> = self
            .node_to_community
            .iter()
            .filter(|(_, &c)| c == comm)
            .map(|(&n, _)| n)
            .collect();
        if self.config.deterministic {
            nodes.sort_unstable();
        }
        nodes
    }

    fn enforce_gamma_properties(&mut self) -> Result<(), CommunityDetectionError> {
        let mut communities: Vec<usize> = self
            .node_to_community
            .values()
            .copied()
            .collect::<HashSet<_>>()
            .into_iter()
            .collect();
        if self.config.deterministic {
            communities.sort_unstable();
        }

        for comm in communities {
            if !self.is_community_connected(comm) {
                self.split_disconnected_community(comm)?;
            }
        }
        Ok(())
    }

    fn is_community_connected(&self, community: usize) -> bool {
        let nodes = self.get_nodes_in_community(community);
        if nodes.len() <= 1 {
            return true;
        }

        let mut visited = HashSet::new();
        let mut stack = vec![nodes[0]];

        while let Some(node) = stack.pop() {
            if visited.insert(node) && node < self.adjacency_list.len() {
                for (neighbor, _) in &self.adjacency_list[node] {
                    if nodes.contains(neighbor) && !visited.contains(neighbor) {
                        stack.push(*neighbor);
                    }
                }
            }
        }

        visited.len() == nodes.len()
    }

    fn split_disconnected_community(
        &mut self,
        community: usize,
    ) -> Result<(), CommunityDetectionError> {
        let nodes = self.get_nodes_in_community(community);
        if nodes.is_empty() {
            return Ok(());
        }

        let components = self.find_connected_components(&nodes);
        for (i, component) in components.iter().enumerate() {
            let new_comm = if i == 0 {
                community
            } else {
                self.adjacency_list.len() + i
            };
            for &node in component {
                self.move_node(node, new_comm)?;
            }
        }
        Ok(())
    }

    fn find_connected_components(&self, nodes: &[usize]) -> Vec<Vec<usize>> {
        let node_set: HashSet<_> = nodes.iter().copied().collect();
        let mut visited = HashSet::new();
        let mut components = Vec::new();

        for &node in nodes {
            if !visited.contains(&node) {
                let mut component = Vec::new();
                let mut stack = vec![node];

                while let Some(current) = stack.pop() {
                    if visited.insert(current) && current < self.adjacency_list.len() {
                        component.push(current);
                        for (neighbor, _) in &self.adjacency_list[current] {
                            if node_set.contains(neighbor) && !visited.contains(neighbor) {
                                stack.push(*neighbor);
                            }
                        }
                    }
                }
                if self.config.deterministic {
                    component.sort_unstable();
                }
                components.push(component);
            }
        }
        components
    }

    fn merge_small_communities(&mut self, min_size: usize) -> Result<(), CommunityDetectionError> {
        let communities = self.get_communities();
        let mut to_merge: Vec<usize> = communities
            .iter()
            .filter(|(_, nodes)| nodes.len() < min_size)
            .map(|(comm, _)| *comm)
            .collect();
        if self.config.deterministic {
            to_merge.sort_unstable();
        }

        for comm in to_merge {
            let mut best_target = comm;
            let mut max_connections = 0.0;

            for node in &communities[&comm] {
                if *node < self.adjacency_list.len() {
                    for (neighbor, weight) in &self.adjacency_list[*node] {
                        let target = self
                            .node_to_community
                            .get(neighbor)
                            .copied()
                            .unwrap_or(*neighbor);
                        if target != comm
                            && communities.get(&target).map_or(0, |v| v.len()) >= min_size
                        {
                            let count = *weight;
                            if count > max_connections {
                                max_connections = count;
                                best_target = target;
                            }
                        }
                    }
                }
            }

            if best_target != comm {
                for node in &communities[&comm] {
                    self.move_node(*node, best_target)?;
                }
            }
        }
        Ok(())
    }

    fn refine_community_subset(
        &mut self,
        comm: usize,
        partition: &mut HashMap<usize, usize>,
    ) -> Result<(), CommunityDetectionError> {
        let mut nodes: Vec<usize> = self
            .node_to_community
            .iter()
            .filter(|(_, &c)| c == comm)
            .map(|(&n, _)| n)
            .collect();

        let max_passes = 10;
        let mut changed;

        for _ in 0..max_passes {
            changed = false;

            if self.config.deterministic {
                nodes.sort_unstable();
            } else {
                nodes.shuffle(&mut self.rng);
            }

            for &node in &nodes {
                if node >= self.adjacency_list.len() {
                    continue;
                }

                let current_comm = partition.get(&node).copied().unwrap_or(node);
                let mut best_comm = current_comm;
                let mut best_delta = f64::MIN;

                let k_i = self.community_weights.get(&node).copied().unwrap_or(0.0);
                let m = self.total_weight.max(f64::EPSILON);

                let mut neighbor_comms: Vec<usize> = self.adjacency_list[node]
                    .iter()
                    .map(|(n, _)| self.node_to_community.get(n).copied().unwrap_or(*n))
                    .collect::<HashSet<_>>()
                    .into_iter()
                    .collect();
                if self.config.deterministic {
                    neighbor_comms.sort_unstable();
                }

                for &neighbor_comm in &neighbor_comms {
                    if neighbor_comm != current_comm {
                        let sum_tot_new = self
                            .community_weights
                            .get(&neighbor_comm)
                            .copied()
                            .unwrap_or(0.0);
                        let sum_tot_old = self
                            .community_weights
                            .get(&current_comm)
                            .copied()
                            .unwrap_or(0.0);
                        let sum_in_new: f64 = self.adjacency_list[node]
                            .iter()
                            .filter(|(n, _)| {
                                self.node_to_community.get(n).copied().unwrap_or(*n)
                                    == neighbor_comm
                            })
                            .map(|(_, w)| w)
                            .sum();
                        let sum_in_old: f64 = self.adjacency_list[node]
                            .iter()
                            .filter(|(n, _)| {
                                self.node_to_community.get(n).copied().unwrap_or(*n) == current_comm
                            })
                            .map(|(_, w)| w)
                            .sum();

                        let delta_new = sum_in_new
                            - self.config.resolution * (sum_tot_new + k_i) * k_i / (2.0 * m);
                        let delta_old =
                            sum_in_old - self.config.resolution * sum_tot_old * k_i / (2.0 * m);
                        let delta = delta_new - delta_old;

                        if delta.is_nan() || delta.is_infinite() {
                            return Err(CommunityDetectionError::InvalidFloatResult(format!(
                                "Delta resulted in {} for node {}",
                                if delta.is_nan() { "NaN" } else { "infinity" },
                                node
                            )));
                        }

                        if delta > best_delta {
                            best_delta = delta;
                            best_comm = neighbor_comm;
                        }
                    }
                }

                if self.config.deterministic {
                    if best_delta > 0.0 && best_comm != current_comm {
                        partition.insert(node, best_comm);
                        changed = true;
                    }
                } else if best_delta > 0.0
                    && self.rng.random::<f64>() < best_delta.exp() / (1.0 + best_delta.exp())
                {
                    partition.insert(node, best_comm);
                    changed = true;
                }
            }

            if !changed {
                break;
            }
        }
        Ok(())
    }

    fn calculate_community_connections(
        node: usize,
        comm: usize,
        adjacency_list: &[Vec<(usize, f64)>],
        node_to_community: &HashMap<usize, usize>,
    ) -> f64 {
        if node >= adjacency_list.len() {
            return 0.0;
        }
        adjacency_list[node]
            .iter()
            .filter(|(n, _)| node_to_community.get(n).copied().unwrap_or(*n) == comm)
            .map(|(_, w)| w)
            .sum()
    }
}

#[cfg(test)]
#[cfg(feature = "graph")]
mod tests {
    use super::*;
    use crate::core::EdgeFiltered;
    use crate::graph::Graph;

    /// Two triangles joined by a single edge — the textbook two-community graph.
    fn barbell() -> (Graph<f64, usize, ()>, Vec<NodeId>) {
        let mut graph = Graph::<f64, usize, ()>::new(false);
        let nodes: Vec<_> = (0..6).map(|i| graph.add_node(i)).collect();
        for triangle in [[0, 1, 2], [3, 4, 5]] {
            for pair in [(0, 1), (1, 2), (0, 2)] {
                graph
                    .add_edge(nodes[triangle[pair.0]], nodes[triangle[pair.1]], 1.0, ())
                    .unwrap();
            }
        }
        graph.add_edge(nodes[2], nodes[3], 1.0, ()).unwrap();
        (graph, nodes)
    }

    #[test]
    fn test_every_node_is_placed_exactly_once() {
        let (graph, nodes) = barbell();
        let communities = graph.detect_communities(1.0).unwrap();

        let mut placed: Vec<NodeId> = communities.values().flatten().copied().collect();
        placed.sort_unstable();
        assert_eq!(placed, nodes);
    }

    #[test]
    fn test_a_seed_makes_the_partition_reproducible() {
        let (graph, _) = barbell();
        let config = CommunityConfig {
            gamma: 1.0,
            seed: Some(42),
            deterministic: true,
            ..CommunityConfig::default()
        };

        let first = graph
            .detect_communities_with_config(config.clone())
            .unwrap();
        for _ in 0..3 {
            assert_eq!(
                graph
                    .detect_communities_with_config(config.clone())
                    .unwrap(),
                first
            );
        }
    }

    #[test]
    fn test_modularity_stays_within_its_bounds() {
        let (graph, _) = barbell();
        let adjacency: Vec<Vec<(usize, f64)>> = graph
            .node_id_vec()
            .into_iter()
            .map(|node| {
                graph
                    .links(node)
                    // The Leiden state works on positions of its own, not node identifiers.
                    .map(|link| (link.target.index(), link.weight))
                    .collect()
            })
            .collect();

        let state = LeidenState::initialize(&adjacency, CommunityConfig::default()).unwrap();
        let modularity = state.calculate_modularity().unwrap();
        assert!((-1.0..=1.0).contains(&modularity));
    }

    #[test]
    fn test_communities_survive_sparse_ids() {
        let mut graph = Graph::<f64, usize, ()>::new(false);
        let a = graph.add_node(0);
        let gap = graph.add_node(1);
        let b = graph.add_node(2);
        let c = graph.add_node(3);
        graph.remove_node(gap).unwrap();
        graph.add_edge(a, b, 1.0, ()).unwrap();
        graph.add_edge(b, c, 1.0, ()).unwrap();

        let communities = graph.detect_communities(1.0).unwrap();
        let mut placed: Vec<NodeId> = communities.values().flatten().copied().collect();
        placed.sort_unstable();
        assert_eq!(placed, vec![a, b, c]);
    }

    #[test]
    fn test_detection_over_a_filtered_view() {
        let (graph, nodes) = barbell();
        // Drop the single edge joining the two triangles and they cannot be one community.
        let bridge = graph.edges_between(nodes[2], nodes[3])[0];
        let split = EdgeFiltered::new(&graph, move |edge| edge != bridge);

        let left: HashSet<NodeId> = nodes[0..3].iter().copied().collect();
        // Swept over seeds: no seed may put nodes from both components in one community,
        // since Leiden's defining guarantee is that the communities it reports are connected.
        for seed in (0..2000).map(|i| i * 7919 + 13) {
            let communities = split
                .detect_communities_with_config(CommunityConfig {
                    seed: Some(seed),
                    deterministic: true,
                    ..CommunityConfig::default()
                })
                .unwrap();
            for members in communities.values() {
                let members: HashSet<NodeId> = members.iter().copied().collect();
                assert!(
                    members.is_subset(&left) || members.is_disjoint(&left),
                    "seed {} produced a community spanning both components: {:?}",
                    seed,
                    members
                );
            }
        }
    }

    /// Leiden's defining guarantee is that the communities it reports are internally
    /// connected. Nothing had been enforcing it across aggregation levels: from the second
    /// aggregation onwards the coarser graph was built by indexing the *current* adjacency
    /// list with *original* node indices, so roughly a third of unseeded runs on this graph
    /// put nodes from two disconnected components into one community.
    #[test]
    fn test_communities_are_never_disconnected() {
        let (graph, nodes) = barbell();
        let bridge = graph.edges_between(nodes[2], nodes[3])[0];
        let split = EdgeFiltered::new(&graph, move |edge| edge != bridge);
        let left: HashSet<NodeId> = nodes[0..3].iter().copied().collect();

        // Unseeded, because the partition depends on hash iteration order as well as on
        // the RNG: fixing only the seed would not have exercised the failure.
        for run in 0..200 {
            let communities = split.detect_communities(1.0).unwrap();
            for members in communities.values() {
                let members: HashSet<NodeId> = members.iter().copied().collect();
                assert!(
                    members.is_subset(&left) || members.is_disjoint(&left),
                    "run {} produced a community spanning both components: {:?}",
                    run,
                    members
                );
            }
        }
    }
}