115 /// Kruskal input source. |
115 /// Kruskal input source. |
116 |
116 |
117 /// Kruskal input source. |
117 /// Kruskal input source. |
118 /// |
118 /// |
119 template<typename Graph, typename Map> |
119 template<typename Graph, typename Map> |
120 class KruskalPairVec |
120 class KruskalMapInput |
121 : public std::vector< std::pair<typename Graph::Edge, |
121 : public std::vector< std::pair<typename Graph::Edge, |
122 typename Map::ValueType> > { |
122 typename Map::ValueType> > { |
123 |
123 |
124 public: |
124 public: |
125 typedef std::vector< std::pair<typename Graph::Edge, |
125 typedef std::vector< std::pair<typename Graph::Edge, |
141 }; |
141 }; |
142 |
142 |
143 public: |
143 public: |
144 |
144 |
145 // FIXME: kell ez? |
145 // FIXME: kell ez? |
146 // KruskalPairVec(Parent const& p) : Parent(p) {} |
146 // KruskalMapInput(Parent const& p) : Parent(p) {} |
147 |
147 |
148 void sort() { |
148 void sort() { |
149 std::sort(this->begin(), this->end(), comparePair()); |
149 std::sort(this->begin(), this->end(), comparePair()); |
150 } |
150 } |
151 |
151 |
152 // FIXME: nem nagyon illik ez ide... |
152 // FIXME: nem nagyon illik ez ide... |
153 KruskalPairVec(Graph const& G, Map const& m) { |
153 KruskalMapInput(Graph const& G, Map const& m) { |
154 typedef typename Graph::EdgeIt EdgeIt; |
154 typedef typename Graph::EdgeIt EdgeIt; |
155 |
155 |
156 this->clear(); |
156 this->clear(); |
157 for(EdgeIt e(G);G.valid(e);G.next(e)) { |
157 for(EdgeIt e(G);G.valid(e);G.next(e)) { |
158 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
158 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
167 // Val const& second(const_iterator i) const { return i->second; } |
167 // Val const& second(const_iterator i) const { return i->second; } |
168 // Val& second(iterator i) { return i->second; } |
168 // Val& second(iterator i) { return i->second; } |
169 }; |
169 }; |
170 |
170 |
171 |
171 |
172 // template <typename Map> |
172 // template<typename Graph, typename Map> |
173 // class KruskalMapVec : public std::vector<typename Map::KeyType> { |
173 // class KruskalMapVec { |
174 // public: |
174 // public: |
175 |
175 |
176 // typedef typename Map::KeyType KeyType; |
176 // typedef std::pair<typename Map::KeyType, Map::ValueType> value_type; |
177 // typedef typename Map::ValueType ValueType; |
177 |
178 |
178 // typedef std::vector<KeyType> Container; |
179 // typedef typename std::vector<KeyType> Parent; |
179 // Container container; |
180 // typedef typename Parent::iterator iterator; |
180 // std::vector<typename Map::KeyType> container |
181 // typedef typename Parent::const_iterator const_iterator; |
181 // const Map &m; |
182 |
182 |
|
183 |
|
184 // class iterator |
|
185 // { |
|
186 // Container::iterator i; |
|
187 // public: |
|
188 // iterator &operator ++() {++i;return *this;} |
|
189 // valuetype operator *() {return value_type(container(i),m[container(i)]);} |
|
190 // bool operator==(iterator b) {return i==b.i;} |
|
191 // iterator() {} |
|
192 // iterator(Container::iterator _i) i(_i) {} |
|
193 // }; |
|
194 // class const_iterator |
|
195 // { |
|
196 // Container::const_iterator i; |
|
197 // public: |
|
198 // iterator &operator ++() {++i;return *this;} |
|
199 // valuetype operator *() {return value_type(container(i),m[container(i)]);} |
|
200 // bool operator==(iterator b) {return i==b.i;} |
|
201 // const_iterator() {} |
|
202 // const_iterator(Container::iterator _i) i(_i) {} |
|
203 // }; |
|
204 |
|
205 // iterator begin() { return iterator(container.begin());} |
|
206 // const_iterator begin() const { return iterator(container.begin());} |
|
207 // iterator end() { return iterator(container.end());} |
|
208 // const_iterator end() const { return iterator(container.end());} |
|
209 |
183 // private: |
210 // private: |
184 |
211 |
185 // const Map &m; |
|
186 |
|
187 // class compareKeys { |
212 // class compareKeys { |
188 // const Map &m; |
213 // const Map &m; |
189 // public: |
214 // public: |
190 // compareKeys(Map const &_m) : m(_m) {} |
215 // compareKeys(Map const &_m) : m(_m) {} |
191 // bool operator()(KeyType const& a, KeyType const& b) { |
216 // bool operator()(KeyType const& a, KeyType const& b) { |
219 |
244 |
220 // ValueType const& second(const_iterator i) const { return m[*i]; } |
245 // ValueType const& second(const_iterator i) const { return m[*i]; } |
221 // ValueType& second(iterator i) { return m[*i]; } |
246 // ValueType& second(iterator i) { return m[*i]; } |
222 // }; |
247 // }; |
223 |
248 |
|
249 |
224 /* ** ** Wrapper fuggvenyek ** ** */ |
250 /* ** ** Wrapper fuggvenyek ** ** */ |
225 |
251 |
226 |
252 |
227 /// \brief Wrapper to Kruskal(). |
253 /// \brief Wrapper to Kruskal(). |
228 /// Input is from an EdgeMap, output is a plain boolmap. |
254 /// Input is from an EdgeMap, output is a plain boolmap. |
234 typename EdgeCostMap::ValueType |
260 typename EdgeCostMap::ValueType |
235 kruskalEdgeMap(Graph const& G, |
261 kruskalEdgeMap(Graph const& G, |
236 EdgeCostMap const& edge_costs, |
262 EdgeCostMap const& edge_costs, |
237 RetEdgeBoolMap &ret_bool_map) { |
263 RetEdgeBoolMap &ret_bool_map) { |
238 |
264 |
239 typedef KruskalPairVec<Graph,EdgeCostMap> InputVec; |
265 typedef KruskalMapInput<Graph,EdgeCostMap> InputVec; |
240 |
266 |
241 InputVec iv(G, edge_costs); |
267 InputVec iv(G, edge_costs); |
242 return kruskal(G, iv, ret_bool_map); |
268 return kruskal(G, iv, ret_bool_map); |
243 } |
269 } |
244 |
270 |
258 typedef typename EdgeCostMap::ValueType ValueType; |
284 typedef typename EdgeCostMap::ValueType ValueType; |
259 |
285 |
260 typedef SequenceOutput<RetIterator> OutMap; |
286 typedef SequenceOutput<RetIterator> OutMap; |
261 OutMap out(ret_iterator); |
287 OutMap out(ret_iterator); |
262 |
288 |
263 typedef KruskalPairVec<Graph, EdgeCostMap> InputVec; |
289 typedef KruskalMapInput<Graph, EdgeCostMap> InputVec; |
264 |
290 |
265 InputVec iv(G, edge_costs); |
291 InputVec iv(G, edge_costs); |
266 |
292 |
267 return kruskal(G, iv, out); |
293 return kruskal(G, iv, out); |
268 } |
294 } |