beckerjc@150: // -*- c++ -*- //
beckerjc@150: #ifndef HUGO_KRUSKAL_H
beckerjc@150: #define HUGO_KRUSKAL_H
beckerjc@150: 
beckerjc@150: #include "unionfind.h"
beckerjc@150: #include <algorithm>
beckerjc@150: 
beckerjc@150: namespace hugo {
beckerjc@150: 
beckerjc@150:   template <typename EdgeCostPair> static
beckerjc@150:   bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
beckerjc@150:     return a.second < b.second;
beckerjc@150:   }
beckerjc@150: 
beckerjc@150: 
beckerjc@150:   template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
beckerjc@150: 
beckerjc@150:   typename EdgeDoubleMap::ValueType 
beckerjc@150:   MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap, 
beckerjc@150: 		     EdgeBoolMap& treemap) 
beckerjc@150:   {
beckerjc@150:     
beckerjc@150:     typedef typename EdgeDoubleMap::ValueType EDouble;
beckerjc@150:     typedef typename Graph::EachEdgeIt EachEdgeIt;
beckerjc@150:     typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
beckerjc@150: 
beckerjc@150: 
beckerjc@150:     typedef std::vector<EdgeCostPair> EdgeCostVector;
beckerjc@150:     EdgeCostVector rank;
beckerjc@150: 
beckerjc@150:     for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
beckerjc@150:       rank.push_back(make_pair(e, costmap.get(e)));
beckerjc@150:     }
beckerjc@150: 
beckerjc@150:     
beckerjc@150:     std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
beckerjc@150: 
beckerjc@150:     typedef typename Graph::NodeMap<int> NodeIntMap;
beckerjc@150:     typedef typename Graph::NodeIt NodeIt;
beckerjc@150:     NodeIntMap comp_map(G, -1);
beckerjc@150:     UnionFind<NodeIt,NodeIntMap> uf(comp_map); 
beckerjc@150: 
beckerjc@150:     EDouble tot_cost = 0;
beckerjc@150:     for (typename EdgeCostVector::iterator p = rank.begin(); 
beckerjc@150: 	 p!=rank.end(); ++p ) {
beckerjc@150:       if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
beckerjc@150: 	treemap.set(p->first, true);
beckerjc@150: 	tot_cost += p->second;
beckerjc@150:       }
beckerjc@150:       else {
beckerjc@150: 	treemap.set(p->first, false);
beckerjc@150:       }
beckerjc@150:     }
beckerjc@150:     return tot_cost;
beckerjc@150:   }
beckerjc@150: 
beckerjc@150: 
beckerjc@150: } //namespace hugo
beckerjc@150: 
beckerjc@150: #endif //HUGO_KRUSKAL_H