k_nearest_neighbors()

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 46 of file ProximityGraphs.cpp.

{
    Eigen::Index n = points.cols();
    if (n < 2) {
        return {};
    }
 
    k = std::min(k, static_cast<size_t>(n - 1));
 
    EdgeList edges;
    edges.reserve(n * k);
 
    for (Eigen::Index i = 0; i < n; ++i) {
        std::vector<std::pair<double, size_t>> distances;
        distances.reserve(n - 1);
 
        for (Eigen::Index j = 0; j < n; ++j) {
            if (i == j)
                continue;
            double dist_sq = distance_squared(points.col(i), points.col(j));
            distances.emplace_back(dist_sq, static_cast<size_t>(j));
        }
 
        std::partial_sort(
            distances.begin(),
            distances.begin() + k,
            distances.end());
 
        for (size_t neighbor_idx = 0; neighbor_idx < k; ++neighbor_idx) {
            edges.emplace_back(static_cast<size_t>(i), distances[neighbor_idx].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, and MayaFlux::Journal::Runtime.

Referenced by generate_proximity_graph().

Here is the caller graph for this function: