按需计算距离，构建单链聚类层次

569        if (570            linkage == "single"571            and affinity != "precomputed"572            and not callable(affinity)573            and affinity in METRIC_MAPPING64574        ):575            # We need the fast cythonized metric from neighbors576            dist_metric = DistanceMetric.get_metric(affinity)577578            # The Cython routines used require contiguous arrays579            X = np.ascontiguousarray(X, dtype=np.double)580581            mst = _hierarchical.mst_linkage_core(X, dist_metric)582            # Sort edges of the min_spanning_tree by weight583            mst = mst[np.argsort(mst.T[2], kind="mergesort"), :]584585            # Convert edge list into standard hierarchical clustering format586            out = _hierarchical.single_linkage_label(mst)587        else:588            out = hierarchy.linkage(X, method=linkage, metric=affinity)

478    for i in range(n_samples - 1):479480        in_tree[current_node] = 1481482        new_distance = INFINITY483        new_node = 0484485        for j in range(n_samples):486            if in_tree[j]:487                continue488489            right_value = current_distances[j]490            left_value = dist_metric.dist(&raw_data[current_node, 0],491                                          &raw_data[j, 0],492                                          num_features)493494            if left_value < right_value:495                current_distances[j] = left_value496497            if current_distances[j] < new_distance:498                new_distance = current_distances[j]499                new_node = j

501        result[i, 0] = current_node502        result[i, 1] = new_node503        result[i, 2] = new_distance504        current_node = new_node505506    return np.array(result)

338    @cython.wraparound(True)339    cdef intp_t fast_find(self, intp_t n) noexcept:340        cdef intp_t p341        p = n342        # find the highest node in the linkage graph so far343        while self.parent[n] != -1:344            n = self.parent[n]345        # provide a shortcut up to the highest node346        while self.parent[p] != n:347            p, self.parent[p] = self.parent[p], n348        return n

376    result_arr = np.zeros((L.shape[0], 4), dtype=np.float64)377    U = UnionFind(L.shape[0] + 1)378379    for index in range(L.shape[0]):380381        left = <intp_t> L[index, 0]382        right = <intp_t> L[index, 1]383        delta = L[index, 2]384385        left_cluster = U.fast_find(left)386        right_cluster = U.fast_find(right)387388        result_arr[index][0] = left_cluster389        result_arr[index][1] = right_cluster390        result_arr[index][2] = delta391        result_arr[index][3] = U.size[left_cluster] + U.size[right_cluster]392393        U.union(left_cluster, right_cluster)394395    return np.asarray(result_arr)