leiden_rs/
lib.rs

1//! # leiden-rs
2//!
3//! A Rust implementation of the [Leiden algorithm](https://doi.org/10.1038/s41598-019-41695-z)
4//! for community detection in graphs, with optional adapters for [gryf](https://github.com/pnevyk/gryf) and [petgraph](https://github.com/petgraph/petgraph).
5//!
6//! The Leiden algorithm guarantees well-connected communities through three phases:
7//! local moving, refinement, and aggregation. It supports four quality functions:
8//! **Modularity**, **CPM**, **RBConfiguration**, and **RBER**.
9//!
10//! # Quick Start
11//!
12//! ```
13//! use leiden_rs::{GraphDataBuilder, Leiden, LeidenConfig};
14//!
15//! let mut b = GraphDataBuilder::new(3);
16//! b.add_edge(0, 1, 1.0).unwrap();
17//! b.add_edge(1, 2, 1.0).unwrap();
18//! let graph = b.build().unwrap();
19//!
20//! let leiden = Leiden::new(LeidenConfig::default());
21//! let result = leiden.run(&graph).expect("leiden failed");
22//! println!("Found {} communities (quality: {:.4})", result.partition.num_communities(), result.quality);
23//! ```
24//!
25//! # Quality Functions
26//!
27//! - **Modularity**: `Q = Σ_c [e_c/m - γ*(Σ_c/(2m))²]` — the classic Newman-Girvan modularity
28//! - **CPM**: `H = Σ_c [e_c - γ * n_c*(n_c-1)/2]` — avoids resolution limit, tunable via γ
29//! - **RBConfiguration**: `Q = Σ_c [e_c - γ * K_c²/(4m)]` — Reichardt-Bornholdt with configuration null model
30//! - **RBER**: `Q = Σ_c [e_c - γ * p * n_c*(n_c-1)/2]` — Reichardt-Bornholdt with Erdős-Rényi null model
31
32#![warn(missing_docs)]
33#![deny(unsafe_code)]
34
35mod algorithm;
36pub mod generators;
37pub mod convert;
38pub mod error;
39pub mod fluid_communities;
40pub mod graph;
41pub mod hierarchy;
42pub mod infomap;
43pub mod label_propagation;
44pub mod leiden;
45pub mod lfr;
46pub mod metrics;
47pub mod multiplex;
48pub mod output;
49#[cfg(feature = "rayon")]
50mod parallel;
51pub mod partition;
52pub mod quality;
53pub mod resolution;
54pub mod util;
55
56#[cfg(feature = "wasm")]
57pub mod wasm;
58
59pub use error::{LeidenError, Result as LeidenResult};
60pub use graph::{GraphData, GraphDataBuilder, MoveComponents};
61pub use hierarchy::{HierarchicalOutput, HierarchyLevel};
62pub use fluid_communities::{FluidCommunities, FluidCommunitiesConfig, FluidCommunitiesOutput};
63pub use infomap::{
64    calc_codelength, compute_flow, compute_node_flows, DeltaFlow, FlowData, Infomap,
65    InfomapConfig, InfomapOutput, MapEquation, ModuleFlowData, plogp,
66};
67pub use leiden::{Leiden, LeidenConfig, LeidenConfigBuilder, LeidenOutput, QualityType};
68pub use generators::{
69    generate_ba_graph, generate_er_graph, generate_er_graph_exact, generate_planted_partition,
70    generate_sbm, generate_sbm_symmetric,
71};
72pub use label_propagation::{LabelPropagation, LabelPropagationConfig, LabelPropagationOutput};
73pub use lfr::{generate_lfr_graph, LfrConfig, LfrGraph};
74pub use metrics::{
75    ami, ari, completeness, conductance, coverage, fmi, homogeneity, internal_density, nmi,
76    performance, purity, try_ami, try_ari, try_completeness, try_fmi, try_homogeneity, try_nmi,
77    try_purity, try_vi, try_v_measure, v_measure, vi,
78};
79pub use multiplex::{run_multiplex, MultiplexConfig, MultiplexOutput};
80pub use output::{CommunityDetectionOutput, ToJson};
81pub use partition::Partition;
82pub use quality::{Modularity, QualityFunction, RBConfiguration, CPM, RBER};
83pub use resolution::{resolution_profile, resolution_scan, ResolutionEntry};
84pub use util::{load_edgelist, modularity as compute_modularity};
85
86#[cfg(feature = "gryf")]
87pub use convert::gryf::from_gryf;
88#[cfg(feature = "gryf")]
89pub use convert::gryf::from_gryf_directed;
90
91#[cfg(feature = "petgraph")]
92pub use convert::petgraph::from_petgraph;
93
94#[cfg(test)]
95mod tests {
96    /// Verify that `#[must_use]` attributes are present on all
97    /// public constructors and pure functions in non-test code.
98    fn collect_rs_files(dir: &std::path::Path) -> Vec<std::path::PathBuf> {
99        let mut files = Vec::new();
100        if let Ok(entries) = std::fs::read_dir(dir) {
101            for entry in entries.flatten() {
102                let path = entry.path();
103                if path.is_dir() {
104                    files.extend(collect_rs_files(&path));
105                } else if path.extension().and_then(|e| e.to_str()) == Some("rs") {
106                    files.push(path);
107                }
108            }
109        }
110        files
111    }
112
113    #[test]
114    fn must_use_attributes_present() {
115        let src = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("src");
116        let mut count = 0usize;
117
118        for path in collect_rs_files(&src) {
119            let content = std::fs::read_to_string(&path).unwrap();
120            let mut in_test_block = false;
121
122            for line in content.lines() {
123                let t = line.trim();
124                if t == "#[cfg(test)]" || t.starts_with("mod tests") {
125                    in_test_block = true;
126                } else if (t.starts_with("pub mod ") || t.starts_with("mod "))
127                    && !t.contains("tests")
128                {
129                    in_test_block = false;
130                }
131                if t.starts_with("#[must_use") && !in_test_block {
132                    count += 1;
133                }
134            }
135        }
136
137        assert!(
138            count >= 53,
139            "expected at least 53 #[must_use] attributes in non-test code, found {count}"
140        );
141    }
142}
leiden_rs/lib.rs

leiden_rs/
lib.rs
