41 lines
1.3 KiB
Cython
41 lines
1.3 KiB
Cython
|
# Fast inner loop for DBSCAN.
|
||
|
|
# Author: Lars Buitinck
|
||
|
|
# License: 3-clause BSD
|
||
|
|
|
||
|
|
from libcpp.vector cimport vector
|
||
|
|
|
||
|
|
from ..utils._typedefs cimport uint8_t, intp_t
|
||
|
|
|
||
|
|
|
||
|
|
def dbscan_inner(const uint8_t[::1] is_core,
|
||
|
|
object[:] neighborhoods,
|
||
|
|
intp_t[::1] labels):
|
||
|
|
cdef intp_t i, label_num = 0, v
|
||
|
|
cdef intp_t[:] neighb
|
||
|
|
cdef vector[intp_t] stack
|
||
|
|
|
||
|
|
for i in range(labels.shape[0]):
|
||
|
|
if labels[i] != -1 or not is_core[i]:
|
||
|
|
continue
|
||
|
|
|
||
|
|
# Depth-first search starting from i, ending at the non-core points.
|
||
|
|
# This is very similar to the classic algorithm for computing connected
|
||
|
|
# components, the difference being that we label non-core points as
|
||
|
|
# part of a cluster (component), but don't expand their neighborhoods.
|
||
|
|
while True:
|
||
|
|
if labels[i] == -1:
|
||
|
|
labels[i] = label_num
|
||
|
|
if is_core[i]:
|
||
|
|
neighb = neighborhoods[i]
|
||
|
|
for i in range(neighb.shape[0]):
|
||
|
|
v = neighb[i]
|
||
|
|
if labels[v] == -1:
|
||
|
|
stack.push_back(v)
|
||
|
|
|
||
|
|
if stack.size() == 0:
|
||
|
|
break
|
||
|
|
i = stack.back()
|
||
|
|
stack.pop_back()
|
||
|
|
|
||
|
|
label_num += 1
|