Finding Minimal Spanning Trees using Kruskal’s Algorithm in MFC / C++ / Boost libraries

Kruskal’s algorithm is used to find the minimal spanning tree for a network with a set of weighted links. This might be a telecoms network, or the layout for planning pipes and cables, or one of many other applications.

It is a greedy algorithm that finds the set of links for which the total weight is a minimum, subject to the constraint that the resulting network is a tree containing no cycles. In other words, the objective is to produce a spanning tree of minimal weight.

In this implementation, the Boost Graph Library is used to take an undirected graph represented by a node or edge list, along with the weights of each link in the graph, and return the edge list that comprises the minimal spanning tree. 

If it is just a simple C++ implementation of Kruskal’s algorithm you are after, without GUI and Boost libraries, here is another post with some downloadable code.

The example implementation that I used in my own version is given below:

#include "stdafx.h"
#include "Algorithm.h"

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

using namespace boost;
using namespace std;

//
// Kruskal's algorithm for finding minimum spanning tree
//
void Algorithm::Kruskal( Network &network, vector< Link > &mst )
{
    typedef adjacency_list < vecS,
                             vecS,
                             undirectedS,
                             no_property,
                             property < edge_weight_t, int >> Graph;

     typedef graph_traits < Graph >::edge_descriptor   Edge;
     typedef graph_traits < Graph >::vertex_descriptor Vertex;
     typedef std::pair<int, int> E;

     const int num_nodes = network.GetNodeCount();
     const int num_links = network.GetLinkCount();   

     Graph g( num_nodes );

     property_map< Graph, edge_weight_t >::type weightmap = get( edge_weight, g );

     for ( size_t j = 0;
           j < num_links;
           ++j )
     {
         Edge e;
         bool inserted;
         tie( e, inserted ) = add_edge( network.GetLinkStartNode( j ),
                                        network.GetLinkEndNode( j ),
                                        g );

         weightmap[ e ] = (size_t) network.GetLinkWeight( j );
     }

     property_map < Graph, edge_weight_t >::type weight =
         get( edge_weight, g );

     std::vector< Edge > spanning_tree;

     kruskal_minimum_spanning_tree( g, std::back_inserter( spanning_tree ) );

     std::cout << "Print the edges in the MST:" << std::endl;

     for ( vector::iterator ei = spanning_tree.begin();
           ei != spanning_tree.end();
           ++ei )
     {
         Link l( (int) source(*ei, g),
                 (int) target(*ei, g),
                 (int) weight[*ei] );

         mst.push_back( l );
     }
}

This implementation also provides a graphical representation of the nodes and their interconnecting links using standard MFC calls to draw the network links and nodes. Nodes are added by a left mouse click and their integer identifiers are allocated in ascending numerical order

To allocate a link, left-click near the vicinity of the intended ‘start’ node, hold the mouse button down and drag towards the intended ‘end’ node before releasing:

http://1.bp.blogspot.com/_k07gmqgR5OE/S7mg97Mi6QI/AAAAAAAAABY/cwXJdBOrZXA/s1600/Kruskal2.JPG

Set the ‘weights’ of the interconnecting links by right-clicking the link and choosing ‘Link Properties’ from the drop-down menu. The default value for each link added is 1.0 units. The user also has the option to delete selected links via the same drop-down menu:

 http://4.bp.blogspot.com/_k07gmqgR5OE/S7mhLf9DF0I/AAAAAAAAABg/N7TvOkK1Zos/s1600/Kruskal3.JPG

Once the link connection weights have been set, select ‘Kruskal’ from the main menu to give a graphical representation of the minimal spanning tree:

http://3.bp.blogspot.com/_k07gmqgR5OE/S7mhSrARv_I/AAAAAAAAABo/dlQCMkSKVYo/s1600/Kruskal4.JPG

Sample Visual Studio 2003 code here:

Please note: for this to build properly and avoid linker errors you will need to have the Boost libraries installed and set up for your Visual Studio project. Here’s how.

Using the software in Visual Studio 2010 / Other Issues

1. After you have downloaded and unzipped KruskalAlg.zip and tried to build it in VS 2010 the compiler whinges about “This file requires _WIN32_WINNT to be #defined at least to 0x0403”.

Go into the stdafx.h file and change:

#define _WIN32_WINNT 0x0400 to
#define _WIN32_WINNT 0x0500

2. Check you have downloaded and installed Boost and check your project dependency settings.  In Project Configuration Properties select C/C++ -> General tab and check the setting for “Additional Include Directories”:

Check that this setting matches the version of Boost that you have downloaded and installed on your machine (usually in the “C:\Program Files\” directory).

Since this was written some time ago, it’s likely that you will have a more recent version of Boost than the one contained in the downloaded project (1_42_0).   If not then you probably don’t need to do anything else.  So long as the version numbers match, that’s all that matters…

A Visual Studio 2010 version of the same is downloadable from here.




`