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