nearest_neighbor_graph()

MAYAFLUX_API EdgeList MayaFlux::Kinesis::nearest_neighbor_graph

(

const Eigen::MatrixXd &

points

)

Compute nearest neighbor graph.

Parameters

points

DxN matrix where each column is a point

Returns

Edge list of nearest neighbor edges

Connects each point to its single nearest neighbor. Directed graph: point i connects to nearest neighbor j, but j may connect to a different point k.

Complexity: O(n²) brute force

Definition at line 457 of file ProximityGraphs.cpp.

{
    const auto n = static_cast<size_t>(points.cols());
    if (n < 2) {
        return {};
    }
 
    const auto dim = static_cast<size_t>(points.rows());
    const double* base = points.data();
 
    std::vector<size_t> nearest(n);
 
    P::for_each(P::par_unseq,
        std::views::iota(size_t { 0 }, n).begin(),
        std::views::iota(size_t { 0 }, n).end(),
        [&](size_t i) {
            double min_dist_sq = std::numeric_limits<double>::max();
            size_t best = i;
 
            const double* pi = base + i * dim;
            for (size_t j = 0; j < n; ++j) {
                if (i == j) {
                    continue;
                }
                const double d = dist_sq(pi, base + j * dim, dim);
                if (d < min_dist_sq) {
                    min_dist_sq = d;
                    best = j;
                }
            }
 
            nearest[i] = best;
        });
 
    EdgeList edges;
    edges.reserve(n);
 
    for (size_t i = 0; i < n; ++i) {
        if (nearest[i] != i) {
            edges.emplace_back(i, nearest[i]);
        }
    }
 
    MF_DEBUG(Journal::Component::Kinesis, Journal::Context::Runtime,
        "nearest_neighbor_graph: {} points, generated {} edges", n, 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: