// -*- 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