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
|
# Fast inner loop for DBSCAN.
# Author: Lars Buitinck
# License: 3-clause BSD
cimport cython
from libcpp.vector cimport vector
from libcpp.set cimport set as cset
cimport numpy as np
import numpy as np
# Work around Cython bug: C++ exceptions are not caught unless thrown within
# a cdef function with an "except +" declaration.
cdef inline void push(vector[np.npy_intp] &stack, np.npy_intp i) except +:
stack.push_back(i)
@cython.boundscheck(False)
@cython.wraparound(False)
def dbscan_inner(np.ndarray[np.uint8_t, ndim=1, mode='c'] is_core,
np.ndarray[object, ndim=1] neighborhoods,
np.ndarray[np.npy_intp, ndim=1, mode='c'] labels):
cdef np.npy_intp i, label_num = 0, v
cdef np.ndarray[np.npy_intp, ndim=1] neighb
cdef vector[np.npy_intp] stack
cdef cset[np.npy_intp] seen
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 and seen.count(v) == 0:
seen.insert(v)
push(stack, v)
if stack.size() == 0:
break
i = stack.back()
stack.pop_back()
seen.clear()
label_num += 1
|
