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 |
10 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
11 template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap> |
11 typename EdgeCostMap::ValueType |
|
12 kruskal1(Graph const& G, EdgeCostMap const& edge_costs, |
|
13 RetEdgeBoolMap &ret_bool_map); |
|
14 |
|
15 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
|
16 typename EdgeCostMap::ValueType |
|
17 kruskal2(Graph const& G, EdgeCostMap const& edge_costs, |
|
18 RetIterator ret_iterator); |
|
19 |
|
20 // FIXME: ret_iterator nem lehet referencia!!! |
|
21 |
|
22 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap> |
|
23 typename EdgeCostPairVec::value_type::second_type |
|
24 kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, |
|
25 RetEdgeBoolMap &ret_bool_map); |
|
26 |
|
27 template <typename Graph, typename EdgeCostPairVec, typename RetIterator> |
|
28 typename EdgeCostPairVec::value_type::second_type |
|
29 kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, |
|
30 RetIterator &ret_iterator); |
|
31 |
|
32 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap> |
|
33 int |
|
34 kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec, |
|
35 RetEdgeBoolMap &ret_bool_map); |
|
36 |
|
37 template <typename Graph, typename EdgePairVec, typename RetIterator> |
|
38 int |
|
39 kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec, |
|
40 RetIterator &ret_iterator); |
|
41 |
|
42 |
|
43 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap, |
|
44 typename RetIterator> |
|
45 typename EdgeCostMap::ValueType |
|
46 kruskal7(Graph const& G, EdgeCostMap const& edge_costs, |
|
47 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); |
|
48 |
|
49 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap, |
|
50 typename RetIterator> |
|
51 typename EdgeCostPairVec::value_type::second_type |
|
52 kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, |
|
53 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); |
|
54 |
|
55 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap, |
|
56 typename RetIterator> |
|
57 int |
|
58 kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec, |
|
59 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); |
|
60 |
|
61 |
|
62 |
|
63 |
|
64 template <typename Graph, typename InputEdgeOrder, typename OutputObserver> |
12 class MinCostTreeKruskal |
65 class MinCostTreeKruskal |
13 { |
66 { |
14 |
67 |
15 typedef typename Graph::EdgeIt EdgeIt; |
68 typedef typename Graph::EdgeIt EdgeIt; |
16 typedef typename Graph::Edge Edge; |
69 typedef typename Graph::Edge Edge; |
17 |
70 |
18 public: |
71 public: |
19 typedef typename EdgeCostMap::ValueType EdgeCost; |
72 typedef typename InputEdgeOrder::ValueType EdgeCost; |
20 typedef std::pair<Edge, EdgeCost> EdgeCostPair; |
|
21 typedef std::vector<EdgeCostPair> EdgeCostVector; |
|
22 |
73 |
23 private: |
74 private: |
24 Graph const &G; |
75 Graph const &G; |
25 EdgeCostMap const &costmap; |
76 InputEdgeOrder const &edges; |
26 EdgeBoolMap& treemap; |
77 OutputObserver &out_obs; |
27 |
78 |
28 //template <typename EdgeCostPair> |
79 public: |
29 class comparePair { |
80 |
30 public: |
81 |
31 bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) { |
82 MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, |
32 return a.second < b.second; |
83 OutputObserver& _out_obs) : |
33 } |
84 G(_G), edges(_edges), out_obs(_out_obs) {} |
34 }; |
|
35 |
|
36 public: |
|
37 |
|
38 |
|
39 MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap, |
|
40 EdgeBoolMap& _treemap) : G(_G), costmap(_costmap), |
|
41 treemap(_treemap) {} |
|
42 |
85 |
43 |
86 |
44 EdgeCost run() |
87 EdgeCost run() |
45 { |
|
46 EdgeCostVector rank; |
|
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); |
|
54 |
|
55 } |
|
56 |
|
57 EdgeCost run(EdgeCostVector const &rank) |
|
58 { |
88 { |
59 typedef typename Graph::NodeMap<int> NodeIntMap; |
89 typedef typename Graph::NodeMap<int> NodeIntMap; |
60 typedef typename Graph::Node Node; |
90 typedef typename Graph::Node Node; |
61 NodeIntMap comp_map(G, -1); |
91 NodeIntMap comp_map(G, -1); |
62 UnionFind<Node,NodeIntMap> uf(comp_map); |
92 UnionFind<Node,NodeIntMap> uf(comp_map); |
63 |
93 |
64 EdgeCost tot_cost = 0; |
94 EdgeCost tot_cost = 0; |
65 for (typename EdgeCostVector::const_iterator p = rank.begin(); |
95 for (typename InputEdgeOrder::const_iterator p = edges.begin(); |
66 p!=rank.end(); ++p ) { |
96 p!=edges.end(); ++p ) { |
67 if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) { |
97 if ( uf.joinComponents(G.head(edges.first(p)), |
68 treemap.set(p->first, true); |
98 G.tail(edges.first(p))) ) { |
69 tot_cost += p->second; |
99 out_obs.setTrue(edges.first(p)); |
|
100 tot_cost += edges.second(p); |
70 } |
101 } |
71 else { |
102 else { |
72 treemap.set(p->first, false); |
103 out_obs.setFalse(edges.first(p)); |
73 } |
104 } |
74 } |
105 } |
75 return tot_cost; |
106 return tot_cost; |
76 |
107 } |
77 } |
108 |
78 |
109 }; |
79 }; |
110 |
|
111 |
|
112 /* ** ** Output-objektumok (Observerek (?)) ** ** */ |
|
113 |
|
114 template <typename BoolMap> |
|
115 class BoolMapOutput { |
|
116 BoolMap &bm; |
|
117 typedef typename BoolMap::KeyType KeyType; |
|
118 |
|
119 public: |
|
120 BoolMapOutput(BoolMap &_bm) : bm(_bm) {} |
|
121 |
|
122 void setTrue(KeyType const& k) { bm.set(k, true); } |
|
123 void setFalse(KeyType const& k) { bm.set(k, false); } |
|
124 }; |
|
125 |
|
126 template <typename Iterator> |
|
127 class SequenceOutput { |
|
128 Iterator ⁢ |
|
129 |
|
130 public: |
|
131 SequenceOutput(Iterator &_it) : it(_it) {} |
|
132 |
|
133 template<typename KeyType> |
|
134 void setTrue(KeyType const& k) { *it=k; ++it; } |
|
135 template<typename KeyType> |
|
136 void setFalse(KeyType const& k) {} |
|
137 }; |
|
138 |
|
139 template <typename BoolMap, typename Iterator> |
|
140 class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> { |
|
141 typedef BoolMapOutput<BoolMap> BMO; |
|
142 typedef SequenceOutput<Iterator> SO; |
|
143 public: |
|
144 CombinedOutput(BoolMap &_bm, Iterator &_it) : |
|
145 BMO(_bm), SO(_it) {} |
|
146 |
|
147 template<typename KeyType> |
|
148 void setTrue(KeyType const& k) { |
|
149 BMO::setTrue(k); |
|
150 SO::setTrue(k); |
|
151 } |
|
152 template<typename KeyType> |
|
153 void setFalse(KeyType const& k) { |
|
154 BMO::setFalse(k); |
|
155 SO::setFalse(k); |
|
156 } |
|
157 }; |
|
158 |
|
159 |
|
160 /* ** ** InputSource -ok ** ** */ |
|
161 |
|
162 template<typename Key, typename Val> |
|
163 class PairVec : public std::vector< std::pair<Key,Val> > { |
|
164 |
|
165 public: |
|
166 typedef std::vector< std::pair<Key,Val> > Parent; |
|
167 typedef Key KeyType; |
|
168 typedef Val ValueType; |
|
169 typedef std::pair<Key,Val> PairType; |
|
170 |
|
171 typedef typename Parent::iterator iterator; |
|
172 typedef typename Parent::const_iterator const_iterator; |
|
173 |
|
174 |
|
175 private: |
|
176 |
|
177 class comparePair { |
|
178 public: |
|
179 bool operator()(PairType const& a, PairType const& b) { |
|
180 return a.second < b.second; |
|
181 } |
|
182 }; |
|
183 |
|
184 public: |
|
185 |
|
186 // FIXME: kell ez? |
|
187 // PairVec(Parent const& p) : Parent(p) {} |
|
188 |
|
189 void sort() { |
|
190 std::sort(begin(), end(), comparePair()); |
|
191 } |
|
192 |
|
193 // FIXME: nem nagyon illik ez ide... |
|
194 template<typename Graph, typename Map> |
|
195 void readGraphEdgeMap(Graph const& G, Map const& m) { |
|
196 typedef typename Graph::EdgeIt EdgeIt; |
|
197 |
|
198 clear(); |
|
199 for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
|
200 push_back(make_pair(e, m[e])); |
|
201 } |
|
202 |
|
203 sort(); |
|
204 } |
|
205 |
|
206 int alma() { return 5; /* FIXME */ } |
|
207 |
|
208 Key const& first(const_iterator i) const { return i->first; } |
|
209 Key& first(iterator i) { return i->first; } |
|
210 |
|
211 Val const& second(const_iterator i) const { return i->second; } |
|
212 Val& second(iterator i) { return i->second; } |
|
213 }; |
|
214 |
|
215 /* ** ** Wrapper fuggvenyek ** ** */ |
|
216 |
|
217 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
|
218 typename EdgeCostMap::ValueType |
|
219 kruskal1(Graph const& G, EdgeCostMap const& edge_costs, |
|
220 RetEdgeBoolMap &ret_bool_map) { |
|
221 typedef BoolMapOutput<RetEdgeBoolMap> OutObs; |
|
222 OutObs out(ret_bool_map); |
|
223 |
|
224 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> |
|
225 InputVec; |
|
226 InputVec iv; |
|
227 iv.readGraphEdgeMap(G, edge_costs); |
|
228 |
|
229 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out); |
|
230 return mctk.run(); |
|
231 } |
|
232 |
|
233 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
|
234 typename EdgeCostMap::ValueType |
|
235 kruskal2(Graph const& G, EdgeCostMap const& edge_costs, |
|
236 RetIterator ret_iterator) { |
|
237 typedef SequenceOutput<RetIterator> OutObs; |
|
238 OutObs out(ret_iterator); |
|
239 |
|
240 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> |
|
241 InputVec; |
|
242 InputVec iv; |
|
243 iv.readGraphEdgeMap(G, edge_costs); |
|
244 |
|
245 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out); |
|
246 return mctk.run(); |
|
247 } |
80 |
248 |
81 |
249 |
82 } //namespace hugo |
250 } //namespace hugo |
83 |
251 |
84 #endif //HUGO_KRUSKAL_H |
252 #endif //HUGO_KRUSKAL_H |