---

kruskal.h

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

#ifndef KRUSKAL_H
#define KRUSKAL_H

#include <vector>

#include "../data_structures/edgeVector.h"
#include "../data_structures/mst.h"

template < typename EdgeType = Edge >
class Kruskal
{
 public:
    Kruskal(EdgeVector<EdgeType> &graph, MST &result)
        : _graph( graph ), _result( result )
        {
            computeMST();
        }

    ~Kruskal() {delete &_graph;}
    
 private:
    void computeMST();
    
    void initUnionFind();


    NodeID find(NodeID node);

    bool unite(NodeID node1, NodeID node2);


    EdgeVector<EdgeType> &_graph;

    MST &_result;

    std::vector<NodeID> _parent;

    std::vector<char> _height;

    EdgeCount edgesAddedToResult;
    
};


template < typename EdgeType >
inline NodeID Kruskal<EdgeType>::find(NodeID node)
{
    // find the root
    NodeID root = node;
    while (_parent[root] != root) root = _parent[root];

    // apply path compression
    NodeID tmp;
    while (_parent[node] != node) {
        tmp = _parent[node];
        _parent[node] = root;
        node = tmp;
    }
    
    return root;
}

template < typename EdgeType >
inline bool Kruskal<EdgeType>::unite(NodeID node1, NodeID node2)
{
    NodeID root1 = find(node1);
    NodeID root2 = find(node2);

    // A cycle would be produced. Therefore the union operation is cancelled.
    if (root1 == root2) return false;

    // Add the smaller tree to the bigger tree
    if (_height[root1] < _height[root2]) {
        _parent[root1] = root2;
    }
    else {
        _parent[root2] = root1;
        
        // Increment the height of the resulting tree if both trees have
        // the same height
        if (_height[root1] == _height[root2]) _height[root1]++;
    }
    return true;
}


#endif // KRUSKAL_H

---