---

kruskal.cpp

/****************************************************
 *  Bachelor Project:                               *
 *  External Memory Minimum Spanning Trees          *
 *  by Dominik Schultes <mail@dominik-schultes.de>  *
 *                                                  *
 *                kruskal.cpp                       *
 *                                                  *
 *  April 13, 2003                                  *
 ****************************************************/


#include "kruskal.h"

#include "../utils/utils.h"

template < typename EdgeType >
void Kruskal<EdgeType>::computeMST()
{
    // sort
    DS_LOGGING2( logMemoryUsage("before sorting") );
    DS_VERBOSE1( std::cout << std::endl << "Kruskal: sort edges" << std::endl );
    _graph.sortByWeight();
    DS_LOGGING2( logMemoryUsage("after sorting") );
    DS_LOGGING1( logging.events().push_back(LoggingEvent("Kruskal: edges sorted")) );
    

    
    // initialize
    DS_VERBOSE1( std::cout << std::endl << "Kruskal: initialize data structures"
                           << std::endl );
    initUnionFind();
    DS_LOGGING2( logMemoryUsage("after initialization") );
    DS_LOGGING1( logging.events().push_back(
                     LoggingEvent("Kruskal: data structures initialized")) );

    
    
    // process edges
    DS_VERBOSE1( std::cout << std::endl << "Kruskal: process edges" << std::endl;
                 Percent percent(_graph.noOfEdges()) );
    // abort the for-loop when the MST is complete or when all edges have been processed.
    for (EdgeCount i=0;
         (edgesAddedToResult < _graph.noOfNodes()-1) && (i<_graph.noOfEdges());
         i++) {
        DS_VERBOSE1( percent.printStatus(i) );
            
        // perform union operation according to the current edge
        if (unite( _graph[i].source(), _graph[i].target() )) {
            // The current edge doesn't produce a cyle.
            // Hence, add it to the resulting MST.
            _result.add(_graph[i]);
            edgesAddedToResult++;
        }       
    }

    DS_LOGGING1( logging.events().push_back(LoggingEvent("Kruskal: edges processed")) );
    
}

template < typename EdgeType >
void Kruskal<EdgeType>::initUnionFind()
{
    // init parent vector
    _parent.resize(_graph.noOfNodes());
    for (NodeCount i=0; i<_parent.size(); i++) _parent[i] = i;

    // init height vector
    _height.resize(_graph.noOfNodes());

    edgesAddedToResult = 0;
}

---