Rough dbscans implementation with dataset3ID.csv as the data

dataset3ID.csv

dbscan.nim

import parsecsv
from os import fileExists
from math import pow, sqrt
from strutils import parseInt, parseFloat, strip
#from algorithm import sort
from sequtils import filter, deduplicate, apply

type
  Coord = object
    #id, cluster: int
    id: int
    x, y: float

  DistanceTest[V] = proc(a: V, b: V): bool

const
  epsilon = 1.0
  minpt = 37

proc getCoords(filename: string): seq[Coord] =
  result = newSeq[Coord]()
  var csv: CsvParser
  csv.open filename
  csv.readHeaderRow
  defer: csv.close()
  var
    x, y: float
    id: int
  while csv.readRow:
    for entry in csv.headers.items:
      let rowval = csv.rowEntry(entry).strip

      case entry
      of "ID": id = try: rowval.parseInt except: -1
      of "X1": x = try: rowval.parseFloat except: 100.0
      of "X2": y = try: rowval.parseFloat except: 100.0
    result.add Coord(id: id, x: x, y: y)

proc `==`(a, b: Coord): bool = a.id == b.id and a.x == b.x and a.y == b.y

#[
proc cmp(a, b: Coord): int =
  if a.id == b.id: 0
  elif a.id < b.id: -1
  elif a.id > b.id: 1
  elif a.x > b.x: 1
  elif a.x == b.x:
    if a.y > b.y: 1
    else: -1
  else: -1
]#

proc euclideanDist(p1, p2: Coord): float =
  sqrt((p1.x - p2.x).pow(2) + (p1.y - p2.y).pow(2))

proc neighbourTest(post, node: Coord): bool =
  post.euclideanDist(node) < epsilon

# Define implementation of how to verify the cluster
# In this case, cluster is deemed okay when it's member more than `minpt`
proc consideredOkay[V](cluster: seq[V]): bool = cluster.len > minpt

proc union[T](a: var seq[T], b: seq[T]) =
  for belm in b:
    if belm notin a:
      a.add belm

proc `+=`[T](a: var seq[T], b: seq[T]) =
  a.union b

proc clustering[V](input: seq[V], test: DistanceTest[V]): seq[seq[V]] =
  result = newSeq[seq[V]]()
  var visited = newSeq[V]()
  proc getNeighbours(node: V): seq[V] = input.filter(proc(a: V): bool =
    a notin visited and a.test(node))

  for node in input:
    if node notin visited:
      visited.add node
      var cluster = newSeq[V]()
      for neighbour in node.getNeighbours:
        if neighbour notin visited:
          visited.add neighbour
          cluster += neighbour.getNeighbours.deduplicate
      if cluster.consideredOkay:
        result.add cluster
  echo "visited length: ", visited.len
  result = result.deduplicate

proc main =
  let
    fname = "dataset3ID.csv"
    coords = if fileExists(fname):
               getCoords fname
              else:
               @[]
  if coords.len == 0:
    quit "No " & fname & " available"
  echo "coords data ", coords.len
  let clusters = coords.clustering neighbourTest
  echo "clusters are ", clusters.len
  var sumelm = 0
  for index, cluster in clusters.pairs:
    echo "cluster ", index, " has element ", cluster.len
    sumelm += cluster.len
  echo "total elements ", sumelm
  for index, cluster in clusters.pairs:
    echo "elm ", index, " with length ", cluster.len
    echo cluster

when isMainModule:
  main()