facett_graphview/

community.rs

//! **Topological semantic zoom** — community detection → meta-nodes → fracture (#3).
//!
//! Zooming out of a large graph should *consolidate*, not shrink-to-illegible. We
//! detect the graph's **communities** (densely-connected clusters) with **Louvain**
//! modularity optimisation, then drive a zoom-aware collapse: at low zoom each
//! community becomes one consolidated **meta-node**; as the user zooms in past a
//! threshold the meta-node **fractures** open — its members ease out from the
//! meta-centroid to their real positions under an **injected-clock easing** curve
//! (the same dependency-injected easing seam `facett-helix` uses), so the structure
//! blooms apart instead of popping.
//!
//! # What lands here vs the roadmap
//! This is one solid level of Louvain (**local-moving** modularity ascent to a fixed
//! point) — deterministic (fixed node order, lowest-index tie-break), enough to
//! detect clear communities and drive the meta-node/fracture pipeline. The recursive
//! **multi-level aggregation** (Louvain proper) and the **Leiden** refinement
//! (guaranteed well-connected communities) are documented in
//! `.nornir/elite-graph-engine.md`; they slot in behind [`louvain`] without changing
//! the meta-graph / fracture API.

use std::collections::BTreeMap;

/// A detected partition: `of[i]` is node `i`'s community (compact `0..count`), with
/// the partition's **modularity** as the quality DATA.
#[derive(Clone, Debug, PartialEq)]
pub struct Communities {
    pub of: Vec<usize>,
    pub count: usize,
    pub modularity: f32,
}

/// **Louvain local-moving** community detection over an undirected, unweighted graph
/// of `n` nodes. Greedily moves each node to the neighbouring community with the best
/// modularity gain until a full pass makes no move. Deterministic in `(n, edges)`.
#[must_use]
pub fn louvain(n: usize, edges: &[(usize, usize)]) -> Communities {
    // ── build undirected adjacency + degrees (drop self-loops / out-of-range) ──
    let mut adj: Vec<BTreeMap<usize, f32>> = vec![BTreeMap::new(); n];
    let mut deg = vec![0.0f32; n];
    let mut m2 = 0.0f32; // 2·m (sum of degrees)
    for &(a, b) in edges {
        if a == b || a >= n || b >= n {
            continue;
        }
        *adj[a].entry(b).or_insert(0.0) += 1.0;
        *adj[b].entry(a).or_insert(0.0) += 1.0;
    }
    for i in 0..n {
        deg[i] = adj[i].values().sum();
        m2 += deg[i];
    }
    if m2 == 0.0 {
        // edgeless: every node is its own community.
        return Communities { of: (0..n).collect(), count: n, modularity: 0.0 };
    }

    let mut comm: Vec<usize> = (0..n).collect();
    let mut sigma_tot: Vec<f32> = deg.clone(); // total degree per community

    loop {
        let mut moved = false;
        for i in 0..n {
            let ci = comm[i];
            // remove i from its community.
            sigma_tot[ci] -= deg[i];
            // weight from i into each candidate community.
            let mut k_in: BTreeMap<usize, f32> = BTreeMap::new();
            for (&j, &w) in &adj[i] {
                if j != i {
                    *k_in.entry(comm[j]).or_insert(0.0) += w;
                }
            }
            // best gain: k_{i,in}(C) − Σ_tot(C)·k_i / (2m). Staying is the baseline.
            let mut best_c = ci;
            let mut best_gain = k_in.get(&ci).copied().unwrap_or(0.0) - sigma_tot[ci] * deg[i] / m2;
            for (&c, &kin) in &k_in {
                let gain = kin - sigma_tot[c] * deg[i] / m2;
                if gain > best_gain + 1e-9 {
                    best_gain = gain;
                    best_c = c;
                }
            }
            sigma_tot[best_c] += deg[i];
            if best_c != ci {
                comm[i] = best_c;
                moved = true;
            }
        }
        if !moved {
            break;
        }
    }

    // ── compact labels 0..count, then score modularity ──
    let mut remap: BTreeMap<usize, usize> = BTreeMap::new();
    let of: Vec<usize> = comm
        .iter()
        .map(|&c| {
            let next = remap.len();
            *remap.entry(c).or_insert(next)
        })
        .collect();
    let count = remap.len();
    let modularity = modularity(n, edges, &of);
    Communities { of, count, modularity }
}

/// Newman modularity `Q = (1/2m) Σ_ij [A_ij − k_i k_j/2m] δ(c_i,c_j)` of a partition.
#[must_use]
pub fn modularity(n: usize, edges: &[(usize, usize)], of: &[usize]) -> f32 {
    let mut deg = vec![0.0f32; n];
    let mut m2 = 0.0f32;
    let mut a_in: BTreeMap<(usize, usize), f32> = BTreeMap::new();
    for &(a, b) in edges {
        if a == b || a >= n || b >= n {
            continue;
        }
        deg[a] += 1.0;
        deg[b] += 1.0;
        m2 += 2.0;
        *a_in.entry((a.min(b), a.max(b))).or_insert(0.0) += 1.0;
    }
    if m2 == 0.0 {
        return 0.0;
    }
    let mut q = 0.0f32;
    // intra-community A_ij contributions (each undirected edge counted twice in the sum).
    for (&(a, b), &w) in &a_in {
        if of[a] == of[b] {
            q += 2.0 * w;
        }
    }
    // − Σ k_i k_j / 2m over same-community pairs.
    let mut by_comm: BTreeMap<usize, f32> = BTreeMap::new();
    for i in 0..n {
        *by_comm.entry(of[i]).or_insert(0.0) += deg[i];
    }
    let mut expected = 0.0f32;
    for &s in by_comm.values() {
        expected += s * s / m2;
    }
    (q - expected) / m2
}

/// One **meta-node**: a collapsed community — its members, centroid position, and a
/// weight (member count) a renderer can size by.
#[derive(Clone, Debug, PartialEq)]
pub struct MetaNode {
    pub community: usize,
    pub members: Vec<usize>,
    pub pos: [f32; 2],
    pub weight: f32,
}

/// The collapsed graph: one [`MetaNode`] per community + aggregated inter-community
/// edges (`from_comm`, `to_comm`, `weight = crossing-edge count`).
#[derive(Clone, Debug, PartialEq)]
pub struct MetaGraph {
    pub metas: Vec<MetaNode>,
    pub edges: Vec<(usize, usize, f32)>,
}

/// Collapse `positions` + `edges` under `comms` into the meta-graph: meta-node
/// centroids + aggregated crossing edges (intra-community edges vanish into the node).
#[must_use]
pub fn meta_graph(positions: &[[f32; 2]], edges: &[(usize, usize)], comms: &Communities) -> MetaGraph {
    let mut members: Vec<Vec<usize>> = vec![Vec::new(); comms.count];
    for (i, &c) in comms.of.iter().enumerate() {
        members[c].push(i);
    }
    let metas = members
        .into_iter()
        .enumerate()
        .map(|(c, mem)| {
            let (mut sx, mut sy) = (0.0f32, 0.0f32);
            for &i in &mem {
                sx += positions[i][0];
                sy += positions[i][1];
            }
            let k = mem.len().max(1) as f32;
            MetaNode { community: c, members: mem.clone(), pos: [sx / k, sy / k], weight: mem.len() as f32 }
        })
        .collect();
    let mut agg: BTreeMap<(usize, usize), f32> = BTreeMap::new();
    for &(a, b) in edges {
        if a >= comms.of.len() || b >= comms.of.len() {
            continue;
        }
        let (ca, cb) = (comms.of[a], comms.of[b]);
        if ca != cb {
            *agg.entry((ca.min(cb), ca.max(cb))).or_insert(0.0) += 1.0;
        }
    }
    let edges = agg.into_iter().map(|((a, b), w)| (a, b, w)).collect();
    MetaGraph { metas, edges }
}

/// The **fracture parameter** `t ∈ [0,1]` for the current `zoom`: `0` = fully
/// collapsed (show meta-nodes), `1` = fully fractured (show members at their real
/// positions). Below `collapse_below` it's collapsed; above `collapse_below +
/// span` it's open; between, the **injected** `ease` drives the bloom (pass
/// `facett_core::effects::easing::ease_in_out_cubic` / `elastic`). Deterministic.
#[must_use]
pub fn fracture_t(zoom: f32, collapse_below: f32, span: f32, ease: impl Fn(f32) -> f32) -> f32 {
    let span = span.max(1e-4);
    let raw = ((zoom - collapse_below) / span).clamp(0.0, 1.0);
    ease(raw).clamp(0.0, 1.0)
}

/// Per-node **rendered** positions at fracture `t`: each node lerps from its meta-node
/// centroid (`t=0`, collapsed) to its real position (`t=1`, fractured). The host paints
/// nodes with opacity ∝ `t` (and meta-nodes ∝ `1−t`) for the bloom-open.
#[must_use]
pub fn fractured_positions(positions: &[[f32; 2]], comms: &Communities, meta: &MetaGraph, t: f32) -> Vec<[f32; 2]> {
    let t = t.clamp(0.0, 1.0);
    positions
        .iter()
        .enumerate()
        .map(|(i, p)| {
            let c = comms.of[i];
            let m = meta.metas[c].pos;
            [m[0] + (p[0] - m[0]) * t, m[1] + (p[1] - m[1]) * t]
        })
        .collect()
}

