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