source: lemon-0.x/src/work/johanna/kruskal.h @ 203:fc4699a76a6f

// -*- c++ -*- //
#ifndef HUGO_KRUSKAL_H
#define HUGO_KRUSKAL_H

#include "unionfind.h"
#include <algorithm>

namespace hugo {

  template <typename EdgeCostPair> static
  bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
    return a.second < b.second;
  }


  template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>

  typename EdgeDoubleMap::ValueType 
  MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap, 
                     EdgeBoolMap& treemap) 
  {
    
    typedef typename EdgeDoubleMap::ValueType EDouble;
    typedef typename Graph::EachEdgeIt EachEdgeIt;
    typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;


    typedef std::vector<EdgeCostPair> EdgeCostVector;
    EdgeCostVector rank;

    for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
      rank.push_back(make_pair(e, costmap.get(e)));
    }

    
    std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);

    typedef typename Graph::NodeMap<int> NodeIntMap;
    typedef typename Graph::NodeIt NodeIt;
    NodeIntMap comp_map(G, -1);
    UnionFind<NodeIt,NodeIntMap> uf(comp_map); 

    EDouble tot_cost = 0;
    for (typename EdgeCostVector::iterator p = rank.begin(); 
         p!=rank.end(); ++p ) {
      if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
        treemap.set(p->first, true);
        tot_cost += p->second;
      }
      else {
        treemap.set(p->first, false);
      }
    }
    return tot_cost;
  }


} //namespace hugo

#endif //HUGO_KRUSKAL_H