110 /// third argument. |
110 /// third argument. |
111 template<class Map> |
111 template<class Map> |
112 class NonConstMapWr { |
112 class NonConstMapWr { |
113 const Map &m; |
113 const Map &m; |
114 public: |
114 public: |
115 typedef typename Map::ValueType ValueType; |
115 typedef typename Map::Value Value; |
116 |
116 |
117 NonConstMapWr(const Map &_m) : m(_m) {} |
117 NonConstMapWr(const Map &_m) : m(_m) {} |
118 |
118 |
119 template<class KeyType> |
119 template<class Key> |
120 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } |
120 void set(Key const& k, Value const &v) const { m.set(k,v); } |
121 }; |
121 }; |
122 |
122 |
123 template <class GR, class IN, class OUT> |
123 template <class GR, class IN, class OUT> |
124 inline |
124 inline |
125 typename IN::value_type::second_type |
125 typename IN::value_type::second_type |
148 ///computing the total cost of the tree). |
148 ///computing the total cost of the tree). |
149 /// |
149 /// |
150 template<class GR, class Map> |
150 template<class GR, class Map> |
151 class KruskalMapInput |
151 class KruskalMapInput |
152 : public std::vector< std::pair<typename GR::Edge, |
152 : public std::vector< std::pair<typename GR::Edge, |
153 typename Map::ValueType> > { |
153 typename Map::Value> > { |
154 |
154 |
155 public: |
155 public: |
156 typedef std::vector< std::pair<typename GR::Edge, |
156 typedef std::vector< std::pair<typename GR::Edge, |
157 typename Map::ValueType> > Parent; |
157 typename Map::Value> > Parent; |
158 typedef typename Parent::value_type value_type; |
158 typedef typename Parent::value_type value_type; |
159 |
159 |
160 private: |
160 private: |
161 class comparePair { |
161 class comparePair { |
162 public: |
162 public: |
233 /// |
233 /// |
234 /// For the most common case, when the input is given by a simple edge |
234 /// For the most common case, when the input is given by a simple edge |
235 /// map and the output is a sequence of the tree edges, a special |
235 /// map and the output is a sequence of the tree edges, a special |
236 /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut(). |
236 /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut(). |
237 /// |
237 /// |
238 /// \warning Not a regular property map, as it doesn't know its KeyType |
238 /// \warning Not a regular property map, as it doesn't know its Key |
239 |
239 |
240 template<class Iterator> |
240 template<class Iterator> |
241 class KruskalSequenceOutput { |
241 class KruskalSequenceOutput { |
242 mutable Iterator it; |
242 mutable Iterator it; |
243 |
243 |
244 public: |
244 public: |
245 typedef bool ValueType; |
245 typedef bool Value; |
246 |
246 |
247 KruskalSequenceOutput(Iterator const &_it) : it(_it) {} |
247 KruskalSequenceOutput(Iterator const &_it) : it(_it) {} |
248 |
248 |
249 template<typename KeyType> |
249 template<typename Key> |
250 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } |
250 void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} } |
251 }; |
251 }; |
252 |
252 |
253 template<class Iterator> |
253 template<class Iterator> |
254 inline |
254 inline |
255 KruskalSequenceOutput<Iterator> |
255 KruskalSequenceOutput<Iterator> |
285 /// |
285 /// |
286 /// \return The cost of the found tree. |
286 /// \return The cost of the found tree. |
287 |
287 |
288 template <class GR, class IN, class RET> |
288 template <class GR, class IN, class RET> |
289 inline |
289 inline |
290 typename IN::ValueType |
290 typename IN::Value |
291 kruskalEdgeMap(GR const& G, |
291 kruskalEdgeMap(GR const& G, |
292 IN const& in, |
292 IN const& in, |
293 RET &out) { |
293 RET &out) { |
294 return kruskal(G, |
294 return kruskal(G, |
295 KruskalMapInput<GR,IN>(G,in), |
295 KruskalMapInput<GR,IN>(G,in), |
330 /// |
330 /// |
331 /// \bug its name does not follow the coding style. |
331 /// \bug its name does not follow the coding style. |
332 |
332 |
333 template <class GR, class IN, class RET> |
333 template <class GR, class IN, class RET> |
334 inline |
334 inline |
335 typename IN::ValueType |
335 typename IN::Value |
336 kruskalEdgeMap_IteratorOut(const GR& G, |
336 kruskalEdgeMap_IteratorOut(const GR& G, |
337 const IN& in, |
337 const IN& in, |
338 RET out) |
338 RET out) |
339 { |
339 { |
340 KruskalSequenceOutput<RET> _out(out); |
340 KruskalSequenceOutput<RET> _out(out); |