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/// ```
40#[derive(Debug, Clone, Serialize, Deserialize)]
41pub struct LeidenConfig {
42    /// Random seed for deterministic partition results.
43    pub seed: u64,
44    /// Maximum iterations of the outer Leiden loop.
45    pub max_iterations: usize,
46    /// Quality function to optimise.
47    pub quality: QualityFunction,
48    /// Resolution parameter forwarded to CPM; ignored for Modularity.
49    pub gamma: f64,
50}
51
52impl Default for LeidenConfig {
53    fn default() -> Self {
54        LeidenConfig {
55            seed: 42,
56            max_iterations: 100,
57            quality: QualityFunction::Modularity,
58            gamma: 1.0,
59        }
60    }
61}
62
63impl LeidenConfig {
64    /// Creates a `LeidenConfig` from a [`sdivi_config::Config`].
65    pub fn from_sdivi_config(cfg: &sdivi_config::Config) -> Self {
66        LeidenConfig {
67            seed: cfg.core.random_seed,
68            max_iterations: 100,
69            quality: QualityFunction::Modularity,
70            gamma: cfg.boundaries.leiden_gamma,
71        }
72    }
73}
74
75/// The result of a Leiden community detection run.
76///
77/// Community IDs are stable integers starting at zero, assigned in ascending
78/// order of the lowest node index within each community.  This guarantees
79/// deterministic JSON output given the same input graph and seed.
80///
81/// # Examples
82///
83/// ```rust
84/// use sdivi_detection::partition::LeidenPartition;
85/// use std::collections::BTreeMap;
86///
87/// let p = LeidenPartition {
88///     assignments: BTreeMap::from([(0, 0), (1, 0), (2, 1)]),
89///     stability: BTreeMap::from([(0, 0.8), (1, 1.0)]),
90///     modularity: 0.42,
91///     seed: 42,
92/// };
93/// assert_eq!(p.assignments[&0], 0);
94/// assert_eq!(p.community_count(), 2);
95/// ```
96#[derive(Debug, Clone, Serialize, Deserialize, PartialEq)]
97pub struct LeidenPartition {
98    /// Node index → community ID.
99    pub assignments: BTreeMap<usize, usize>,
100    /// Community ID → stability score (internal edge density, `[0, 1]`).
101    pub stability: BTreeMap<usize, f64>,
102    /// Overall modularity of the final partition.
103    pub modularity: f64,
104    /// Seed used to produce this partition.
105    pub seed: u64,
106}
107
108impl LeidenPartition {
109    /// Number of communities in the partition.
110    pub fn community_count(&self) -> usize {
111        self.stability.len()
112    }
113
114    /// Returns the community ID for node index `node`.
115    pub fn community_of(&self, node: usize) -> Option<usize> {
116        self.assignments.get(&node).copied()
117    }
118
119    /// Returns the file path associated with the largest community (most nodes).
120    pub fn largest_community_size(&self) -> usize {
121        let mut counts: BTreeMap<usize, usize> = BTreeMap::new();
122        for &comm in self.assignments.values() {
123            *counts.entry(comm).or_insert(0) += 1;
124        }
125        counts.values().copied().max().unwrap_or(0)
126    }
127
128    /// Groups node indices by community, sorted for determinism.
129    pub fn communities(&self) -> BTreeMap<usize, Vec<usize>> {
130        let mut map: BTreeMap<usize, Vec<usize>> = BTreeMap::new();
131        for (&node, &comm) in &self.assignments {
132            map.entry(comm).or_default().push(node);
133        }
134        map
135    }
136
137    /// Serialises the partition to compact JSON.
138    pub fn to_json(&self) -> serde_json::Result<String> {
139        serde_json::to_string(self)
140    }
141
142    /// Deserialises a partition from JSON.
143    pub fn from_json(json: &str) -> serde_json::Result<Self> {
144        serde_json::from_str(json)
145    }
146}
sdivi_detection/partition.rs

sdivi_detection/
partition.rs
