5 #include "unionfind.h" |
5 #include "unionfind.h" |
6 #include <algorithm> |
6 #include <algorithm> |
7 |
7 |
8 namespace hugo { |
8 namespace hugo { |
9 |
9 |
10 template <typename EdgeCostPair> static |
10 |
11 bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) { |
11 template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap> |
12 return a.second < b.second; |
12 class MinCostTreeKruskal |
13 } |
13 { |
|
14 |
|
15 typedef typename Graph::EdgeIt EdgeIt; |
|
16 typedef typename Graph::Edge Edge; |
|
17 |
|
18 public: |
|
19 typedef typename EdgeCostMap::ValueType EdgeCost; |
|
20 typedef std::pair<Edge, EdgeCost> EdgeCostPair; |
|
21 typedef std::vector<EdgeCostPair> EdgeCostVector; |
|
22 |
|
23 private: |
|
24 Graph const &G; |
|
25 EdgeCostMap const &costmap; |
|
26 EdgeBoolMap& treemap; |
|
27 |
|
28 //template <typename EdgeCostPair> |
|
29 class comparePair { |
|
30 public: |
|
31 bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) { |
|
32 return a.second < b.second; |
|
33 } |
|
34 }; |
|
35 |
|
36 public: |
14 |
37 |
15 |
38 |
16 template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap> |
39 MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap, |
|
40 EdgeBoolMap& _treemap) : G(_G), costmap(_costmap), |
|
41 treemap(_treemap) {} |
|
42 |
17 |
43 |
18 typename EdgeDoubleMap::ValueType |
44 EdgeCost run() |
19 MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap, |
45 { |
20 EdgeBoolMap& treemap) |
46 EdgeCostVector rank; |
21 { |
47 for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
|
48 rank.push_back(make_pair(e, costmap.get(e))); |
|
49 } |
|
50 |
|
51 std::sort(rank.begin(), rank.end(), comparePair()); |
|
52 |
|
53 return run(rank); |
22 |
54 |
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 } |
55 } |
34 |
56 |
35 |
57 EdgeCost run(EdgeCostVector const &rank) |
36 std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>); |
58 { |
|
59 typedef typename Graph::NodeMap<int> NodeIntMap; |
|
60 typedef typename Graph::Node Node; |
|
61 NodeIntMap comp_map(G, -1); |
|
62 UnionFind<Node,NodeIntMap> uf(comp_map); |
|
63 |
|
64 EdgeCost tot_cost = 0; |
|
65 for (typename EdgeCostVector::const_iterator p = rank.begin(); |
|
66 p!=rank.end(); ++p ) { |
|
67 if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) { |
|
68 treemap.set(p->first, true); |
|
69 tot_cost += p->second; |
|
70 } |
|
71 else { |
|
72 treemap.set(p->first, false); |
|
73 } |
|
74 } |
|
75 return tot_cost; |
37 |
76 |
38 typedef typename Graph::NodeMap<int> NodeIntMap; |
77 } |
39 typedef typename Graph::NodeIt NodeIt; |
|
40 NodeIntMap comp_map(G, -1); |
|
41 UnionFind<NodeIt,NodeIntMap> uf(comp_map); |
|
42 |
78 |
43 EDouble tot_cost = 0; |
79 }; |
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 |
80 |
57 |
81 |
58 } //namespace hugo |
82 } //namespace hugo |
59 |
83 |
60 #endif //HUGO_KRUSKAL_H |
84 #endif //HUGO_KRUSKAL_H |