Minimum Spanning Tree Library

A high-performance C++17 header-only library for computing Minimum Spanning Trees (MST) using Kruskal's algorithm.

Features

• Header-only: Easy to integrate into any project
• Template-based: Supports various coordinate types (int, double, float, etc.)
• Optimized: Uses Union-Find with path compression and union by rank
• Well-tested: Comprehensive unit tests with Google Test
• Benchmarked: Performance benchmarks with Google Benchmark
• Modern C++: Clean C++17 code following best practices

Algorithm

The library implements Kruskal's algorithm for finding the minimum spanning tree:

• Time Complexity: O(E log E) where E is the number of edges
• Space Complexity: O(V + E) where V is the number of vertices

The implementation uses an optimized Union-Find data structure with:

• Path compression for find operations
• Union by rank for balanced tree structures

Quick Start

Building the Project

mkdir build && cd build
cmake ..
make

Running Tests

./tests/mst_tests

Running Benchmarks

./benchmarks/mst_benchmarks

Usage Example

#include "MinimumSpanningTree.hpp"
#include <iostream>

using namespace MinimumSpanningTree;

int main()
{
    // Create nodes with (id, x, y)
    std::vector<MST_Node<double>> nodes;
    nodes.emplace_back("A", 0.0, 0.0);
    nodes.emplace_back("B", 1.0, 0.0);
    nodes.emplace_back("C", 1.0, 1.0);
    nodes.emplace_back("D", 0.0, 1.0);

    // Generate MST using Kruskal's algorithm
    auto mst = generateMST_Kruskal(nodes);

    // Print connections
    for (const auto& connection : mst)
    {
        std::cout << connection.first << " -- "
                  << connection.second << std::endl;
    }

    return 0;
}

API Documentation

MST_Node

Represents a node in the graph with a unique ID and 2D position.

Constructor:

MST_Node(const std::string& nodeId, CoordType xCoord, CoordType yCoord)
MST_Node(const std::string& nodeId, const std::tuple<CoordType, CoordType>& nodePosition)

Methods:

• const std::string& getId() const - Get node ID
• const std::tuple<CoordType, CoordType>& getPosition() const - Get position
• CoordType getX() const - Get X coordinate
• CoordType getY() const - Get Y coordinate

MST_Edge

Represents an edge between two nodes with an associated weight.

Constructor:

MST_Edge(const std::string& firstNode, const std::string& secondNode, double edgeWeight)

Methods:

• const std::string& getNodeA() const - Get first node ID
• const std::string& getNodeB() const - Get second node ID
• double getWeight() const - Get edge weight

Functions

generateMST_Kruskal()

template<typename CoordType>
std::vector<std::pair<std::string, std::string>> generateMST_Kruskal(
    const std::vector<MST_Node<CoordType>>& nodes)

Computes the minimum spanning tree for the given nodes.

calculateDistance()

template<typename CoordType>
double calculateDistance(
    const std::tuple<CoordType, CoordType>& pos1,
    const std::tuple<CoordType, CoordType>& pos2)

Calculates Euclidean distance between two positions.

Code Quality

This library follows strict coding standards:

• Encapsulation: Private members with public accessors
• Functional Abstraction: Single responsibility per function
• DRY Principle: No code duplication
• Readability: Clear naming and documentation
• Simplicity: Maximum 2 levels of nesting per function
• Efficiency: Optimized algorithms and data structures

Requirements

• CMake 3.14 or higher
• C++17 compatible compiler (GCC 7+, Clang 5+, MSVC 2017+)
• Internet connection (for downloading Google Test and Google Benchmark)

License

See LICENSE file for details.

Contributing

This library was developed as part of the CultGame project. Contributions are welcome!