sdivi_detection/
partition.rs

1//! [`LeidenPartition`] — the output type of the Leiden community detection stage.
2
3use std::collections::BTreeMap;
4
5use serde::{Deserialize, Serialize};
6
7/// Quality function used during community detection.
8///
9/// # Examples
10///
11/// ```rust
12/// use sdivi_detection::partition::QualityFunction;
13///
14/// let q = QualityFunction::Modularity;
15/// assert!(matches!(q, QualityFunction::Modularity));
16/// ```
17#[derive(Debug, Clone, PartialEq, Serialize, Deserialize, Default)]
18pub enum QualityFunction {
19    /// Newman–Girvan modularity (default).
20    #[default]
21    Modularity,
22    /// Constant Potts Model with resolution parameter `gamma`.
23    Cpm {
24        /// Resolution parameter; higher values produce smaller communities.
25        gamma: f64,
26    },
27}
28
29/// Configuration for a Leiden run.
30///
31/// # Examples
32///
33/// ```rust
34/// use sdivi_detection::partition::LeidenConfig;
35///
36/// let cfg = LeidenConfig::default();
37/// assert_eq!(cfg.seed, 42);
38/// assert_eq!(cfg.max_iterations, 100);
39/// assert_eq!(cfg.min_compression_ratio, 0.1);
40/// assert_eq!(cfg.max_recursion_depth, 32);
41/// ```
42#[derive(Debug, Clone, Serialize, Deserialize)]
43pub struct LeidenConfig {
44    /// Random seed for deterministic partition results.
45    pub seed: u64,
46    /// Maximum iterations of the outer Leiden loop.
47    pub max_iterations: usize,
48    /// Quality function to optimise.
49    pub quality: QualityFunction,
50    /// Resolution parameter forwarded to CPM; ignored for Modularity.
51    pub gamma: f64,
52    /// Minimum graph compression ratio to continue Leiden recursion. Default `0.1`.
53    pub min_compression_ratio: f64,
54    /// Hard cap on Leiden recursion depth. Default `32`.
55    pub max_recursion_depth: u32,
56}
57
58impl Default for LeidenConfig {
59    fn default() -> Self {
60        LeidenConfig {
61            seed: 42,
62            max_iterations: 100,
63            quality: QualityFunction::Modularity,
64            gamma: 1.0,
65            min_compression_ratio: 0.1,
66            max_recursion_depth: 32,
67        }
68    }
69}
70
71impl LeidenConfig {
72    /// Creates a `LeidenConfig` from a [`sdivi_config::Config`].
73    pub fn from_sdivi_config(cfg: &sdivi_config::Config) -> Self {
74        LeidenConfig {
75            seed: cfg.core.random_seed,
76            max_iterations: 100,
77            quality: QualityFunction::Modularity,
78            gamma: cfg.boundaries.leiden_gamma,
79            min_compression_ratio: cfg.boundaries.leiden_min_compression_ratio,
80            max_recursion_depth: cfg.boundaries.leiden_max_recursion_depth,
81        }
82    }
83}
84
85/// The result of a Leiden community detection run.
86///
87/// Community IDs are stable integers starting at zero, assigned in ascending
88/// order of the lowest node index within each community.  This guarantees
89/// deterministic JSON output given the same input graph and seed.
90///
91/// # Examples
92///
93/// ```rust
94/// use sdivi_detection::partition::LeidenPartition;
95/// use std::collections::BTreeMap;
96///
97/// let p = LeidenPartition {
98///     assignments: BTreeMap::from([(0, 0), (1, 0), (2, 1)]),
99///     stability: BTreeMap::from([(0, 0.8), (1, 1.0)]),
100///     modularity: 0.42,
101///     seed: 42,
102/// };
103/// assert_eq!(p.assignments[&0], 0);
104/// assert_eq!(p.community_count(), 2);
105/// ```
106#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
107pub struct LeidenPartition {
108    /// Node index → community ID.
109    pub assignments: BTreeMap<usize, usize>,
110    /// Community ID → stability score (internal edge density, `[0, 1]`).
111    pub stability: BTreeMap<usize, f64>,
112    /// Overall modularity of the final partition.
113    pub modularity: f64,
114    /// Seed used to produce this partition.
115    pub seed: u64,
116}
117
118impl LeidenPartition {
119    /// Number of communities in the partition.
120    pub fn community_count(&self) -> usize {
121        self.stability.len()
122    }
123
124    /// Returns the community ID for node index `node`.
125    pub fn community_of(&self, node: usize) -> Option<usize> {
126        self.assignments.get(&node).copied()
127    }
128
129    /// Returns the file path associated with the largest community (most nodes).
130    pub fn largest_community_size(&self) -> usize {
131        let mut counts: BTreeMap<usize, usize> = BTreeMap::new();
132        for &comm in self.assignments.values() {
133            *counts.entry(comm).or_insert(0) += 1;
134        }
135        counts.values().copied().max().unwrap_or(0)
136    }
137
138    /// Groups node indices by community, sorted for determinism.
139    pub fn communities(&self) -> BTreeMap<usize, Vec<usize>> {
140        let mut map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
141        for (&node, &comm) in &self.assignments {
142            map.entry(comm).or_default().push(node);
143        }
144        map
145    }
146
147    /// Serialises the partition to compact JSON.
148    pub fn to_json(&self) -> serde_json::Result<String> {
149        serde_json::to_string(self)
150    }
151
152    /// Deserialises a partition from JSON.
153    pub fn from_json(json: &str) -> serde_json::Result<Self> {
154        serde_json::from_str(json)
155    }
156}
sdivi_detection/partition.rs

sdivi_detection/
partition.rs