/// How many nodes are *visible* at fracture `t`: the collapsed meta-node count when
/// `t == 0`, the full node count when fully fractured — the semantic-zoom LOD DATA.
#[must_use]
pub fn visible_count(comms: &Communities, t: f32) -> usize {
    if t <= 0.0 { comms.count } else { comms.of.len() }
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Two triangles (0-1-2, 3-4-5) joined by a single bridge edge 2-3 — two obvious
    /// communities.
    fn two_triangles() -> (usize, Vec<(usize, usize)>) {
        (6, vec![(0, 1), (1, 2), (2, 0), (3, 4), (4, 5), (5, 3), (2, 3)])
    }

    #[test]
    fn louvain_finds_the_two_clusters() {
        let (n, edges) = two_triangles();
        let c = louvain(n, &edges);
        assert_eq!(c.count, 2, "two communities detected (modularity {})", c.modularity);
        // 0,1,2 share a community; 3,4,5 share the other; the two differ.
        assert_eq!(c.of[0], c.of[1]);
        assert_eq!(c.of[1], c.of[2]);
        assert_eq!(c.of[3], c.of[4]);
        assert_eq!(c.of[4], c.of[5]);
        assert_ne!(c.of[0], c.of[3], "the bridge didn't merge the clusters");
        assert!(c.modularity > 0.3, "a real community structure (Q={})", c.modularity);
    }

    #[test]
    fn louvain_is_deterministic() {
        let (n, edges) = two_triangles();
        assert_eq!(louvain(n, &edges), louvain(n, &edges));
    }

    #[test]
    fn edgeless_graph_is_all_singletons() {
        let c = louvain(4, &[]);
        assert_eq!(c.count, 4);
        assert_eq!(c.modularity, 0.0);
    }

    #[test]
    fn meta_graph_collapses_and_aggregates_the_bridge() {
        let (n, edges) = two_triangles();
        let c = louvain(n, &edges);
        // positions: left triangle near (0,*), right near (10,*).
        let positions = vec![[0.0, 0.0], [0.5, 1.0], [1.0, 0.0], [10.0, 0.0], [10.5, 1.0], [11.0, 0.0]];
        let mg = meta_graph(&positions, &edges, &c);
        assert_eq!(mg.metas.len(), 2, "one meta-node per community");
        // meta-node count strictly fewer than the 6 real nodes (the zoom-out win).
        assert!(mg.metas.len() < n, "consolidation: {} meta-nodes < {n} nodes", mg.metas.len());
        // only the single bridge edge survives as an inter-community meta-edge.
        assert_eq!(mg.edges.len(), 1);
        assert_eq!(mg.edges[0].2, 1.0, "one crossing edge aggregated");
        // centroids land in their cluster's region.
        let left = &mg.metas[c.of[0]];
        assert!(left.pos[0] < 5.0 && (left.weight - 3.0).abs() < 1e-6, "3-member left cluster centroid");
    }

    #[test]
    fn fracture_eases_from_collapsed_to_open_with_injected_clock() {
        use std::f32::consts::PI;
        // An injected ease (smoothstep-ish) — same dependency-injection seam helix uses.
        let ease = |t: f32| 0.5 - 0.5 * (t * PI).cos();
        // Far out → collapsed.
        assert_eq!(fracture_t(0.2, 0.5, 1.0, ease), 0.0, "below threshold: fully collapsed");
        // Far in → fully open.
        assert!((fracture_t(2.0, 0.5, 1.0, ease) - 1.0).abs() < 1e-5, "well past: fully fractured");
        // Mid-zoom: strictly between (the bloom is mid-animation) and monotone.
        let mid = fracture_t(1.0, 0.5, 1.0, ease);
        assert!(mid > 0.0 && mid < 1.0, "mid-zoom is mid-fracture ({mid})");
        let a = fracture_t(0.7, 0.5, 1.0, ease);
        let b = fracture_t(1.2, 0.5, 1.0, ease);
        assert!(b > a, "zooming in advances the fracture ({a} → {b})");
    }

    #[test]
    fn fractured_positions_and_visible_count_track_t() {
        let (n, edges) = two_triangles();
        let c = louvain(n, &edges);
        let positions = vec![[0.0, 0.0], [0.5, 1.0], [1.0, 0.0], [10.0, 0.0], [10.5, 1.0], [11.0, 0.0]];
        let mg = meta_graph(&positions, &edges, &c);

        // Collapsed: every member sits on its meta-centroid; visible == meta count.
        let collapsed = fractured_positions(&positions, &c, &mg, 0.0);
        for i in 0..n {
            assert_eq!(collapsed[i], mg.metas[c.of[i]].pos, "node {i} collapsed onto its meta-node");
        }
        assert_eq!(visible_count(&c, 0.0), 2, "low zoom shows 2 meta-nodes, not 6 nodes");

        // Fully fractured: members back at their real positions; visible == node count.
        let open = fractured_positions(&positions, &c, &mg, 1.0);
        for i in 0..n {
            assert!((open[i][0] - positions[i][0]).abs() < 1e-5 && (open[i][1] - positions[i][1]).abs() < 1e-5);
        }
        assert_eq!(visible_count(&c, 1.0), 6);

        // Half-fractured: a member is strictly between centroid and real position (DATA).
        let half = fractured_positions(&positions, &c, &mg, 0.5);
        let i = 3usize;
        let m = mg.metas[c.of[i]].pos;
        assert!((half[i][0] - (m[0] + (positions[i][0] - m[0]) * 0.5)).abs() < 1e-5, "lerps halfway open");
    }
}