vrp_core/algorithms/clustering/
dbscan.rs

1//! This module contains an implementation of Density-Based Spatial Clustering of Applications with
2//! Noise (DBSCAN)
3
4#[cfg(test)]
5#[path = "../../../tests/unit/algorithms/clustering/dbscan_test.rs"]
6mod dbscan_test;
7
8use std::collections::{HashMap, HashSet};
9use std::hash::Hash;
10
11/// Represents a cluster of points.
12pub type Cluster<'a, T> = Vec<&'a T>;
13
14/// Creates clusters of points using DBSCAN (Density-Based Spatial Clustering of Applications with Noise).
15/// `points`: A list of points to cluster.
16/// `min_points`: The minimum number of points required to form a cluster.
17/// `neighborhood_fn`: A function which returns neighbors of given point. It should return point itself.
18pub fn create_clusters<'a, T, IS, FN, IR>(points: IS, min_points: usize, neighborhood_fn: FN) -> Vec<Cluster<'a, T>>
19where
20    T: Clone + Hash + Eq,
21    IS: IntoIterator<Item = &'a T>,
22    FN: Fn(&'a T) -> IR + 'a,
23    IR: Iterator<Item = &'a T> + 'a,
24{
25    let mut point_types = HashMap::<&T, PointType>::new();
26    let mut clusters = Vec::new();
27
28    for point in points {
29        if point_types.contains_key(point) {
30            continue;
31        }
32
33        let mut neighbors = neighborhood_fn(point).collect::<Vec<_>>();
34        let mut neighbors_index = neighbors.iter().cloned().collect::<HashSet<_>>();
35
36        if neighbors.len() < min_points {
37            point_types.insert(point, PointType::Noise);
38        } else {
39            let mut cluster = vec![point];
40            point_types.insert(point, PointType::Clustered);
41
42            let mut index = 0;
43            while index < neighbors.len() {
44                let point = neighbors[index];
45                let point_type = point_types.get(point).cloned();
46
47                if point_type.is_none() {
48                    let other_neighbours = neighborhood_fn(point).collect::<Vec<_>>();
49                    if other_neighbours.len() >= min_points {
50                        neighbors
51                            .extend(other_neighbours.iter().filter(|&point| !neighbors_index.contains(point)).cloned());
52                        neighbors_index.extend(other_neighbours.into_iter());
53                    }
54                }
55
56                match point_type {
57                    Some(PointType::Clustered) => {}
58                    _ => {
59                        point_types.insert(point, PointType::Clustered);
60                        cluster.push(point);
61                    }
62                }
63
64                index += 1;
65            }
66
67            clusters.push(cluster);
68        }
69    }
70
71    clusters
72}
73
74#[derive(Clone, Eq, PartialEq)]
75enum PointType {
76    Noise,
77    Clustered,
78}
vrp_core/algorithms/clustering/dbscan.rs

vrp_core/algorithms/clustering/
dbscan.rs
