k_nearest_neighbors()

MAYAFLUX_API EdgeList MayaFlux::Kinesis::k_nearest_neighbors	(	const Eigen::MatrixXd &	points,
		size_t	k
	)

Compute K-nearest neighbors graph.

Parameters

points	Dx N matrix where each column is a point
k	Number of nearest neighbors per point

Returns

Edge list (point index pairs)

For each point, connects it to its k nearest neighbors. Directed graph: point i connects to k neighbors, but neighbor j might not reciprocally connect to i.

Complexity: O(n² log k) with partial sort

Definition at line 254 of file ProximityGraphs.cpp.

{
    const auto n = static_cast<size_t>(points.cols());
    if (n < 2) {
        return {};
    }
 
    k = std::min(k, n - 1);
    if (k == 0) {
        return {};
    }
 
    const auto dim = static_cast<size_t>(points.rows());
    const double* base = points.data();
 
    EdgeList edges(n * k);
 
    std::for_each(std::execution::par_unseq,
        std::views::iota(size_t { 0 }, n).begin(),
        std::views::iota(size_t { 0 }, n).end(),
        [&](size_t i) {
            std::vector<std::pair<double, size_t>> distances;
            distances.reserve(n - 1);
 
            const double* pi = base + i * dim;
            for (size_t j = 0; j < n; ++j) {
                if (i == j) {
                    continue;
                }
                distances.emplace_back(dist_sq(pi, base + j * dim, dim), j);
            }
 
            std::partial_sort(
                distances.begin(),
                distances.begin() + static_cast<ptrdiff_t>(k),
                distances.end());
 
            for (size_t m = 0; m < k; ++m) {
                edges[i * k + m] = { i, distances[m].second };
            }
        });
 
    MF_DEBUG(Journal::Component::Kinesis, Journal::Context::Runtime,
        "k_nearest_neighbors: {} points, k={}, generated {} edges",
        n, k, edges.size());
 
    return edges;
}

References MayaFlux::Journal::Kinesis, MF_DEBUG, points, and MayaFlux::Journal::Runtime.

Referenced by generate_proximity_graph().

Here is the caller graph for this function: