minimum_spanning_tree()

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

{
    Eigen::Index n = points.cols();
    if (n < 2) {
        return {};
    }
 
    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 (Eigen::Index j = 1; j < n; ++j) {
        double dist = distance(points.col(0), points.col(j));
        pq.push({ 0, static_cast<size_t>(j), dist });
    }
 
    while (!pq.empty() && mst_edges.size() < static_cast<size_t>(n - 1)) {
        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;
 
        for (Eigen::Index j = 0; j < n; ++j) {
            if (!in_mst[j]) {
                double dist = distance(points.col(e.b), points.col(j));
                pq.push({ e.b, static_cast<size_t>(j), dist });
            }
        }
    }
 
    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, and MayaFlux::Journal::Runtime.

Referenced by generate_proximity_graph().

Here is the caller graph for this function: