A very simple and unoptimized DBSCAN implementation written in Swift

myDBSCANImplem.swift

// myDbscanImplem - v1.0
// Constantin Clerc

// this is a random dbscan implem i fugured out why not to do on a random sunday evening
// to do so, we need a collection of points. because I have no idea how to do it for now, it'll be 2d but this can be changed in the future
// this code was done ONLY thanks to the really good explaination available at https://youtu.be/RDZUdRSDOok

struct Point: Equatable {
    var x: Double
    var y: Double

    init(_ x: Double, _ y: Double) { // this allows me to win time typing this in
        self.x = x
        self.y = y
    }
}

// say we need a sample array of points, representing the points on our graph

let points: [Point] = [
    // thanks chatgpt for generating me this sample im lazy
    // cluster 1 (around (1, 1))
    Point(1, 1),
    Point(2, 1),
    Point(1, 2),
    Point(2, 2),
    Point(1, 3),
    Point(3, 2),

    // cluster 2 (around (8, 8))
    Point(8, 8),
    Point(9, 8),
    Point(8, 9),
    Point(9, 9),
    Point(10, 8),
    Point(8, 10),

    // noise / outliers
    Point(0, 10),
    Point(10, 0),
    Point(5, 5)
]


// so to sum it up : the way this works is for each point it sees how much points are in the radius
// this implem wont be ideal, but first let's set a radius, say 2 seems reasonable
let radius: Int = 2

// dbscan also relies on the fact that we have core points. those core points are said to have an x numbers of close neigbours in the radius

let coreThreesold: Int = 4

// for now uhm let's clearly say that this will only work on Integers, i dont wanna work with doubles but hey this shouldnt be hard

// this is very pythonesque welp
// and so not optimiseddddd, prob better way to do it through native swift but hey idc
func getPointRelatives(point: Point, points: [Point], radius: Int) -> [Point] {
    var relatives: [Point] = []
    let r = Double(radius)
    for p in points {
        if p != point {
            if abs(p.x - point.x) <= r && abs(p.y - point.y) <= r { // note : this should work well but euclidyan distance is a better alternative cuz it's a circle ; idk how to do it so let's just stick with that
                relatives.append(p)
            }
        }
    }
    return relatives
}


var pointsCloseness: [(Point, [Point])] = []
for point in points {
    pointsCloseness.append((point, getPointRelatives(point: point, points: points, radius: radius)))
}

var corePoints: [Point] = []
for point in pointsCloseness {
    if point.1.count >= coreThreesold {
        corePoints.append(point.0)
    }
}

// suppose we have x clusters
// let's randomly pick a core point and assign it to cluster 1

func addPointToCluster(corePoint: Point, pointsCloseness: [(Point, [Point])], clusters: inout [[Point]]) {
    for cluster in clusters {
        if cluster.contains(corePoint) { return }
    }

    // we add the first randomCorePoint to the st cluster
    clusters.append([corePoint])
    
    // then we add the close points of this closePoint to the cluster too !
    var queue: [Point] = [corePoint]
    
    while !queue.isEmpty {
        let point = queue.removeFirst()
        
        // it's very ugly buttt we refind the point in the pointsCloseness and its relatives
        if let (_, relatives) = pointsCloseness.first(where: { $0.0 == point }) {
            for relative in relatives {
                // case for corePoints: here we add close points to the cluster
                if corePoints.contains(relative) && !clusters.last!.contains(relative) {
                    clusters[clusters.count - 1].append(relative)
                    queue.append(relative)
                }
                // case for not corePoints : their relatives shouldnt be added to the cluster as they cant extend it further
                else if !clusters.last!.contains(relative) { // yikes force unwrap
                    clusters[clusters.count - 1].append(relative)
                }
            }
        }
    }
}

var clusters: [[Point]] = []
var unclusteredCorePoints = corePoints

while !unclusteredCorePoints.isEmpty {
    if let randomCorePoint = unclusteredCorePoints.randomElement() {
        addPointToCluster(corePoint: randomCorePoint, pointsCloseness: pointsCloseness, clusters: &clusters)
        
        // then we remove every corePoints that were added to our new cluster 
        let lastClusterPoints = clusters.last ?? []
        unclusteredCorePoints.removeAll(where: { lastClusterPoints.contains($0) })
    }
}

// yayyy we got our clusters
for (i, cluster) in clusters.enumerated() {
    print("Cluster \(i + 1) : \(cluster)")
}

// let's look at what is noise by just removing what's not in clusters
let noisePoints = points.filter { !clusters.flatMap({ $0 }).contains($0) }
print("Noise points : \(noisePoints)")