leiden-rs 0.7.0

//! Core Leiden algorithm implementation.

use std::borrow::Cow;

use rand::rngs::StdRng;
use rand::seq::SliceRandom;
use rand::SeedableRng;
#[cfg(feature = "rayon")]
use rayon::prelude::*;
use rustc_hash::{FxBuildHasher, FxHashMap};

use crate::algorithm;
use crate::partition::Partition;
use crate::quality::{GraphData, Modularity, MoveComponents, QualityFunction};

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};

/// Quality function selection for the Leiden algorithm.
#[derive(Debug, Clone, Copy, Default)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub enum QualityType {
    /// Newman-Girvan modularity (default).
    #[default]
    Modularity,
    /// Constant Potts Model.
    CPM,
    /// Reichardt-Bornholdt with configuration model null.
    RBConfiguration,
    /// Reichardt-Bornholdt with Erdős-Rényi null model.
    RBER,
}

/// Configuration for the Leiden algorithm.
#[derive(Debug, Clone)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct LeidenConfig {
    /// Maximum number of Leiden iterations (local move → refine → aggregate).
    pub max_iterations: usize,
    /// Resolution parameter γ controlling community granularity.
    pub resolution: f64,
    /// Optional RNG seed for reproducible results.
    pub seed: Option<u64>,
    /// Quality function to optimize.
    pub quality: QualityType,
    /// Convergence threshold: stop when quality improvement is below this value.
    pub epsilon: f64,
    /// Maximum number of nodes per community (0 = unlimited).
    pub max_comm_size: usize,
}

impl Default for LeidenConfig {
    fn default() -> Self {
        Self {
            max_iterations: 100,
            resolution: 1.0,
            seed: None,
            quality: QualityType::default(),
            epsilon: 1e-10,
            max_comm_size: 0,
        }
    }
}

impl LeidenConfig {
    /// Create a builder for configuring the Leiden algorithm.
    pub fn builder() -> LeidenConfigBuilder {
        LeidenConfigBuilder::default()
    }
}

/// Builder for [`LeidenConfig`].
#[derive(Debug, Clone, Default)]
pub struct LeidenConfigBuilder {
    max_iterations: Option<usize>,
    resolution: Option<f64>,
    seed: Option<u64>,
    quality: Option<QualityType>,
    epsilon: Option<f64>,
    max_comm_size: Option<usize>,
}

impl LeidenConfigBuilder {
    /// Set the maximum number of Leiden iterations.
    pub fn max_iterations(mut self, v: usize) -> Self {
        self.max_iterations = Some(v);
        self
    }

    /// Set the resolution parameter γ.
    pub fn resolution(mut self, v: f64) -> Self {
        self.resolution = Some(v);
        self
    }

    /// Set the RNG seed for reproducible results.
    pub fn seed(mut self, v: u64) -> Self {
        self.seed = Some(v);
        self
    }

    /// Set the quality function to optimize.
    pub fn quality(mut self, v: QualityType) -> Self {
        self.quality = Some(v);
        self
    }

    /// Set the convergence threshold.
    pub fn epsilon(mut self, v: f64) -> Self {
        self.epsilon = Some(v);
        self
    }

    /// Set the maximum number of nodes per community (0 = unlimited).
    pub fn max_comm_size(mut self, v: usize) -> Self {
        self.max_comm_size = Some(v);
        self
    }

    /// Build the configuration, applying defaults for unset fields.
    pub fn build(self) -> LeidenConfig {
        LeidenConfig {
            max_iterations: self.max_iterations.unwrap_or(100),
            resolution: self.resolution.unwrap_or(1.0),
            seed: self.seed,
            quality: self.quality.unwrap_or_default(),
            epsilon: self.epsilon.unwrap_or(1e-10),
            max_comm_size: self.max_comm_size.unwrap_or(0),
        }
    }
}

/// Result of running the Leiden algorithm, containing the partition and its quality score.
#[derive(Debug)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct LeidenOutput {
    /// The detected community partition.
    pub partition: Partition,
    /// The quality score of the partition (higher is better).
    pub quality: f64,
}

impl LeidenOutput {
    /// Create a new Leiden output with the given partition and quality score.
    pub fn new(partition: Partition, quality: f64) -> Self {
        Self { partition, quality }
    }
}

/// Owned quality function enum wrapping all supported quality functions.
///
/// Used internally to pass a quality function through the algorithm pipeline
/// without lifetime concerns. Implements [`QualityFunction`] by delegating
/// to the wrapped variant.
enum QualityFn {
    Modularity(Modularity),
    CPM(crate::quality::CPM),
    RBConfiguration(crate::quality::RBConfiguration),
    RBER(crate::quality::RBER),
}

impl QualityFunction for QualityFn {
    fn delta_move_from_components(&self, c: &MoveComponents) -> f64 {
        match self {
            Self::Modularity(q) => q.delta_move_from_components(c),
            Self::CPM(q) => q.delta_move_from_components(c),
            Self::RBConfiguration(q) => q.delta_move_from_components(c),
            Self::RBER(q) => q.delta_move_from_components(c),
        }
    }

    fn total_quality(&self, data: &GraphData, partition: &Partition) -> f64 {
        match self {
            Self::Modularity(q) => q.total_quality(data, partition),
            Self::CPM(q) => q.total_quality(data, partition),
            Self::RBConfiguration(q) => q.total_quality(data, partition),
            Self::RBER(q) => q.total_quality(data, partition),
        }
    }
}

/// The Leiden community detection algorithm.
pub struct Leiden {
    config: LeidenConfig,
}

impl Leiden {
    /// Create a new Leiden instance with the given configuration.
    pub fn new(config: LeidenConfig) -> Self {
        Self { config }
    }

    fn create_quality(&self) -> QualityFn {
        match self.config.quality {
            QualityType::Modularity => {
                QualityFn::Modularity(Modularity::with_resolution(self.config.resolution))
            }
            QualityType::CPM => QualityFn::CPM(crate::quality::CPM::new(self.config.resolution)),
            QualityType::RBConfiguration => QualityFn::RBConfiguration(
                crate::quality::RBConfiguration::with_resolution(self.config.resolution),
            ),
            QualityType::RBER => QualityFn::RBER(crate::quality::RBER::new(self.config.resolution)),
        }
    }

    /// Core Leiden iteration loop.
    ///
    /// Runs the three-phase cycle (local moving → refinement → aggregation)
    /// and calls `on_iteration` after each successful local-moving phase,
    /// allowing the caller to collect per-level information without
    /// duplicating the algorithm logic.
    ///
    /// The `on_iteration` closure receives `(data, partition, q_after,
    /// flat_mapping, original_n)`. For `run()` an empty closure is passed
    /// and the compiler eliminates it entirely via monomorphization.
    fn run_core<'a, F>(
        &self,
        input_data: &'a GraphData,
        quality: &QualityFn,
        on_iteration: &mut F,
    ) -> crate::error::Result<(Partition, f64)>
    where
        F: FnMut(&GraphData, &Partition, f64, &[usize], usize),
    {
        let original_n = input_data.node_count();
        let mut data: Cow<'a, GraphData> = Cow::Borrowed(input_data);
        let mut partition = Partition::new(data.node_count());
        let mut flat_mapping: Vec<usize> = (0..data.node_count()).collect();

        let mut rng = match self.config.seed {
            Some(seed) => StdRng::seed_from_u64(seed),
            None => StdRng::from_rng(&mut rand::rng()),
        };

        for _iter in 0..self.config.max_iterations {
            let q_before = quality.total_quality(&data, &partition);
            let changed = local_moving_dispatch(
                std::slice::from_ref(&*data),
                &mut partition,
                quality,
                &mut rng,
                self.config.max_comm_size,
                self.config.epsilon,
            );
            if !changed {
                break;
            }
            partition.renumber();

            let q_after = quality.total_quality(&data, &partition);

            on_iteration(&data, &partition, q_after, &flat_mapping, original_n);

            if (q_after - q_before).abs() < self.config.epsilon {
                break;
            }

            let refined = refinement(&data, &partition, quality, &mut rng, self.config.epsilon);

            let (agg_data, orig_to_agg, agg_initial_partition) =
                aggregate(&data, &refined, &partition);

            for orig_node in 0..original_n {
                flat_mapping[orig_node] = orig_to_agg[flat_mapping[orig_node]];
            }

            data = Cow::Owned(agg_data);
            partition = agg_initial_partition;

            if data.node_count() <= 1 {
                break;
            }
        }

        // Resolve aggregate nodes back to original node IDs.
        let mut result = Partition::from_membership(vec![0; original_n]);
        for (orig_node, &agg_node) in flat_mapping.iter().enumerate() {
            let comm = partition.community_of(agg_node);
            result.move_node(orig_node, comm);
        }
        result.renumber();
        // Compute quality on the original input graph, not the aggregated graph
        let q = quality.total_quality(input_data, &result);
        Ok((result, q))
    }

    /// Run the Leiden algorithm on the given graph.
    ///
    /// Returns a [`LeidenOutput`] containing the community partition and its quality score.
    pub fn run(&self, data: &GraphData) -> crate::error::Result<LeidenOutput> {
        if data.node_count() == 0 {
            return Ok(LeidenOutput::new(Partition::new(0), 0.0));
        }

        let quality = self.create_quality();
        let (partition, q) = self.run_core(data, &quality, &mut |_, _, _, _, _| {})?;
        Ok(LeidenOutput::new(partition, q))
    }

    /// Run the Leiden algorithm and capture intermediate community structure
    /// at each aggregation level.
    ///
    /// Returns a [`HierarchicalOutput`](crate::hierarchy::HierarchicalOutput)
    /// containing the final partition, quality, and per-level membership vectors.
    pub fn run_hierarchical(
        &self,
        data: &GraphData,
    ) -> crate::error::Result<crate::hierarchy::HierarchicalOutput> {
        use crate::hierarchy::{HierarchicalOutput, HierarchyLevel};

        if data.node_count() == 0 {
            return Ok(HierarchicalOutput {
                levels: vec![HierarchyLevel {
                    node_count: 0,
                    num_communities: 0,
                    quality: 0.0,
                    membership: vec![],
                }],
                partition: Partition::new(0),
                quality: 0.0,
            });
        }

        let quality = self.create_quality();
        let mut levels: Vec<HierarchyLevel> = Vec::new();
        let (partition, q) = self.run_core(
            data,
            &quality,
            &mut |data, part, q_after, flat_mapping, original_n| {
                let membership = resolve_to_original_nodes(flat_mapping, part, original_n);
                levels.push(HierarchyLevel {
                    node_count: data.node_count(),
                    num_communities: part.num_communities(),
                    quality: q_after,
                    membership,
                });
            },
        )?;

        Ok(HierarchicalOutput {
            levels,
            partition,
            quality: q,
        })
    }
}

fn resolve_to_original_nodes(
    flat_mapping: &[usize],
    partition: &Partition,
    original_n: usize,
) -> Vec<usize> {
    let mut result = vec![0; original_n];
    for orig_node in 0..original_n {
        let agg_node = flat_mapping[orig_node];
        result[orig_node] = partition.community_of(agg_node);
    }
    result
}

fn local_moving_dispatch(
    data: &[GraphData],
    partition: &mut Partition,
    quality: &(dyn QualityFunction + Sync),
    rng: &mut StdRng,
    max_comm_size: usize,
    epsilon: f64,
) -> bool {
    #[cfg(feature = "rayon")]
    {
        if should_use_parallel(&data[0]) {
            let (parallel_changed, converged_naturally) =
                local_moving_parallel(&data[0], partition, quality, rng, max_comm_size, epsilon);
            if converged_naturally {
                return parallel_changed;
            }
            let sequential_changed = algorithm::local_moving_generic(
                data,
                &[1.0],
                partition,
                quality,
                rng,
                max_comm_size,
                epsilon,
            );
            return parallel_changed || sequential_changed;
        }
    }
    algorithm::local_moving_generic(
        data,
        &[1.0],
        partition,
        quality,
        rng,
        max_comm_size,
        epsilon,
    )
}
/// Returns (colors: Vec<usize>, num_colors: usize) where colors[node] is the color assignment.
/// Uses at most max_degree + 1 colors. O(V + E) time.
#[cfg(feature = "rayon")]
fn greedy_coloring(data: &GraphData, order: &[usize]) -> (Vec<usize>, usize) {
    let n = data.node_count();
    let directed = data.is_directed();
    let mut colors = vec![0usize; n];
    let mut used_colors: Vec<bool> = Vec::new();
    let mut num_colors = 1usize;

    for &node in order {
        let (targets, _) = data.out_neighbor_slices(node);
        let max_neighbor_color = targets.iter().map(|&t| colors[t]).max().unwrap_or(0);
        if used_colors.len() <= max_neighbor_color {
            used_colors.resize(max_neighbor_color + 1, false);
        }
        for &neighbor in targets {
            used_colors[colors[neighbor]] = true;
        }
        if directed {
            let (in_targets, _) = data.in_neighbor_slices(node);
            let max_in_color = in_targets.iter().map(|&t| colors[t]).max().unwrap_or(0);
            if used_colors.len() <= max_in_color {
                used_colors.resize(max_in_color + 1, false);
            }
            for &neighbor in in_targets {
                used_colors[colors[neighbor]] = true;
            }
        }

        let mut color = 0;
        while color < used_colors.len() && used_colors[color] {
            color += 1;
        }
        colors[node] = color;
        if color + 1 > num_colors {
            num_colors = color + 1;
        }
        if color >= used_colors.len() {
            used_colors.resize(color + 1, false);
        }

        for &neighbor in targets {
            used_colors[colors[neighbor]] = false;
        }
        if directed {
            let (in_targets, _) = data.in_neighbor_slices(node);
            for &neighbor in in_targets {
                used_colors[colors[neighbor]] = false;
            }
        }
    }

    (colors, num_colors)
}

