79 return tot_cost; |
79 return tot_cost; |
80 } |
80 } |
81 |
81 |
82 /* A work-around for running Kruskal with const-reference bool maps... */ |
82 /* A work-around for running Kruskal with const-reference bool maps... */ |
83 |
83 |
84 ///\bug What is this? Or why doesn't it work? |
84 /// Helper class for calling kruskal with "constant" output map. |
85 /// |
85 |
|
86 /// Helper class for calling kruskal with output maps constructed |
|
87 /// on-the-fly. |
|
88 /// |
|
89 /// A typical examle is the following call: |
|
90 /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>. |
|
91 /// Here, the third argument is a temporary object (which wraps around an |
|
92 /// iterator with a writable bool map interface), and thus by rules of C++ |
|
93 /// is a \c const object. To enable call like this exist this class and |
|
94 /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt> |
|
95 /// third argument. |
86 template<class Map> |
96 template<class Map> |
87 class NonConstMapWr { |
97 class NonConstMapWr { |
88 const Map &m; |
98 const Map &m; |
89 public: |
99 public: |
90 typedef typename Map::ValueType ValueType; |
100 typedef typename Map::ValueType ValueType; |
95 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } |
105 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } |
96 }; |
106 }; |
97 |
107 |
98 template <class GR, class IN, class OUT> |
108 template <class GR, class IN, class OUT> |
99 inline |
109 inline |
100 typename IN::ValueType |
110 typename IN::value_type::second_type |
101 kruskal(GR const& G, IN const& edges, |
111 kruskal(GR const& G, IN const& edges, OUT const& out_map) |
102 OUT const& out_map) |
|
103 { |
112 { |
104 NonConstMapWr<OUT> map_wr(out_map); |
113 NonConstMapWr<OUT> map_wr(out_map); |
105 return kruskal(G, edges, map_wr); |
114 return kruskal(G, edges, map_wr); |
106 } |
115 } |
107 |
116 |
182 { |
190 { |
183 return KruskalMapInput<GR,Map>(G,m); |
191 return KruskalMapInput<GR,Map>(G,m); |
184 } |
192 } |
185 |
193 |
186 |
194 |
187 /* ** ** Output-objects: simple writable bool maps** ** */ |
195 |
|
196 /* ** ** Output-objects: simple writable bool maps ** ** */ |
188 |
197 |
|
198 |
|
199 |
189 /// A writable bool-map that makes a sequence of "true" keys |
200 /// A writable bool-map that makes a sequence of "true" keys |
190 |
201 |
191 /// A writable bool-map that creates a sequence out of keys that receives |
202 /// A writable bool-map that creates a sequence out of keys that receives |
192 /// the value "true". |
203 /// the value "true". |
|
204 /// |
|
205 /// \sa makeKruskalSequenceOutput() |
|
206 /// |
|
207 /// Very often, when looking for a min cost spanning tree, we want as |
|
208 /// output a container containing the edges of the found tree. For this |
|
209 /// purpose exist this class that wraps around an STL iterator with a |
|
210 /// writable bool map interface. When a key gets value "true" this key |
|
211 /// is added to sequence pointed by the iterator. |
|
212 /// |
|
213 /// A typical usage: |
|
214 /// \code |
|
215 /// std::vector<Graph::Edge> v; |
|
216 /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v))); |
|
217 /// \endcode |
|
218 /// |
|
219 /// For the most common case, when the input is given by a simple edge |
|
220 /// map and the output is a sequence of the tree edges, a special |
|
221 /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut(). |
|
222 /// |
193 /// \warning Not a regular property map, as it doesn't know its KeyType |
223 /// \warning Not a regular property map, as it doesn't know its KeyType |
194 /// \bug Missing documentation. |
224 |
195 /// \todo This class may be of wider usage, therefore it could move to |
|
196 /// <tt>maps.h</tt> |
|
197 template<class Iterator> |
225 template<class Iterator> |
198 class SequenceOutput { |
226 class KruskalSequenceOutput { |
199 mutable Iterator it; |
227 mutable Iterator it; |
200 |
228 |
201 public: |
229 public: |
202 typedef bool ValueType; |
230 typedef bool ValueType; |
203 |
231 |
204 SequenceOutput(Iterator const &_it) : it(_it) {} |
232 KruskalSequenceOutput(Iterator const &_it) : it(_it) {} |
205 |
233 |
206 template<typename KeyType> |
234 template<typename KeyType> |
207 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } |
235 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } |
208 }; |
236 }; |
209 |
237 |
210 template<class Iterator> |
238 template<class Iterator> |
211 inline |
239 inline |
212 SequenceOutput<Iterator> |
240 KruskalSequenceOutput<Iterator> |
213 makeSequenceOutput(Iterator it) { |
241 makeKruskalSequenceOutput(Iterator it) { |
214 return SequenceOutput<Iterator>(it); |
242 return KruskalSequenceOutput<Iterator>(it); |
215 } |
243 } |
|
244 |
|
245 |
216 |
246 |
217 /* ** ** Wrapper funtions ** ** */ |
247 /* ** ** Wrapper funtions ** ** */ |
|
248 |
218 |
249 |
219 |
250 |
220 /// \brief Wrapper function to kruskal(). |
251 /// \brief Wrapper function to kruskal(). |
221 /// Input is from an edge map, output is a plain bool map. |
252 /// Input is from an edge map, output is a plain bool map. |
222 /// |
253 /// |
236 /// this will contain the found minimum cost spanning tree: the value of an |
267 /// this will contain the found minimum cost spanning tree: the value of an |
237 /// edge will be set to \c true if it belongs to the tree, otherwise it will |
268 /// edge will be set to \c true if it belongs to the tree, otherwise it will |
238 /// be set to \c false. The value of each edge will be set exactly once. |
269 /// be set to \c false. The value of each edge will be set exactly once. |
239 /// |
270 /// |
240 /// \return The cost of the found tree. |
271 /// \return The cost of the found tree. |
241 |
|
242 |
272 |
243 template <class GR, class IN, class RET> |
273 template <class GR, class IN, class RET> |
244 inline |
274 inline |
245 typename IN::ValueType |
275 typename IN::ValueType |
246 kruskalEdgeMap(GR const& G, |
276 kruskalEdgeMap(GR const& G, |
282 /// \endcode |
312 /// \endcode |
283 /// |
313 /// |
284 /// \return The cost of the found tree. |
314 /// \return The cost of the found tree. |
285 /// |
315 /// |
286 /// \bug its name does not follow the coding style. |
316 /// \bug its name does not follow the coding style. |
|
317 |
287 template <class GR, class IN, class RET> |
318 template <class GR, class IN, class RET> |
288 inline |
319 inline |
289 typename IN::ValueType |
320 typename IN::ValueType |
290 kruskalEdgeMap_IteratorOut(const GR& G, |
321 kruskalEdgeMap_IteratorOut(const GR& G, |
291 const IN& in, |
322 const IN& in, |
292 RET out) |
323 RET out) |
293 { |
324 { |
294 SequenceOutput<RET> _out(out); |
325 KruskalSequenceOutput<RET> _out(out); |
295 return kruskal(G, |
326 return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out); |
296 KruskalMapInput<GR,IN>(G, in), |
|
297 _out); |
|
298 } |
327 } |
299 |
328 |
300 /// @} |
329 /// @} |
301 |
330 |
302 } //namespace hugo |
331 } //namespace hugo |