hdbscan 0.12.0

HDBSCAN clustering in pure Rust. A huge improvement on DBSCAN, capable of identifying clusters of varying densities.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

pub(crate) struct UnionFind {
    parent: Vec<usize>,
    next_label: usize,
    size: Vec<usize>,
}

impl UnionFind {
    pub(crate) fn new(n_samples: usize) -> Self {
        let length = 2 * n_samples - 1;
        let parent = vec![length; length];
        let next_label = n_samples;
        let size = (0..length)
            .map(|n| if n < n_samples { 1 } else { 0 })
            .collect();

        UnionFind {
            parent,
            next_label,
            size,
        }
    }

    pub(crate) fn union(&mut self, m: usize, n: usize) {
        self.parent[m] = self.next_label;
        self.parent[n] = self.next_label;
        self.size[self.next_label] = self.size[m] + self.size[n];
        self.next_label += 1;
    }

    pub(crate) fn find(&mut self, mut n: usize) -> usize {
        let mut p = n;
        while self.parent[n] != self.parent.len() {
            n = self.parent[n];
        }
        while self.parent[p] != n {
            p = self.wrap_parent_index_if_necessary(p);
            p = self.parent[p];
            p = self.wrap_parent_index_if_necessary(p);
            self.parent[p] = n;
        }
        n
    }

    pub(crate) fn size_of(&self, n: usize) -> usize {
        self.size[n]
    }

    fn wrap_parent_index_if_necessary(&self, idx: usize) -> usize {
        if idx == self.parent.len() {
            self.parent.len() - 1
        } else {
            idx
        }
    }
}