/// Decide whether to use parallel local moving based on graph structure.
/// MUST only depend on graph properties, NOT on runtime state (threads, load),
/// to ensure deterministic behavior (same graph → same code path → same result).
#[cfg(feature = "rayon")]
#[inline]
fn should_use_parallel(data: &GraphData) -> bool {
    let n = data.node_count();
    // Use edge slot count (total CSR entries) as the work estimate.
    // 2000 edge slots ≈ ~500 nodes × avg_degree 4, or ~200 nodes × avg_degree 10
    let edge_slots = data.out_offsets[n];
    edge_slots >= 2000 && n >= 100
}

/// Minimum number of edge slots (CSR entries) to use parallel aggregation.
#[cfg(feature = "rayon")]
pub(crate) const AGG_PARALLEL_THRESHOLD: usize = 10_000;

#[cfg(feature = "rayon")]
fn aggregate_edges_parallel(
    data: &GraphData,
    orig_to_agg: &[usize],
    directed: bool,
) -> FxHashMap<(usize, usize), f64> {
    use rayon::prelude::*;
    let n = data.node_count();
    (0..n)
        .into_par_iter()
        .fold(FxHashMap::<(usize, usize), f64>::default, |mut local, u| {
            algorithm::aggregate_node_edges_into(data, u, orig_to_agg, directed, &mut local);
            local
        })
        .reduce(
            FxHashMap::<(usize, usize), f64>::default,
            |mut acc, local| {
                for (k, v) in local {
                    *acc.entry(k).or_default() += v;
                }
                acc
            },
        )
}

#[cfg(feature = "rayon")]
fn local_moving_parallel(
    data: &GraphData,
    partition: &mut Partition,
    quality: &(dyn QualityFunction + Sync),
    rng: &mut StdRng,
    max_comm_size: usize,
    epsilon: f64,
) -> (bool, bool) {
    let n = data.node_count();
    if n == 0 {
        return (false, true);
    }

    let directed = data.is_directed();

    let m = data.total_weight();
    if m <= 0.0 {
        return (false, true);
    }
    let two_m = 2.0 * m;
    let total_node_weight: f64 = data.total_node_weight();

    let mut order: Vec<usize> = (0..n).filter(|&node| data.degree_of(node) > 0.0).collect();
    order.shuffle(rng);
    let (colors, num_colors) = greedy_coloring(data, &order);

    let mut color_groups: Vec<Vec<usize>> = vec![Vec::new(); num_colors];
    for &node in &order {
        color_groups[colors[node]].push(node);
    }

    let (mut community_total_degree, mut community_in_degree, mut community_size) =
        algorithm::init_community_stats(n, std::slice::from_ref(data), |node| {
            partition.community_of(node)
        });

    let mut changed = false;
    let mut any_move = true;
    let mut iteration = 0usize;
    let max_rounds = 100;

    while any_move && iteration < max_rounds {
        any_move = false;
        iteration += 1;

        for group in &color_groups {
            if group.is_empty() {
                continue;
            }

            let moves: Vec<(usize, usize, usize, f64, f64, f64)> = group
                .par_iter()
                .filter_map(|&node| {
                    let current_community = partition.community_of(node);
                    let k_v_out = data.out_degree_of(node);
                    let k_v_in = if directed {
                        data.in_degree_of(node)
                    } else {
                        0.0
                    };
                    let node_weight = data.node_weight(node);

                    let (targets, weights) = data.out_neighbor_slices(node);
                    let mut neighbor_comm_weights: FxHashMap<usize, f64> =
                        FxHashMap::with_capacity_and_hasher(
                            targets.len(),
                            FxBuildHasher::default(),
                        );
                    let mut k_v_to_current_out = 0.0f64;

                    for i in 0..targets.len() {
                        let neighbor = targets[i];
                        let weight = weights[i];
                        if neighbor == node {
                            continue;
                        }
                        let comm = partition.community_of(neighbor);
                        if comm == current_community {
                            k_v_to_current_out += weight;
                        } else {
                            *neighbor_comm_weights.entry(comm).or_default() += weight;
                        }
                    }

                    let (in_targets, in_weights) = if directed {
                        data.in_neighbor_slices(node)
                    } else {
                        (&[] as &[usize], &[] as &[f64])
                    };
                    let mut in_neighbor_comm_weights: FxHashMap<usize, f64> =
                        FxHashMap::with_capacity_and_hasher(
                            in_targets.len(),
                            FxBuildHasher::default(),
                        );
                    let mut k_v_to_current_in = 0.0f64;
                    if directed {
                        for i in 0..in_targets.len() {
                            let neighbor = in_targets[i];
                            let weight = in_weights[i];
                            if neighbor == node {
                                continue;
                            }
                            let comm = partition.community_of(neighbor);
                            if comm == current_community {
                                k_v_to_current_in += weight;
                            } else {
                                *in_neighbor_comm_weights.entry(comm).or_default() += weight;
                            }
                        }
                    }

                    let sigma_tot_current_out = community_total_degree[current_community];
                    let sigma_tot_current_in = if directed {
                        community_in_degree[current_community]
                    } else {
                        0.0
                    };

                    let candidates = neighbor_comm_weights.keys().copied();
                    let (best_community, _) = algorithm::find_best_community(
                        candidates,
                        current_community,
                        epsilon,
                        max_comm_size,
                        &community_size,
                        node_weight,
                        |target_comm| {
                            let k_v_to_target_out = neighbor_comm_weights[&target_comm];
                            let k_v_to_target_in = if directed {
                                in_neighbor_comm_weights
                                    .get(&target_comm)
                                    .copied()
                                    .unwrap_or(0.0)
                            } else {
                                0.0
                            };
                            quality.delta_move_from_components(&MoveComponents {
                                two_m,
                                node_weight,
                                total_node_weight,
                                k_v_out,
                                k_v_to_target_out,
                                k_v_to_current_out,
                                sigma_tot_target_out: community_total_degree[target_comm],
                                sigma_tot_current_out,
                                k_v_in,
                                k_v_to_target_in,
                                k_v_to_current_in,
                                sigma_tot_target_in: if directed {
                                    community_in_degree[target_comm]
                                } else {
                                    0.0
                                },
                                sigma_tot_current_in,
                                n_target: community_size[target_comm],
                                n_current: community_size[current_community],
                                directed,
                            })
                        },
                    );

                    if best_community != current_community {
                        Some((
                            node,
                            current_community,
                            best_community,
                            k_v_out,
                            k_v_in,
                            node_weight,
                        ))
                    } else {
                        None
                    }
                })
                .collect();

            for (node, old_comm, new_comm, k_v_out, k_v_in, node_weight) in moves {
                algorithm::apply_move(
                    Some(&mut *partition),
                    None,
                    node,
                    old_comm,
                    new_comm,
                    k_v_out,
                    k_v_in,
                    node_weight,
                    &mut community_total_degree,
                    &mut community_in_degree,
                    &mut community_size,
                );
                any_move = true;
                changed = true;
            }
        }
    }

    (changed, !any_move)
}

fn refinement(
    data: &GraphData,
    partition: &Partition,
    quality: &(dyn QualityFunction + Sync),
    rng: &mut StdRng,
    epsilon: f64,
) -> Partition {
    if data.total_weight() <= 0.0 {
        return Partition::new(data.node_count());
    }
    let layers = std::slice::from_ref(data);
    algorithm::refinement_generic(data.node_count(), partition, rng, |community, nodes| {
        algorithm::refine_community_generic(
            layers,
            &[1.0],
            partition,
            quality,
            community,
            nodes,
            epsilon,
        )
    })
}

fn aggregate_edges_sequential(
    data: &GraphData,
    orig_to_agg: &[usize],
    directed: bool,
) -> FxHashMap<(usize, usize), f64> {
    let n = data.node_count();
    let mut agg_edges: FxHashMap<(usize, usize), f64> = FxHashMap::default();
    for u in 0..n {
        algorithm::aggregate_node_edges_into(data, u, orig_to_agg, directed, &mut agg_edges);
    }
    agg_edges
}

fn aggregate(
    data: &GraphData,
    refined_partition: &Partition,
    coarse_partition: &Partition,
) -> (GraphData, Vec<usize>, Partition) {
    let n = data.node_count();
    let (orig_to_agg, agg_n) = algorithm::build_orig_to_agg_mapping(n, refined_partition);

    let directed = data.is_directed();
    let agg_edges_map: FxHashMap<(usize, usize), f64> = {
        #[cfg(feature = "rayon")]
        {
            let edge_slots = data.out_offsets[n];
            if edge_slots >= AGG_PARALLEL_THRESHOLD {
                aggregate_edges_parallel(data, &orig_to_agg, directed)
            } else {
                aggregate_edges_sequential(data, &orig_to_agg, directed)
            }
        }
        #[cfg(not(feature = "rayon"))]
        {
            aggregate_edges_sequential(data, &orig_to_agg, directed)
        }
    };

    algorithm::build_aggregated_graph(
        orig_to_agg,
        agg_n,
        directed,
        agg_edges_map,
        coarse_partition,
        |orig| data.node_weight(orig),
    )
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::graph::{GraphData, GraphDataBuilder};
    use rand::prelude::IndexedRandom;

    fn make_two_cliques() -> GraphData {
        let mut b = GraphDataBuilder::new(10);
        for i in 0..5 {
            for j in (i + 1)..5 {
                b.add_edge(i, j, 1.0).unwrap();
            }
        }
        for i in 5..10 {
            for j in (i + 1)..10 {
                b.add_edge(i, j, 1.0).unwrap();
            }
        }
        b.add_edge(0, 5, 1.0).unwrap();
        b.build().unwrap()
    }

    #[test]
    fn test_two_cliques() {
        let graph = make_two_cliques();
        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&graph).unwrap().partition;

        assert_eq!(partition.num_communities(), 2);

        let comm0 = partition.community_of(0);
        for i in 1..5 {
            assert_eq!(partition.community_of(i), comm0, "node {i}");
        }
        let comm5 = partition.community_of(5);
        for i in 6..10 {
            assert_eq!(partition.community_of(i), comm5, "node {i}");
        }
        assert_ne!(comm0, comm5);
    }

    #[test]
    fn test_single_node() {
        let data = GraphDataBuilder::new(1).build().unwrap();

        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;
        assert_eq!(partition.num_communities(), 1);
    }

    #[test]
    fn test_ring_of_cliques() {
        let mut b = GraphDataBuilder::new(12);

        for i in 0..4 {
            for j in (i + 1)..4 {
                b.add_edge(i, j, 1.0).unwrap();
            }
        }
        for i in 4..8 {
            for j in (i + 1)..8 {
                b.add_edge(i, j, 1.0).unwrap();
            }
        }
        for i in 8..12 {
            for j in (i + 1)..12 {
                b.add_edge(i, j, 1.0).unwrap();
            }
        }
        b.add_edge(0, 4, 0.1).unwrap();
        b.add_edge(4, 8, 0.1).unwrap();
        b.add_edge(8, 0, 0.1).unwrap();

        let data = b.build().unwrap();
        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;

        assert_eq!(partition.num_communities(), 3);
    }

    #[test]
    fn test_empty_graph() {
        let data = GraphDataBuilder::new(0).build().unwrap();
        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;
        assert_eq!(partition.num_communities(), 0);
    }

    #[test]
    fn test_disconnected_graph() {
        let mut b = GraphDataBuilder::new(6);

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

        let data = b.build().unwrap();
        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;

        assert_eq!(partition.num_communities(), 2);

        let comm0 = partition.community_of(0);
        assert_eq!(partition.community_of(1), comm0);
        assert_eq!(partition.community_of(2), comm0);

        let comm3 = partition.community_of(3);
        assert_eq!(partition.community_of(4), comm3);
        assert_eq!(partition.community_of(5), comm3);

        assert_ne!(comm0, comm3);
    }

    #[test]
    fn test_single_edge() {
        let mut b = GraphDataBuilder::new(2);
        b.add_edge(0, 1, 1.0).unwrap();
        let data = b.build().unwrap();

        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;

        assert_eq!(partition.num_communities(), 1);
        assert_eq!(partition.community_of(0), partition.community_of(1));
    }

    #[test]
    fn test_weighted_graph() {
        let mut b = GraphDataBuilder::new(6);

        for i in 0..3 {
            for j in (i + 1)..3 {
                b.add_edge(i, j, 5.0).unwrap();
            }
        }
        for i in 3..6 {
            for j in (i + 1)..6 {
                b.add_edge(i, j, 5.0).unwrap();
            }
        }
        b.add_edge(0, 3, 0.1).unwrap();

        let data = b.build().unwrap();
        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;

        assert_eq!(partition.num_communities(), 2);

        let comm0 = partition.community_of(0);
        for i in 1..3 {
            assert_eq!(partition.community_of(i), comm0, "node {i}");
        }
        let comm3 = partition.community_of(3);
        for i in 4..6 {
            assert_eq!(partition.community_of(i), comm3, "node {i}");
        }
        assert_ne!(comm0, comm3);
    }

    #[test]
    fn test_large_random_graph_determinism() {
        let mut rng = StdRng::seed_from_u64(12345);

        let mut builder = GraphDataBuilder::new(100);

        let clusters: Vec<Vec<usize>> = (0..4).map(|c| (c * 25..(c + 1) * 25).collect()).collect();

        for cluster in &clusters {
            for &node in cluster {
                let others: Vec<usize> = cluster.iter().filter(|&&x| x != node).copied().collect();
                let count = std::cmp::min(5, others.len());
                let chosen: Vec<usize> = others.choose_multiple(&mut rng, count).copied().collect();
                for &neighbor in &chosen {
                    if neighbor > node {
                        builder.add_edge(node, neighbor, 1.0).unwrap();
                    }
                }
            }
        }

        for i in 0..4 {
            for j in (i + 1)..4 {
                let mut pairs: Vec<(usize, usize)> = Vec::new();
                for &a in &clusters[i] {
                    for &bb in &clusters[j] {
                        pairs.push((a, bb));
                    }
                }
                let count = std::cmp::min(3, pairs.len());
                for &(a, b) in pairs.choose_multiple(&mut rng, count) {
                    builder.add_edge(a, b, 0.1).unwrap();
                }
            }
        }

        let data = builder.build().unwrap();

        let leiden = Leiden::new(LeidenConfig {
            seed: Some(42),
            ..Default::default()
        });
        let partition1 = leiden.run(&data).unwrap().partition;

        let leiden2 = Leiden::new(LeidenConfig {
            seed: Some(42),
            ..Default::default()
        });
        let partition2 = leiden2.run(&data).unwrap().partition;

        assert_eq!(
            partition1.as_slice(),
            partition2.as_slice(),
            "same seed should produce identical partitions"
        );
        assert!(
            partition1.num_communities() >= 2,
            "expected at least 2 communities, got {}",
            partition1.num_communities()
        );
    }

    #[test]
    fn test_star_graph() {
        let mut b = GraphDataBuilder::new(11);
        for i in 1..11 {
            b.add_edge(0, i, 1.0).unwrap();
        }
        let data = b.build().unwrap();

        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;

        assert!(partition.num_communities() >= 1);
    }

    #[test]
    fn test_isolated_nodes_with_edges() {
        let mut b = GraphDataBuilder::new(9);
        for i in 0..4 {
            for j in (i + 1)..4 {
                b.add_edge(i, j, 1.0).unwrap();
            }
        }
        for i in 4..8 {
            for j in (i + 1)..8 {
                b.add_edge(i, j, 1.0).unwrap();
            }
        }
        let data = b.build().unwrap();

        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;

        assert_eq!(partition.num_communities(), 3);

        let comm0 = partition.community_of(0);
        for i in 1..4 {
            assert_eq!(partition.community_of(i), comm0, "node {i}");
        }
        let comm4 = partition.community_of(4);
        for i in 5..8 {
            assert_eq!(partition.community_of(i), comm4, "node {i}");
        }
        let comm8 = partition.community_of(8);
        assert_ne!(comm8, comm0);
        assert_ne!(comm8, comm4);
    }

    #[test]
    fn test_seed_determinism_different_seeds() {
        let graph = make_two_cliques();

        let config1 = LeidenConfig {
            seed: Some(1),
            ..Default::default()
        };
        let leiden1 = Leiden::new(config1);
        let partition1 = leiden1.run(&graph).unwrap().partition;

        let config2 = LeidenConfig {
            seed: Some(2),
            ..Default::default()
        };
        let leiden2 = Leiden::new(config2);
        let partition2 = leiden2.run(&graph).unwrap().partition;

        assert_eq!(partition1.num_communities(), 2);
        assert_eq!(partition2.num_communities(), 2);
    }

    #[test]
    fn test_self_loop() {
        let mut b = GraphDataBuilder::new(4);
        b.add_edge(0, 1, 1.0).unwrap();
        b.add_edge(2, 3, 1.0).unwrap();
        b.add_edge(0, 0, 2.0).unwrap();
        let data = b.build().unwrap();

        let leiden = Leiden::new(LeidenConfig::default());
        let partition = leiden.run(&data).unwrap().partition;

        assert_eq!(partition.num_communities(), 2);
        assert_eq!(partition.community_of(0), partition.community_of(1));
        assert_eq!(partition.community_of(2), partition.community_of(3));
        assert_ne!(partition.community_of(0), partition.community_of(2));
    }

    #[test]
    fn test_hierarchical_matches_run() {
        let graph = make_two_cliques();
        let leiden = Leiden::new(LeidenConfig {
            seed: Some(42),
            ..Default::default()
        });
        let normal = leiden.run(&graph).unwrap();
        let hierarchical = leiden.run_hierarchical(&graph).unwrap();

        assert_eq!(
            normal.partition.as_slice(),
            hierarchical.partition.as_slice()
        );
        assert!((normal.quality - hierarchical.quality).abs() < 1e-10);
        assert!(!hierarchical.levels.is_empty());
    }

    #[test]
    fn test_hierarchical_levels_decrease_nodes() {
        let graph = make_two_cliques();
        let leiden = Leiden::new(LeidenConfig {
            seed: Some(42),
            ..Default::default()
        });
        let h = leiden.run_hierarchical(&graph).unwrap();

        for window in h.levels.windows(2) {
            assert!(window[1].node_count <= window[0].node_count);
        }

        if !h.levels.is_empty() {
            let last_level = &h.levels[h.levels.len() - 1];
            for node in 0..graph.node_count() {
                assert_eq!(last_level.membership[node], h.partition.community_of(node));
            }
        }
    }

    #[test]
    fn test_hierarchical_community_of_at_level() {
        let graph = make_two_cliques();
        let leiden = Leiden::new(LeidenConfig {
            seed: Some(42),
            ..Default::default()
        });
        let h = leiden.run_hierarchical(&graph).unwrap();

        if h.levels.len() >= 2 {
            assert!(h.levels[0].num_communities >= h.partition.num_communities());
        }
    }

    #[test]
    #[cfg(feature = "rayon")]
    fn test_coloring_basic() {
        let data = make_two_cliques();
        let order: Vec<usize> = (0..data.node_count()).collect();
        let (colors, num_colors) = greedy_coloring(&data, &order);

        for node in 0..data.node_count() {
            let (targets, _) = data.neighbor_slices(node);
            for &neighbor in targets {
                if neighbor != node {
                    assert_ne!(
                        colors[node], colors[neighbor],
                        "Adjacent nodes {} and {} have same color {}",
                        node, neighbor, colors[node]
                    );
                }
            }
        }
        assert!(num_colors > 0);
    }

    #[test]
    fn test_parallel_matches_sequential() {
        let graph = make_two_cliques();
        let leiden = Leiden::new(LeidenConfig {
            seed: Some(42),
            ..Default::default()
        });
        let result_normal = leiden.run(&graph).unwrap();
        assert!(result_normal.partition.num_communities() >= 1);
    }
}