sdivi_detection/
warm_start.rs

1//! Warm-start support for the Leiden algorithm.
2//!
3//! The partition cache allows consecutive snapshot runs to start from the
4//! previous community assignments rather than all-singletons, improving
5//! stability across incremental changes.  FS I/O (load / save) lives in
6//! `sdivi-pipeline::cache`; this module contains only the pure mapping logic.
7
8use std::collections::BTreeMap;
9
10use crate::partition::LeidenPartition;
11
12/// Default cache path relative to the `.sdivi` directory.
13///
14/// The FS operations using this constant live in `sdivi-pipeline::cache`.
15pub const CACHE_FILENAME: &str = "cache/partition.json";
16
17/// Converts a cached partition into an initial assignment vector.
18///
19/// `node_count` is the number of nodes in the current graph.
20/// Nodes not present in `cached` fall back to singleton assignments
21/// (`assignment[i] = i`).
22///
23/// Community IDs from the cache are remapped so they stay in `[0, node_count)`.
24///
25/// # Examples
26///
27/// ```rust
28/// use std::collections::BTreeMap;
29/// use sdivi_detection::partition::LeidenPartition;
30/// use sdivi_detection::warm_start::initial_assignment_from_cache;
31///
32/// let cached = LeidenPartition {
33///     assignments: BTreeMap::from([(0, 0), (1, 0)]),
34///     stability: BTreeMap::from([(0, 0.9)]),
35///     modularity: 0.5,
36///     seed: 42,
37/// };
38/// let init = initial_assignment_from_cache(Some(&cached), 3);
39/// assert_eq!(init[0], init[1]); // same community
40/// assert_ne!(init[0], init[2]); // node 2 falls back to singleton
41/// ```
42pub fn initial_assignment_from_cache(
43    cached: Option<&LeidenPartition>,
44    node_count: usize,
45) -> Vec<usize> {
46    let mut assignment: Vec<usize> = (0..node_count).collect();
47
48    let cached = match cached {
49        Some(c) => c,
50        None => return assignment,
51    };
52
53    let mut community_remap: BTreeMap<usize, usize> = BTreeMap::new();
54    let mut next_comm = 0usize;
55
56    for (&node, &comm) in &cached.assignments {
57        if node >= node_count {
58            continue;
59        }
60        let remapped = *community_remap.entry(comm).or_insert_with(|| {
61            let c = next_comm;
62            next_comm += 1;
63            c
64        });
65        assignment[node] = remapped;
66    }
67
68    let mut used: std::collections::BTreeSet<usize> = community_remap.values().copied().collect();
69    let mut counter = 0usize;
70
71    for (i, slot) in assignment.iter_mut().enumerate().take(node_count) {
72        if !cached.assignments.contains_key(&i) {
73            while used.contains(&counter) {
74                counter += 1;
75            }
76            *slot = counter;
77            used.insert(counter);
78            counter += 1;
79        }
80    }
81
82    assignment
83}
sdivi_detection/warm_start.rs

sdivi_detection/
warm_start.rs
