boruvkas_minimum_spanning_tree.cpp File Reference

[Borůvkas Algorithm](https://en.wikipedia.org/wiki/Borůvka's_algorithm) to find the Minimum Spanning Tree More...

#include <cassert>
#include <climits>
#include <iostream>
#include <vector>

Include dependency graph for boruvkas_minimum_spanning_tree.cpp:

Namespaces
namespace	greedy_algorithms
	for std::vector
namespace	boruvkas_minimum_spanning_tree
	Functions for the [Borůvkas Algorithm](https://en.wikipedia.org/wiki/Borůvka's_algorithm) implementation.

Functions
int	greedy_algorithms::boruvkas_minimum_spanning_tree::findParent (std::vector< std::pair< int, int > > parent, const int v)
	Recursively returns the vertex's parent at the root of the tree.
std::vector< std::vector< int > >	greedy_algorithms::boruvkas_minimum_spanning_tree::boruvkas (std::vector< std::vector< int > > adj)
	the implementation of boruvka's algorithm
int	greedy_algorithms::boruvkas_minimum_spanning_tree::test_findGraphSum (std::vector< std::vector< int > > adj)
	counts the sum of edges in the given tree
static void	tests ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

[Borůvkas Algorithm](https://en.wikipedia.org/wiki/Borůvka's_algorithm) to find the Minimum Spanning Tree

Author

Jason Nardoni

Boruvka's algorithm is a greepy algorithm to find the MST by starting with small trees, and combining them to build bigger ones.

1. Creates a group for every vertex.
2. looks through each edge of every vertex for the smallest weight. Keeps track of the smallest edge for each of the current groups.

Combine each group with the group it shares its smallest edge, adding the smallest edge to the MST.

1. Repeat step 2-3 until all vertices are combined into a single group.

It assumes that the graph is connected. Non-connected edges can be represented using 0 or INT_MAX

Function Documentation

boruvkas()

std::vector< std::vector< int > > greedy_algorithms::boruvkas_minimum_spanning_tree::boruvkas

(

std::vector< std::vector< int > >

adj

)

the implementation of boruvka's algorithm

Parameters

adj	a graph adjancency matrix stored as 2d vectors.

Returns

the MST as 2d vectors

                                                                  {
    size_t size = adj.size();
    size_t total_groups = size;
 
    if (size <= 1) {
        return adj;
    }
 
    // Stores the current Minimum Spanning Tree. As groups are combined, they
    // are added to the MST
    std::vector<std::vector<int>> MST(size, std::vector<int>(size, INT_MAX));
    for (int i = 0; i < size; i++) {
        MST[i][i] = 0;
    }
 
    // Step 1: Create a group for each vertex
 
    // Stores the parent of the vertex and its current depth, both initialized
    // to 0
    std::vector<std::pair<int, int>> parent(size, std::make_pair(0, 0));
 
    for (int i = 0; i < size; i++) {
        parent[i].first =
            i;  // Sets parent of each vertex to itself, depth remains 0
    }
 
    // Repeat until all are in a single group
    while (total_groups > 1) {
        std::vector<std::pair<int, int>> smallest_edge(
            size, std::make_pair(-1, -1));  // Pairing: start node, end node
 
        // Step 2: Look throught each vertex for its smallest edge, only using
        // the right half of the adj matrix
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                if (adj[i][j] == INT_MAX || adj[i][j] == 0) {  // No connection
                    continue;
                }
 
                // Finds the parents of the start and end points to make sure
                // they arent in the same group
                int parentA = findParent(parent, i);
                int parentB = findParent(parent, j);
 
                if (parentA != parentB) {
                    // Grabs the start and end points for the first groups
                    // current smallest edge
                    int start = smallest_edge[parentA].first;
                    int end = smallest_edge[parentA].second;
 
                    // If there is no current smallest edge, or the new edge is
                    // smaller, records the new smallest
                    if (start == -1 || adj[i][j] < adj[start][end]) {
                        smallest_edge[parentA].first = i;
                        smallest_edge[parentA].second = j;
                    }
 
                    // Does the same for the second group
                    start = smallest_edge[parentB].first;
                    end = smallest_edge[parentB].second;
 
                    if (start == -1 || adj[j][i] < adj[start][end]) {
                        smallest_edge[parentB].first = j;
                        smallest_edge[parentB].second = i;
                    }
                }
            }
        }
 
        // Step 3: Combine the groups based off their smallest edge
 
        for (int i = 0; i < size; i++) {
            // Makes sure the smallest edge exists
            if (smallest_edge[i].first != -1) {
                // Start and end points for the groups smallest edge
                int start = smallest_edge[i].first;
                int end = smallest_edge[i].second;
 
                // Parents of the two groups - A is always itself
                int parentA = i;
                int parentB = findParent(parent, end);
 
                // Makes sure the two nodes dont share the same parent. Would
                // happen if the two groups have been
                // merged previously through a common shortest edge
                if (parentA == parentB) {
                    continue;
                }
 
                // Tries to balance the trees as much as possible as they are
                // merged. The parent of the shallower
                // tree will be pointed to the parent of the deeper tree.
                if (parent[parentA].second < parent[parentB].second) {
                    parent[parentB].first = parentA;  // New parent
                    parent[parentB].second++;         // Increase depth
                } else {
                    parent[parentA].first = parentB;
                    parent[parentA].second++;
                }
                // Add the connection to the MST, using both halves of the adj
                // matrix
                MST[start][end] = adj[start][end];
                MST[end][start] = adj[end][start];
                total_groups--;  // one fewer group
            }
        }
    }
    return MST;
}

Here is the call graph for this function:

findParent()

int greedy_algorithms::boruvkas_minimum_spanning_tree::findParent	(	std::vector< std::pair< int, int > >	parent,
		const int	v )

Recursively returns the vertex's parent at the root of the tree.

Parameters

parent	the array that will be checked
v	vertex to find parent of

Returns

the parent of the vertex

                                                                 {
    if (parent[v].first != v) {
        parent[v].first = findParent(parent, parent[v].first);
    }
 
    return parent[v].first;
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    tests();  // run self-test implementations
    return 0;
}

Here is the call graph for this function:

test_findGraphSum()

int greedy_algorithms::boruvkas_minimum_spanning_tree::test_findGraphSum

(

std::vector< std::vector< int > >

adj

)

counts the sum of edges in the given tree

Parameters

adj	2D vector adjacency matrix

Returns

the int size of the tree

                                                     {
    size_t size = adj.size();
    int sum = 0;
 
    // Moves through one side of the adj matrix, counting the sums of each edge
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (adj[i][j] < INT_MAX) {
                sum += adj[i][j];
            }
        }
    }
    return sum;
}

Here is the call graph for this function:

tests()

static void tests ( )

static

Self-test implementations.

Returns

void

                    {
    std::cout << "Starting tests...\n\n";
    std::vector<std::vector<int>> graph = {
        {0, 5, INT_MAX, 3, INT_MAX}, {5, 0, 2, INT_MAX, 5},
        {INT_MAX, 2, 0, INT_MAX, 3}, {3, INT_MAX, INT_MAX, 0, INT_MAX},
        {INT_MAX, 5, 3, INT_MAX, 0},
    };
    std::vector<std::vector<int>> MST =
        greedy_algorithms::boruvkas_minimum_spanning_tree::boruvkas(graph);
    assert(greedy_algorithms::boruvkas_minimum_spanning_tree::test_findGraphSum(
               MST) == 13);
    std::cout << "1st test passed!" << std::endl;
 
    graph = {{0, 2, 0, 6, 0},
             {2, 0, 3, 8, 5},
             {0, 3, 0, 0, 7},
             {6, 8, 0, 0, 9},
             {0, 5, 7, 9, 0}};
    MST = greedy_algorithms::boruvkas_minimum_spanning_tree::boruvkas(graph);
    assert(greedy_algorithms::boruvkas_minimum_spanning_tree::test_findGraphSum(
               MST) == 16);
    std::cout << "2nd test passed!" << std::endl;
}

Here is the call graph for this function: