leiden-rs 0.7.1

//! Shared algorithm internals for single-layer and multiplex Leiden.

use std::collections::VecDeque;

use crate::graph::GraphData;
use crate::graph::GraphDataBuilder;
use crate::partition::Partition;
use crate::quality::{MoveComponents, QualityFunction};
use rand::rngs::StdRng;
use rand::seq::SliceRandom;
use rustc_hash::FxHashMap;

/// Pre-allocated buffers for the local-moving phase, reused across iterations.
///
/// Eliminates per-iteration heap allocations in `local_moving_generic` by
/// maintaining buffers that grow to the maximum needed size and are cleared
/// (not freed) between calls.
pub(crate) struct LocalMovingBuffers {
    /// Per-community total out-degree: `comm_total_degree[comm]`.
    pub comm_total_degree: Vec<f64>,
    /// Per-community total in-degree: `comm_in_degree[comm]` (empty for undirected).
    pub comm_in_degree: Vec<f64>,
    /// Per-community weighted size: `comm_size[comm]`.
    pub comm_size: Vec<f64>,
    /// Per-layer per-community out-edge weight from the current node.
    pub layer_out_weights: Vec<Vec<f64>>,
    /// Per-layer per-community in-edge weight from the current node.
    pub layer_in_weights: Vec<Vec<f64>>,
    /// Communities whose weight buffers are non-zero and need clearing.
    pub touched_list: Vec<usize>,
    /// Mark array for touched communities.
    pub touched_mark: Vec<bool>,
    /// Whether a node is currently in the work queue.
    pub in_queue: Vec<bool>,
    /// Per-layer `2 * total_weight` values.
    pub two_m_values: Vec<f64>,
}

impl LocalMovingBuffers {
    /// Create buffers pre-allocated for `capacity` nodes and `num_layers` layers.
    pub fn new(capacity: usize, num_layers: usize) -> Self {
        Self {
            comm_total_degree: vec![0.0; capacity],
            comm_in_degree: vec![0.0; capacity],
            comm_size: vec![0.0; capacity],
            layer_out_weights: vec![vec![0.0; capacity]; num_layers],
            layer_in_weights: vec![vec![0.0; capacity]; num_layers],
            touched_list: Vec::with_capacity(64),
            touched_mark: vec![false; capacity],
            in_queue: vec![false; capacity],
            two_m_values: vec![0.0; num_layers],
        }
    }

    /// Ensure buffers can hold at least `n` communities and `num_layers` layers,
    /// then clear them for reuse. Does not shrink.
    pub fn resize_and_clear(&mut self, n: usize, num_layers: usize) {
        if n > self.comm_total_degree.len() {
            self.comm_total_degree.resize(n, 0.0);
            self.comm_in_degree.resize(n, 0.0);
            self.comm_size.resize(n, 0.0);
            self.touched_mark.resize(n, false);
            self.in_queue.resize(n, false);
        }
        self.comm_total_degree[..n].fill(0.0);
        self.comm_in_degree[..n].fill(0.0);
        self.comm_size[..n].fill(0.0);
        self.touched_mark[..n].fill(false);
        self.in_queue[..n].fill(false);

        if num_layers > self.layer_out_weights.len() {
            self.layer_out_weights
                .resize_with(num_layers, || vec![0.0; n]);
            self.layer_in_weights
                .resize_with(num_layers, || vec![0.0; n]);
        }
        for lw in &mut self.layer_out_weights[..num_layers] {
            if n > lw.len() {
                lw.resize(n, 0.0);
            }
            lw[..n].fill(0.0);
        }
        for lw in &mut self.layer_in_weights[..num_layers] {
            if n > lw.len() {
                lw.resize(n, 0.0);
            }
            lw[..n].fill(0.0);
        }

        if num_layers > self.two_m_values.len() {
            self.two_m_values.resize(num_layers, 0.0);
        }

        for &idx in &self.touched_list {
            if idx < self.touched_mark.len() {
                self.touched_mark[idx] = false;
            }
        }
        self.touched_list.clear();
    }
}

/// Pre-allocated buffers for refinement phase, reused across communities.
///
/// Eliminates repeated allocations in `refine_community_generic` by maintaining
/// buffers that can be resized and cleared between community refinements.
pub(crate) struct RefinementBuffers {
    comm_total_degree: Vec<f64>,
    comm_in_degree: Vec<f64>,
    comm_size: Vec<f64>,
    layer_out_weights: Vec<Vec<f64>>,
    layer_in_weights: Vec<Vec<f64>>,
    touched_list: Vec<usize>,
    touched_mark: Vec<bool>,
    /// Per-layer `2 * total_weight` values.
    two_m_values: Vec<f64>,
}

impl RefinementBuffers {
    pub fn new(capacity: usize, num_layers: usize) -> Self {
        Self {
            comm_total_degree: vec![0.0; capacity],
            comm_in_degree: vec![0.0; capacity],
            comm_size: vec![0.0; capacity],
            layer_out_weights: vec![vec![0.0; capacity]; num_layers],
            layer_in_weights: vec![vec![0.0; capacity]; num_layers],
            touched_list: Vec::with_capacity(64),
            touched_mark: vec![false; capacity],
            two_m_values: vec![0.0; num_layers],
        }
    }

    /// Ensure buffers can hold at least `new_capacity` entries, then clear
    /// them for reuse. Also populates `two_m_values` from `layers`.
    pub fn resize_and_clear(&mut self, new_capacity: usize, layers: &[GraphData]) {
        if new_capacity > self.comm_total_degree.len() {
            self.comm_total_degree.resize(new_capacity, 0.0);
            self.comm_in_degree.resize(new_capacity, 0.0);
            self.comm_size.resize(new_capacity, 0.0);
            for layer_weights in &mut self.layer_out_weights {
                layer_weights.resize(new_capacity, 0.0);
            }
            for layer_weights in &mut self.layer_in_weights {
                layer_weights.resize(new_capacity, 0.0);
            }
            self.touched_mark.resize(new_capacity, false);
        }
        self.comm_total_degree[..new_capacity].fill(0.0);
        self.comm_in_degree[..new_capacity].fill(0.0);
        self.comm_size[..new_capacity].fill(0.0);
        for layer_weights in &mut self.layer_out_weights {
            layer_weights[..new_capacity].fill(0.0);
        }
        for layer_weights in &mut self.layer_in_weights {
            layer_weights[..new_capacity].fill(0.0);
        }
        for &idx in &self.touched_list {
            self.touched_mark[idx] = false;
        }
        self.touched_list.clear();

        let num_layers = layers.len();
        if num_layers > self.two_m_values.len() {
            self.two_m_values.resize(num_layers, 0.0);
        }
        for (l, layer) in layers.iter().enumerate() {
            self.two_m_values[l] = 2.0 * layer.total_weight();
        }
    }
}

/// Find the best community to move a node to.
///
/// `delta_fn(target_comm) -> f64` returns the quality delta for moving to that community.
/// Returns `(best_community, best_delta)`. Stays at current if no improvement > epsilon.
#[inline]
pub(crate) fn find_best_community(
    candidates: impl Iterator<Item = usize>,
    current_community: usize,
    epsilon: f64,
    max_comm_size: usize,
    comm_size: &[f64],
    node_weight: f64,
    delta_fn: impl Fn(usize) -> f64,
) -> (usize, f64) {
    let mut best_community = current_community;
    let mut best_delta = epsilon;
    for target_comm in candidates {
        if max_comm_size > 0 && comm_size[target_comm] + node_weight > max_comm_size as f64 {
            continue;
        }
        let delta = delta_fn(target_comm);
        if delta > best_delta {
            best_delta = delta;
            best_community = target_comm;
        }
    }
    (best_community, best_delta)
}

