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: 
beckerjc@218:   template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
beckerjc@218:   class MinCostTreeKruskal
beckerjc@218:   {
beckerjc@150: 
beckerjc@218:     typedef typename Graph::EdgeIt EdgeIt;
beckerjc@218:     typedef typename Graph::Edge Edge;
beckerjc@150: 
beckerjc@218:   public:
beckerjc@218:     typedef typename EdgeCostMap::ValueType EdgeCost;
beckerjc@218:     typedef std::pair<Edge, EdgeCost> EdgeCostPair;
beckerjc@218:     typedef std::vector<EdgeCostPair> EdgeCostVector;
beckerjc@150:     
beckerjc@218:   private:
beckerjc@218:     Graph const &G;
beckerjc@218:     EdgeCostMap const &costmap;
beckerjc@218:     EdgeBoolMap& treemap;
beckerjc@218:     
beckerjc@218:     //template <typename EdgeCostPair>
beckerjc@218:     class comparePair {
beckerjc@218:     public:
beckerjc@218:       bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) {
beckerjc@218: 	return a.second < b.second;
beckerjc@218:       }
beckerjc@218:     };
beckerjc@150: 
beckerjc@218:   public:
beckerjc@150: 
beckerjc@150: 
beckerjc@218:     MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap, 
beckerjc@218: 		       EdgeBoolMap& _treemap) : G(_G), costmap(_costmap), 
beckerjc@218: 						treemap(_treemap) {}
beckerjc@218:   
beckerjc@218: 
beckerjc@218:     EdgeCost run() 
beckerjc@218:     {
beckerjc@218:      EdgeCostVector rank;
beckerjc@218:      for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
beckerjc@218: 	rank.push_back(make_pair(e, costmap.get(e)));
beckerjc@218:       }
beckerjc@218:       
beckerjc@218:       std::sort(rank.begin(), rank.end(), comparePair());
beckerjc@218: 
beckerjc@218:       return run(rank);
beckerjc@218:     
beckerjc@150:     }
beckerjc@150: 
beckerjc@218:     EdgeCost run(EdgeCostVector const &rank)
beckerjc@218:     {
beckerjc@218:       typedef typename Graph::NodeMap<int> NodeIntMap;
beckerjc@218:       typedef typename Graph::Node Node;
beckerjc@218:       NodeIntMap comp_map(G, -1);
beckerjc@218:       UnionFind<Node,NodeIntMap> uf(comp_map); 
beckerjc@218:       
beckerjc@218:       EdgeCost tot_cost = 0;
beckerjc@218:       for (typename EdgeCostVector::const_iterator p = rank.begin(); 
beckerjc@218: 	   p!=rank.end(); ++p ) {
beckerjc@218: 	if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
beckerjc@218: 	  treemap.set(p->first, true);
beckerjc@218: 	  tot_cost += p->second;
beckerjc@218: 	}
beckerjc@218: 	else {
beckerjc@218: 	  treemap.set(p->first, false);
beckerjc@218: 	}
beckerjc@218:       }
beckerjc@218:       return tot_cost;
beckerjc@150: 
beckerjc@218:     }
beckerjc@150: 
beckerjc@218:   };
beckerjc@150: 
beckerjc@150: 
beckerjc@150: } //namespace hugo
beckerjc@150: 
beckerjc@150: #endif //HUGO_KRUSKAL_H