[150] | 1 | // -*- c++ -*- // |
---|
| 2 | #ifndef HUGO_KRUSKAL_H |
---|
| 3 | #define HUGO_KRUSKAL_H |
---|
| 4 | |
---|
| 5 | #include "unionfind.h" |
---|
| 6 | #include <algorithm> |
---|
| 7 | |
---|
| 8 | namespace hugo { |
---|
| 9 | |
---|
| 10 | template <typename EdgeCostPair> static |
---|
| 11 | bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) { |
---|
| 12 | return a.second < b.second; |
---|
| 13 | } |
---|
| 14 | |
---|
| 15 | |
---|
| 16 | template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap> |
---|
| 17 | |
---|
| 18 | typename EdgeDoubleMap::ValueType |
---|
| 19 | MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap, |
---|
| 20 | EdgeBoolMap& treemap) |
---|
| 21 | { |
---|
| 22 | |
---|
| 23 | typedef typename EdgeDoubleMap::ValueType EDouble; |
---|
| 24 | typedef typename Graph::EachEdgeIt EachEdgeIt; |
---|
| 25 | typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair; |
---|
| 26 | |
---|
| 27 | |
---|
| 28 | typedef std::vector<EdgeCostPair> EdgeCostVector; |
---|
| 29 | EdgeCostVector rank; |
---|
| 30 | |
---|
| 31 | for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { |
---|
| 32 | rank.push_back(make_pair(e, costmap.get(e))); |
---|
| 33 | } |
---|
| 34 | |
---|
| 35 | |
---|
| 36 | std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>); |
---|
| 37 | |
---|
| 38 | typedef typename Graph::NodeMap<int> NodeIntMap; |
---|
| 39 | typedef typename Graph::NodeIt NodeIt; |
---|
| 40 | NodeIntMap comp_map(G, -1); |
---|
| 41 | UnionFind<NodeIt,NodeIntMap> uf(comp_map); |
---|
| 42 | |
---|
| 43 | EDouble tot_cost = 0; |
---|
| 44 | for (typename EdgeCostVector::iterator p = rank.begin(); |
---|
| 45 | p!=rank.end(); ++p ) { |
---|
| 46 | if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) { |
---|
| 47 | treemap.set(p->first, true); |
---|
| 48 | tot_cost += p->second; |
---|
| 49 | } |
---|
| 50 | else { |
---|
| 51 | treemap.set(p->first, false); |
---|
| 52 | } |
---|
| 53 | } |
---|
| 54 | return tot_cost; |
---|
| 55 | } |
---|
| 56 | |
---|
| 57 | |
---|
| 58 | } //namespace hugo |
---|
| 59 | |
---|
| 60 | #endif //HUGO_KRUSKAL_H |
---|