/// Target for a community move: either a partition or a refined map.
pub(crate) enum MoveTarget<'a> {
    /// Local moving phase: update the partition directly.
    Partition(&'a mut Partition),
    /// Refinement phase: update the refined map array.
    RefinedMap(&'a mut [usize]),
}

/// Apply a community move and update statistics arrays.
///
/// In-degree update only when `comm_in_degree` is non-empty.
#[inline]
pub(crate) fn apply_move(
    target: MoveTarget<'_>,
    node: usize,
    old_comm: usize,
    new_comm: usize,
    k_v_out: f64,
    k_v_in: f64,
    node_weight: f64,
    comm_total_degree: &mut [f64],
    comm_in_degree: &mut [f64],
    comm_size: &mut [f64],
) {
    match target {
        MoveTarget::RefinedMap(map) => map[node] = new_comm,
        MoveTarget::Partition(partition) => partition.move_node(node, new_comm),
    }
    comm_total_degree[old_comm] -= k_v_out;
    comm_total_degree[new_comm] += k_v_out;
    if !comm_in_degree.is_empty() {
        comm_in_degree[old_comm] -= k_v_in;
        comm_in_degree[new_comm] += k_v_in;
    }
    comm_size[old_comm] -= node_weight;
    comm_size[new_comm] += node_weight;
}

/// Initialize community statistics directly into the provided slices.
///
/// `community_of_fn` maps node -> community index.
/// Writes into `comm_total_degree_out`, `comm_in_degree_out`, `comm_size_out`.
pub(crate) fn init_community_stats_into(
    layers: &[GraphData],
    community_of_fn: impl Fn(usize) -> usize,
    comm_total_degree_out: &mut [f64],
    comm_in_degree_out: &mut [f64],
    comm_size_out: &mut [f64],
) {
    for layer in layers {
        for node in 0..comm_total_degree_out.len() {
            let comm = community_of_fn(node);
            comm_total_degree_out[comm] += layer.out_degree_of(node);
            comm_in_degree_out[comm] += layer.in_degree_of(node);
            comm_size_out[comm] += layer.node_weight(node);
        }
    }
}

/// Accumulate one node's edges into the aggregated edge map.
///
/// For directed graphs: maps (u→v) through orig_to_agg.
/// For undirected graphs: canonicalizes keys to (min, max) to avoid double-counting;
/// self-loops use (u, u); skips edges where v <= u (each undirected edge stored twice in CSR).
#[inline]
pub(crate) fn aggregate_node_edges_into(
    source: &GraphData,
    u: usize,
    orig_to_agg: &[usize],
    directed: bool,
    map: &mut FxHashMap<(usize, usize), f64>,
) {
    let ru = orig_to_agg[u];
    if directed {
        for (v, w) in source.neighbors(u) {
            let rv = orig_to_agg[v];
            *map.entry((ru, rv)).or_default() += w;
        }
    } else {
        for (v, w) in source.neighbors(u) {
            if u == v {
                *map.entry((ru, ru)).or_default() += w;
            } else if v > u {
                let rv = orig_to_agg[v];
                let key = if ru <= rv { (ru, rv) } else { (rv, ru) };
                *map.entry(key).or_default() += w;
            }
        }
    }
}

/// Build the orig_to_agg mapping from a refined partition.
///
/// Returns `(orig_to_agg, agg_n)` where `orig_to_agg[original_node] = aggregate_node_id`
/// and `agg_n` is the number of aggregate nodes.
pub(crate) fn build_orig_to_agg_mapping(
    n: usize,
    refined_partition: &Partition,
) -> (Vec<usize>, usize) {
    let mut orig_to_agg: Vec<usize> = vec![0; n];
    let mut comm_to_agg: FxHashMap<usize, usize> = FxHashMap::default();
    let mut next_id = 0usize;
    for (node, entry) in orig_to_agg.iter_mut().enumerate() {
        let c = refined_partition.community_of(node);
        let agg_id = *comm_to_agg.entry(c).or_insert_with(|| {
            let id = next_id;
            next_id += 1;
            id
        });
        *entry = agg_id;
    }
    (orig_to_agg, next_id)
}

/// Build the aggregated graph from collected edges and node weights.
///
/// Takes ownership of `orig_to_agg` and returns `(GraphData, Vec<usize>, Partition)`.
/// The `node_weight_fn` closure provides the weight for each original node.
pub(crate) fn build_aggregated_graph(
    orig_to_agg: Vec<usize>,
    agg_n: usize,
    directed: bool,
    agg_edges_map: FxHashMap<(usize, usize), f64>,
    coarse_partition: &Partition,
    node_weight_fn: impl Fn(usize) -> f64,
) -> crate::error::Result<(crate::graph::GraphData, Vec<usize>, Partition)> {
    let mut agg_edges: Vec<((usize, usize), f64)> = agg_edges_map.into_iter().collect();
    agg_edges.sort_by_key(|&((u, v), _)| (u, v));

    let mut agg_node_weight: Vec<f64> = vec![0.0; agg_n];
    for (orig, &agg_node) in orig_to_agg.iter().enumerate() {
        agg_node_weight[agg_node] += node_weight_fn(orig);
    }

    let mut builder = GraphDataBuilder::new(agg_n);
    if directed {
        builder = builder.directed();
    }
    for &((u, v), w) in &agg_edges {
        builder.add_edge(u, v, w)?;
    }
    for (node, &nw) in agg_node_weight.iter().enumerate() {
        if nw != 1.0 {
            builder.set_node_weight(node, nw)?;
        }
    }
    let agg_data = builder.build()?;

    let mut agg_initial = Partition::new(agg_n);
    for (orig, &agg_node) in orig_to_agg.iter().enumerate() {
        let coarse_comm = coarse_partition.community_of(orig);
        agg_initial.move_node(agg_node, coarse_comm);
    }
    agg_initial.renumber();

    Ok((agg_data, orig_to_agg, agg_initial))
}

/// Generic refinement wrapper: collect community nodes, shuffle, dispatch refinement
/// per community (sequential or parallel), and apply moves.
///
/// The `refine_fn` closure receives `(community_index, community_node_list, &mut buffers)` and
/// returns a list of `(node, new_community)` moves.
pub(crate) fn refinement_generic(
    n: usize,
    num_layers: usize,
    partition: &Partition,
    rng: &mut StdRng,
    refine_fn: impl Fn(usize, &[usize], &mut RefinementBuffers) -> Vec<(usize, usize)> + Send + Sync,
) -> Partition {
    let mut refined = Partition::new(n);

    let num_comms = partition.num_communities();
    let mut community_nodes: Vec<Vec<usize>> = vec![Vec::new(); num_comms];
    for node in 0..n {
        community_nodes[partition.community_of(node)].push(node);
    }
    for nodes in &mut community_nodes {
        nodes.shuffle(rng);
    }

    let results: Vec<Vec<(usize, usize)>> = {
        #[cfg(feature = "rayon")]
        {
            let par_threshold = std::cmp::max(4, rayon::current_num_threads() * 2);
            if num_comms > par_threshold {
                use rayon::prelude::*;
                community_nodes
                    .par_iter()
                    .enumerate()
                    .map_init(
                        || RefinementBuffers::new(n, num_layers),
                        |buffers, (community, nodes)| refine_fn(community, nodes, buffers),
                    )
                    .collect()
            } else {
                let mut buffers = RefinementBuffers::new(n, num_layers);
                community_nodes
                    .iter()
                    .enumerate()
                    .map(|(community, nodes)| refine_fn(community, nodes, &mut buffers))
                    .collect()
            }
        }
        #[cfg(not(feature = "rayon"))]
        {
            let mut buffers = RefinementBuffers::new(n, num_layers);
            community_nodes
                .iter()
                .enumerate()
                .map(|(community, nodes)| refine_fn(community, nodes, &mut buffers))
                .collect()
        }
    };

    for moves in &results {
        for &(node, new_comm) in moves {
            refined.move_node(node, new_comm);
        }
    }

    refined.renumber();
    refined
}

/// Unified local moving for single-layer and multiplex Leiden.
///
/// Single-layer: `layers = &[data], layer_weights = &[1.0]`
/// Multi-layer: pass all layers and their weights.
///
/// Uses per-layer pre-computed neighbor weight buffers instead of re-scanning,
/// accumulating out-edge and in-edge weights separately for each layer in one pass.
///
/// `buffers` are reused across calls to avoid repeated allocations.
pub(crate) fn local_moving_generic(
    layers: &[GraphData],
    layer_weights: &[f64],
    partition: &mut Partition,
    quality: &(dyn QualityFunction + Sync),
    rng: &mut StdRng,
    max_comm_size: usize,
    epsilon: f64,
    buffers: &mut LocalMovingBuffers,
) -> bool {
    let n = layers[0].node_count();
    if n == 0 {
        return false;
    }

    let num_layers = layers.len();

    let total_weight: f64 = layers.iter().map(|l| l.total_weight()).sum();
    if total_weight <= 0.0 {
        return false;
    }

    buffers.resize_and_clear(n, num_layers);

    for (l, layer) in layers.iter().enumerate() {
        buffers.two_m_values[l] = 2.0 * layer.total_weight();
    }
    let total_node_weight: f64 = layers[0].total_node_weight();

    init_community_stats_into(
        layers,
        |node| partition.community_of(node),
        &mut buffers.comm_total_degree[..n],
        &mut buffers.comm_in_degree[..n],
        &mut buffers.comm_size[..n],
    );
    let comm_total_degree = &mut buffers.comm_total_degree;
    let comm_in_degree = &mut buffers.comm_in_degree;
    let comm_size = &mut buffers.comm_size;

    let mut order: Vec<usize> = (0..n)
        .filter(|&node| layers.iter().any(|l| l.degree_of(node) > 0.0))
        .collect();
    order.shuffle(rng);
    let mut queue: VecDeque<usize> = order.into_iter().collect();
    let in_queue = &mut buffers.in_queue;
    for &node in &queue {
        in_queue[node] = true;
    }

    let layer_out_weights = &mut buffers.layer_out_weights;
    let layer_in_weights = &mut buffers.layer_in_weights;
    let two_m_values = &buffers.two_m_values;

    let mut changed = false;
    let touched_list = &mut buffers.touched_list;
    let touched_mark = &mut buffers.touched_mark;

    while let Some(node) = queue.pop_front() {
        in_queue[node] = false;
        let current_community = partition.community_of(node);

        for l in 0..num_layers {
            layer_out_weights[l][current_community] = 0.0;
            layer_in_weights[l][current_community] = 0.0;
        }

        let mut current_touched = false;

        for (l, layer) in layers.iter().enumerate() {
            let (targets, weights) = layer.neighbor_slices(node);
            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 layer_out_weights[l][comm] == 0.0 && layer_in_weights[l][comm] == 0.0 {
                    if comm == current_community {
                        current_touched = true;
                    } else if !touched_mark[comm] {
                        touched_mark[comm] = true;
                        touched_list.push(comm);
                    }
                }
                layer_out_weights[l][comm] += weight;
            }
            let (in_targets, in_weights) = layer.in_neighbor_slices(node);
            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 layer_out_weights[l][comm] == 0.0 && layer_in_weights[l][comm] == 0.0 {
                    if comm == current_community {
                        current_touched = true;
                    } else if !touched_mark[comm] {
                        touched_mark[comm] = true;
                        touched_list.push(comm);
                    }
                }
                layer_in_weights[l][comm] += weight;
            }
        }

        let k_v_out: f64 = layers.iter().map(|l| l.out_degree_of(node)).sum();
        let k_v_in: f64 = layers.iter().map(|l| l.in_degree_of(node)).sum();
        let node_weight = layers[0].node_weight(node);

        let sigma_tot_current_out = comm_total_degree[current_community];
        let sigma_tot_current_in = comm_in_degree[current_community];

        let (best_community, _) = find_best_community(
            touched_list.iter().copied(),
            current_community,
            epsilon,
            max_comm_size,
            &comm_size[..n],
            node_weight,
            |target_comm| {
                let mut total_delta = 0.0f64;
                for (l, layer) in layers.iter().enumerate() {
                    let delta = quality.delta_move_from_components(&MoveComponents {
                        two_m: two_m_values[l],
                        node_weight,
                        total_node_weight,
                        k_v_out: layer.out_degree_of(node),
                        k_v_to_target_out: layer_out_weights[l][target_comm],
                        k_v_to_current_out: layer_out_weights[l][current_community],
                        sigma_tot_target_out: comm_total_degree[target_comm],
                        sigma_tot_current_out,
                        k_v_in: layer.in_degree_of(node),
                        k_v_to_target_in: layer_in_weights[l][target_comm],
                        k_v_to_current_in: layer_in_weights[l][current_community],
                        sigma_tot_target_in: comm_in_degree[target_comm],
                        sigma_tot_current_in,
                        n_target: comm_size[target_comm],
                        n_current: comm_size[current_community],
                        directed: layer.is_directed(),
                    });
                    total_delta += layer_weights[l] * delta;
                }
                total_delta
            },
        );

        for l in 0..num_layers {
            if current_touched {
                layer_out_weights[l][current_community] = 0.0;
                layer_in_weights[l][current_community] = 0.0;
            }
            for &comm in &*touched_list {
                layer_out_weights[l][comm] = 0.0;
                layer_in_weights[l][comm] = 0.0;
            }
        }
        for &idx in &*touched_list {
            touched_mark[idx] = false;
        }
        touched_list.clear();

        if best_community != current_community {
            apply_move(
                MoveTarget::Partition(&mut *partition),
                node,
                current_community,
                best_community,
                k_v_out,
                k_v_in,
                node_weight,
                &mut comm_total_degree[..n],
                &mut comm_in_degree[..n],
                &mut comm_size[..n],
            );
            changed = true;

            for layer in layers {
                let (targets, _) = layer.neighbor_slices(node);
                for &neighbor in targets {
                    if !in_queue[neighbor] {
                        queue.push_back(neighbor);
                        in_queue[neighbor] = true;
                    }
                }
                let (in_targets, _) = layer.in_neighbor_slices(node);
                for &neighbor in in_targets {
                    if !in_queue[neighbor] {
                        queue.push_back(neighbor);
                        in_queue[neighbor] = true;
                    }
                }
            }
        }
    }

    changed
}

/// Unified refinement for single-layer and multiplex Leiden.
///
/// Refines communities by splitting them based on quality improvement.
/// Only considers neighbors within the same coarse community.
/// Uses per-layer pre-computed neighbor weights for delta computation.
///
/// Single-layer: `layers = &[data], layer_weights = &[1.0]`
/// Multi-layer: pass all layers and their weights.
///
/// `buffers` are reused across calls to avoid repeated allocations.
pub(crate) fn refine_community_generic(
    layers: &[GraphData],
    layer_weights: &[f64],
    partition: &Partition,
    quality: &(dyn QualityFunction + Sync),
    community: usize,
    nodes: &[usize],
    epsilon: f64,
    buffers: &mut RefinementBuffers,
) -> Vec<(usize, usize)> {
    if nodes.len() <= 1 {
        return Vec::new();
    }

    let num_layers = layers.len();
    let total_node_weight: f64 = layers[0].total_node_weight();

    let max_node_id = nodes.iter().copied().max().unwrap_or(0);
    let mut refined_map: Vec<usize> = (0..=max_node_id).collect();

    buffers.resize_and_clear(max_node_id + 1, layers);

    // Split borrow: separate fields so the closure can read two_m_values
    // while other fields are accessed mutably through reborrow.
    let two_m_values = &buffers.two_m_values;
    let comm_total_degree = &mut buffers.comm_total_degree;
    let comm_in_degree = &mut buffers.comm_in_degree;
    let comm_size = &mut buffers.comm_size;
    let layer_out_weights = &mut buffers.layer_out_weights;
    let layer_in_weights = &mut buffers.layer_in_weights;
    let touched_list = &mut buffers.touched_list;
    let touched_mark = &mut buffers.touched_mark;

    for &node in nodes {
        comm_total_degree[node] +=
            layers.iter().map(|l| l.out_degree_of(node)).sum::<f64>();
        comm_in_degree[node] += layers.iter().map(|l| l.in_degree_of(node)).sum::<f64>();
        comm_size[node] += layers[0].node_weight(node);
    }

    for &node in nodes {
        let current_refined = refined_map[node];

        for l in 0..num_layers {
            layer_out_weights[l][current_refined] = 0.0;
            layer_in_weights[l][current_refined] = 0.0;
        }

        for (l, layer) in layers.iter().enumerate() {
            let (targets, weights) = layer.neighbor_slices(node);
            for i in 0..targets.len() {
                let neighbor = targets[i];
                let weight = weights[i];
                if partition.community_of(neighbor) != community {
                    continue;
                }
                if neighbor == node {
                    continue;
                }
                let rc = refined_map[neighbor];
                if layer_out_weights[l][rc] == 0.0
                    && layer_in_weights[l][rc] == 0.0
                    && rc != current_refined
                    && !touched_mark[rc]
                {
                    touched_mark[rc] = true;
                    touched_list.push(rc);
                }
                layer_out_weights[l][rc] += weight;
            }
            let (in_targets, in_weights) = layer.in_neighbor_slices(node);
            for i in 0..in_targets.len() {
                let neighbor = in_targets[i];
                let weight = in_weights[i];
                if partition.community_of(neighbor) != community {
                    continue;
                }
                if neighbor == node {
                    continue;
                }
                let rc = refined_map[neighbor];
                if layer_out_weights[l][rc] == 0.0
                    && layer_in_weights[l][rc] == 0.0
                    && rc != current_refined
                    && !touched_mark[rc]
                {
                    touched_mark[rc] = true;
                    touched_list.push(rc);
                }
                layer_in_weights[l][rc] += weight;
            }
        }

        let k_v_out: f64 = layers.iter().map(|l| l.out_degree_of(node)).sum();
        let k_v_in: f64 = layers.iter().map(|l| l.in_degree_of(node)).sum();
        let node_weight = layers[0].node_weight(node);
        let sigma_tot_current_out = comm_total_degree[current_refined];
        let sigma_tot_current_in = comm_in_degree[current_refined];

        let (best_refined, _) = find_best_community(
            touched_list.iter().copied(),
            current_refined,
            epsilon,
            0,
            &comm_size[..],
            node_weight,
            |target_comm| {
                let mut total_delta = 0.0f64;
                for (l, layer) in layers.iter().enumerate() {
                    let delta = quality.delta_move_from_components(&MoveComponents {
                        two_m: two_m_values[l],
                        node_weight,
                        total_node_weight,
                        k_v_out: layer.out_degree_of(node),
                        k_v_to_target_out: layer_out_weights[l][target_comm],
                        k_v_to_current_out: layer_out_weights[l][current_refined],
                        sigma_tot_target_out: comm_total_degree[target_comm],
                        sigma_tot_current_out,
                        k_v_in: layer.in_degree_of(node),
                        k_v_to_target_in: layer_in_weights[l][target_comm],
                        k_v_to_current_in: layer_in_weights[l][current_refined],
                        sigma_tot_target_in: comm_in_degree[target_comm],
                        sigma_tot_current_in,
                        n_target: comm_size[target_comm],
                        n_current: comm_size[current_refined],
                        directed: layer.is_directed(),
                    });
                    total_delta += layer_weights[l] * delta;
                }
                total_delta
            },
        );

        for l in 0..num_layers {
            for &rc in &*touched_list {
                layer_out_weights[l][rc] = 0.0;
                layer_in_weights[l][rc] = 0.0;
            }
            layer_out_weights[l][current_refined] = 0.0;
            layer_in_weights[l][current_refined] = 0.0;
        }
        for &idx in &*touched_list {
            touched_mark[idx] = false;
        }
        touched_list.clear();

        if best_refined != current_refined {
            apply_move(
                MoveTarget::RefinedMap(&mut refined_map),
                node,
                current_refined,
                best_refined,
                k_v_out,
                k_v_in,
                node_weight,
                &mut comm_total_degree[..],
                &mut comm_in_degree[..],
                &mut comm_size[..],
            );
        }
    }

    nodes
        .iter()
        .filter_map(|&node| {
            let rc = refined_map[node];
            if rc != node {
                Some((node, rc))
            } else {
                None
            }
        })
        .collect()
}