minimum_spanning_tree()

MAYAFLUX_API EdgeList MayaFlux::Kinesis::minimum_spanning_tree

(

const Eigen::MatrixXd &

points

)

Compute minimum spanning tree (Prim's algorithm)

Parameters

points

DxN matrix where each column is a point

Returns

Edge list forming MST

Returns exactly (n-1) edges forming tree of minimum total length that connects all points. Undirected acyclic graph.

Complexity: O(n² log n) with priority queue

Definition at line 360 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();
 
    EdgeList mst_edges;
    mst_edges.reserve(n - 1);
 
    std::vector<bool> in_mst(n, false);
    std::priority_queue<Edge, std::vector<Edge>, std::greater<>> pq;
 
    in_mst[0] = true;
 
    for (size_t j = 1; j < n; ++j) {
        pq.push({ .a = 0, .b = j, .weight = std::sqrt(dist_sq(base, base + j * dim, dim)) });
    }
 
    while (!pq.empty() && mst_edges.size() < n - 1) {
        const Edge e = pq.top();
        pq.pop();
 
        if (in_mst[e.b]) {
            continue;
        }
 
        mst_edges.emplace_back(e.a, e.b);
        in_mst[e.b] = true;
 
        const double* pb = base + e.b * dim;
        for (size_t j = 0; j < n; ++j) {
            if (!in_mst[j]) {
                pq.push({ .a = e.b, .b = j, .weight = std::sqrt(dist_sq(pb, base + j * dim, dim)) });
            }
        }
    }
 
    MF_DEBUG(Journal::Component::Kinesis, Journal::Context::Runtime,
        "minimum_spanning_tree: {} points, generated {} edges",
        n, mst_edges.size());
 
    return mst_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: