32 ///Kruskal's algorithm to compute a minimum cost tree. |
37 ///Kruskal's algorithm to compute a minimum cost tree. |
33 /// |
38 /// |
34 |
39 |
35 namespace lemon { |
40 namespace lemon { |
36 |
41 |
37 /// \addtogroup spantree |
42 namespace _kruskal_bits { |
38 /// @{ |
43 |
39 |
44 template <typename Map, typename Comp> |
40 /// Kruskal's algorithm to find a minimum cost tree of a graph. |
45 struct MappedComp { |
41 |
46 |
|
47 typedef typename Map::Key Key; |
|
48 |
|
49 const Map& map; |
|
50 Comp comp; |
|
51 |
|
52 MappedComp(const Map& _map) |
|
53 : map(_map), comp() {} |
|
54 |
|
55 bool operator()(const Key& left, const Key& right) { |
|
56 return comp(map[left], map[right]); |
|
57 } |
|
58 |
|
59 }; |
|
60 |
|
61 } |
|
62 |
|
63 /// \ingroup spantree |
|
64 /// |
|
65 /// \brief Default traits class of Kruskal class. |
|
66 /// |
|
67 /// Default traits class of Kruskal class. |
|
68 /// \param _UGraph Undirected graph type. |
|
69 /// \param _CostMap Type of cost map. |
|
70 template <typename _UGraph, typename _CostMap> |
|
71 struct KruskalDefaultTraits{ |
|
72 |
|
73 /// \brief The graph type the algorithm runs on. |
|
74 typedef _UGraph UGraph; |
|
75 |
|
76 /// \brief The type of the map that stores the edge costs. |
|
77 /// |
|
78 /// The type of the map that stores the edge costs. |
|
79 /// It must meet the \ref concepts::ReadMap "ReadMap" concept. |
|
80 typedef _CostMap CostMap; |
|
81 |
|
82 /// \brief The type of the cost of the edges. |
|
83 typedef typename _CostMap::Value Value; |
|
84 |
|
85 /// \brief The type of the map that stores whether an edge is in the |
|
86 /// spanning tree or not. |
|
87 /// |
|
88 /// The type of the map that stores whether an edge is in the |
|
89 /// spanning tree or not. |
|
90 typedef typename _UGraph::template UEdgeMap<bool> TreeMap; |
|
91 |
|
92 /// \brief Instantiates a TreeMap. |
|
93 /// |
|
94 /// This function instantiates a \ref TreeMap. |
|
95 /// |
|
96 /// The first parameter is the graph, to which |
|
97 /// we would like to define the \ref TreeMap |
|
98 static TreeMap *createTreeMap(const _UGraph& graph){ |
|
99 return new TreeMap(graph); |
|
100 } |
|
101 |
|
102 template <typename Iterator> |
|
103 static void sort(Iterator begin, Iterator end, const CostMap& cost) { |
|
104 _kruskal_bits::MappedComp<CostMap, std::less<Value> > comp(cost); |
|
105 std::sort(begin, end, comp); |
|
106 } |
|
107 |
|
108 }; |
|
109 |
|
110 /// \brief Kruskal's algorithm to find a minimum cost tree of a graph. |
|
111 /// |
|
112 /// This class implements Kruskal's algorithm to find a minimum cost |
|
113 /// spanning tree. The |
|
114 /// |
|
115 /// \param _UGraph Undirected graph type. |
|
116 /// \param _CostMap Type of cost map. |
|
117 template <typename _UGraph, typename _CostMap, |
|
118 typename _Traits = KruskalDefaultTraits<_UGraph, _CostMap> > |
|
119 class Kruskal { |
|
120 public: |
|
121 |
|
122 typedef _Traits Traits; |
|
123 |
|
124 typedef typename _Traits::UGraph UGraph; |
|
125 typedef typename _Traits::CostMap CostMap; |
|
126 |
|
127 typedef typename _Traits::TreeMap TreeMap; |
|
128 |
|
129 typedef typename _Traits::Value Value; |
|
130 |
|
131 template <typename Comp> |
|
132 struct DefSortCompareTraits : public Traits { |
|
133 template <typename Iterator> |
|
134 static void sort(Iterator begin, Iterator end, const CostMap& cost) { |
|
135 _kruskal_bits::MappedComp<CostMap, Comp> comp(cost, Comp()); |
|
136 std::sort(begin, end, comp); |
|
137 } |
|
138 }; |
|
139 |
|
140 /// \brief \ref named-templ-param "Named parameter" for setting the |
|
141 /// comparator object of the standard sort |
|
142 /// |
|
143 /// \ref named-templ-param "Named parameter" for setting the |
|
144 /// comparator object of the standard sort |
|
145 template <typename Comp> |
|
146 struct DefSortCompare |
|
147 : public Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > { |
|
148 typedef Kruskal<UGraph, CostMap, DefSortCompareTraits<Comp> > Create; |
|
149 }; |
|
150 |
|
151 struct DefRadixSortTraits : public Traits { |
|
152 template <typename Iterator> |
|
153 static void sort(Iterator begin, Iterator end, const CostMap& cost) { |
|
154 radixSort(begin, end, cost); |
|
155 } |
|
156 }; |
|
157 |
|
158 /// \brief \ref named-templ-param "Named parameter" for setting the |
|
159 /// sort function to radix sort |
|
160 /// |
|
161 /// \brief \ref named-templ-param "Named parameter" for setting the |
|
162 /// sort function to radix sort. The value type of the cost map should |
|
163 /// be integral, of course. |
|
164 struct DefRadixSort |
|
165 : public Kruskal<UGraph, CostMap, DefRadixSortTraits> { |
|
166 typedef Kruskal<UGraph, CostMap, DefRadixSortTraits> Create; |
|
167 }; |
|
168 |
|
169 template <class TM> |
|
170 struct DefTreeMapTraits : public Traits { |
|
171 typedef TM TreeMap; |
|
172 static TreeMap *createTreeMap(const UGraph &) { |
|
173 throw UninitializedParameter(); |
|
174 } |
|
175 }; |
|
176 |
|
177 /// \brief \ref named-templ-param "Named parameter" for setting |
|
178 /// TreeMap |
|
179 /// |
|
180 /// \ref named-templ-param "Named parameter" for setting TreeMap |
|
181 /// |
|
182 template <class TM> |
|
183 struct DefTreeMap |
|
184 : public Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > { |
|
185 typedef Kruskal< UGraph, CostMap, DefTreeMapTraits<TM> > Create; |
|
186 }; |
|
187 |
|
188 |
|
189 private: |
|
190 |
|
191 typedef typename UGraph::Node Node; |
|
192 typedef typename UGraph::NodeIt NodeIt; |
|
193 |
|
194 typedef typename UGraph::UEdge UEdge; |
|
195 typedef typename UGraph::UEdgeIt UEdgeIt; |
|
196 |
|
197 const UGraph& graph; |
|
198 const CostMap& cost; |
|
199 |
|
200 std::vector<UEdge> edges; |
|
201 |
|
202 typedef typename UGraph::template NodeMap<int> UfIndex; |
|
203 typedef UnionFind<UfIndex> Uf; |
|
204 UfIndex *ufi; |
|
205 Uf *uf; |
|
206 |
|
207 int index; |
|
208 |
|
209 void initStructures() { |
|
210 if (!_tree) { |
|
211 _tree = Traits::createTreeMap(graph); |
|
212 local_tree = true; |
|
213 } |
|
214 if (!uf) { |
|
215 ufi = new typename UGraph::template NodeMap<int>(graph); |
|
216 uf = new UnionFind<typename UGraph::template NodeMap<int> >(*ufi); |
|
217 } |
|
218 } |
|
219 |
|
220 void initUnionFind() { |
|
221 uf->clear(); |
|
222 for (NodeIt it(graph); it != INVALID; ++it) { |
|
223 uf->insert(it); |
|
224 } |
|
225 } |
|
226 |
|
227 bool local_tree; |
|
228 TreeMap* _tree; |
|
229 |
|
230 public: |
|
231 |
|
232 /// \brief Constructor |
|
233 /// |
|
234 /// Constructor of the algorithm. |
|
235 Kruskal(const UGraph& _graph, const CostMap& _cost) |
|
236 : graph(_graph), cost(_cost), |
|
237 ufi(0), uf(0), local_tree(false), _tree(0) {} |
|
238 |
|
239 /// \brief Destructor |
|
240 /// |
|
241 /// Destructor |
|
242 ~Kruskal() { |
|
243 if (local_tree) { |
|
244 delete _tree; |
|
245 } |
|
246 if (uf) { |
|
247 delete uf; |
|
248 delete ufi; |
|
249 } |
|
250 } |
|
251 |
|
252 /// \brief Sets the map storing the tree edges. |
|
253 /// |
|
254 /// Sets the map storing the tree edges. |
|
255 /// If you don't use this function before calling \ref run(), |
|
256 /// it will allocate one. The destuctor deallocates this |
|
257 /// automatically allocated map, of course. |
|
258 /// \return \c *this </tt> |
|
259 Kruskal& treeMap(TreeMap &m){ |
|
260 if (local_tree) { |
|
261 delete _tree; |
|
262 local_tree = false; |
|
263 } |
|
264 _tree = &m; |
|
265 return *this; |
|
266 } |
|
267 |
|
268 /// \brief Initialize the algorithm |
|
269 /// |
|
270 /// This member function initializes the unionfind data structure |
|
271 /// and sorts the edges into ascending order |
|
272 void init() { |
|
273 initStructures(); |
|
274 initUnionFind(); |
|
275 for (UEdgeIt e(graph); e != INVALID; ++e) { |
|
276 edges.push_back(e); |
|
277 _tree->set(e, false); |
|
278 } |
|
279 Traits::sort(edges.begin(), edges.end(), cost); |
|
280 index = 0; |
|
281 } |
|
282 |
|
283 |
|
284 /// \brief Initialize the algorithm |
|
285 /// |
|
286 /// This member function initializes the unionfind data structure |
|
287 /// and sets the edge order to the given sequence. The given |
|
288 /// sequence should be a valid STL range of undirected edges. |
|
289 template <typename Iterator> |
|
290 void initPresorted(Iterator begin, Iterator end) { |
|
291 initStructures(); |
|
292 initUnionFind(); |
|
293 edges.clear(); |
|
294 std::copy(begin, end, std::back_inserter(edges)); |
|
295 index = 0; |
|
296 } |
|
297 |
|
298 /// \brief Initialize the algorithm |
|
299 /// |
|
300 /// This member function initializes the unionfind data structure |
|
301 /// and sets the edge order to the given sequence. The given |
|
302 /// sequence should be a valid STL range of undirected edges. |
|
303 void reinit() { |
|
304 initStructures(); |
|
305 initUnionFind(); |
|
306 for (UEdgeIt e(graph); e != INVALID; ++e) { |
|
307 _tree->set(e, false); |
|
308 } |
|
309 index = 0; |
|
310 } |
|
311 |
|
312 |
|
313 /// \brief Executes the algorithm. |
|
314 /// |
|
315 /// Executes the algorithm. |
|
316 /// |
|
317 /// \pre init() must be called before using this function. |
|
318 /// |
|
319 /// This method runs the %Kruskal algorithm. |
|
320 void start() { |
|
321 while (index < int(edges.size())) { |
|
322 if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) { |
|
323 _tree->set(edges[index], true); |
|
324 } |
|
325 ++index; |
|
326 } |
|
327 } |
|
328 |
|
329 /// \brief Runs the prim algorithm until it find a new tree edge |
|
330 /// |
|
331 /// Runs the prim algorithm until it find a new tree edge. If it |
|
332 /// does not next tree edge in the sequence it gives back \c INVALID. |
|
333 UEdge findNextTreeEdge() { |
|
334 while (index < int(edges.size())) { |
|
335 if (uf->join(graph.target(edges[index]), graph.source(edges[index]))) { |
|
336 _tree->set(edges[index], true); |
|
337 return edges[index++]; |
|
338 } |
|
339 ++index; |
|
340 } |
|
341 return INVALID; |
|
342 } |
|
343 |
|
344 /// \brief Processes the next edge in the sequence |
|
345 /// |
|
346 /// Processes the next edge in the sequence. |
|
347 /// |
|
348 /// \return The prcocessed edge. |
|
349 /// |
|
350 /// \warning The sequence must not be empty! |
|
351 UEdge processNextEdge() { |
|
352 UEdge edge = edges[index++]; |
|
353 processEdge(edge); |
|
354 return edge; |
|
355 } |
|
356 |
|
357 /// \brief Processes an arbitrary edge |
|
358 /// |
|
359 /// Processes the next edge in the sequence. |
|
360 /// |
|
361 /// \return True when the edge is a tree edge. |
|
362 bool processEdge(const UEdge& edge) { |
|
363 if (uf->join(graph.target(edge), graph.source(edge))) { |
|
364 _tree->set(edge, true); |
|
365 return true; |
|
366 } else { |
|
367 return false; |
|
368 } |
|
369 } |
|
370 |
|
371 /// \brief Returns \c false if there are edge to be processed in |
|
372 /// sequence |
|
373 /// |
|
374 /// Returns \c false if there are nodes to be processed in the |
|
375 /// sequence |
|
376 bool emptyQueue() { |
|
377 return index == int(edges.size()); |
|
378 } |
|
379 |
|
380 /// \brief Returns the next edge to be processed |
|
381 /// |
|
382 /// Returns the next edge to be processed |
|
383 /// |
|
384 UEdge nextEdge() const { |
|
385 return edges[index]; |
|
386 } |
|
387 |
|
388 /// \brief Runs %Kruskal algorithm. |
|
389 /// |
|
390 /// This method runs the %Kruskal algorithm in order to compute the |
|
391 /// minimum spanning tree (or minimum spanning forest). The |
|
392 /// method also works on graphs that has more than one components. |
|
393 /// In this case it computes the minimum spanning forest. |
|
394 void run() { |
|
395 init(); |
|
396 start(); |
|
397 } |
|
398 |
|
399 /// \brief Returns a reference to the tree edges map |
|
400 /// |
|
401 /// Returns a reference to the TreeEdgeMap of the edges of the |
|
402 /// minimum spanning tree. The value of the map is \c true only if |
|
403 /// the edge is in the minimum spanning tree. |
|
404 /// |
|
405 const TreeMap &treeMap() const { return *_tree;} |
|
406 |
|
407 /// \brief Returns the total cost of the tree |
|
408 /// |
|
409 /// Returns the total cost of the tree |
|
410 Value treeValue() const { |
|
411 Value value = 0; |
|
412 for (UEdgeIt it(graph); it != INVALID; ++it) { |
|
413 if ((*_tree)[it]) { |
|
414 value += cost[it]; |
|
415 } |
|
416 } |
|
417 return value; |
|
418 } |
|
419 |
|
420 /// \brief Returns true when the given edge is tree edge |
|
421 /// |
|
422 /// Returns true when the given edge is tree edge |
|
423 bool tree(UEdge e) const { |
|
424 return (*_tree)[e]; |
|
425 } |
|
426 |
|
427 |
|
428 }; |
|
429 |
|
430 |
|
431 namespace _kruskal_bits { |
|
432 |
|
433 template <typename Graph, typename In, typename Out> |
|
434 typename In::value_type::second_type |
|
435 kruskal(const Graph& graph, const In& in, Out& out) { |
|
436 typedef typename In::value_type::second_type Value; |
|
437 typedef typename Graph::template NodeMap<int> IndexMap; |
|
438 typedef typename Graph::Node Node; |
|
439 |
|
440 IndexMap index(graph); |
|
441 UnionFind<IndexMap> uf(index); |
|
442 for (typename Graph::NodeIt it(graph); it != INVALID; ++it) { |
|
443 uf.insert(it); |
|
444 } |
|
445 |
|
446 Value tree_value = 0; |
|
447 for (typename In::const_iterator it = in.begin(); it != in.end(); ++it) { |
|
448 if (uf.join(graph.target(it->first),graph.source(it->first))) { |
|
449 out.set(it->first, true); |
|
450 tree_value += it->second; |
|
451 } |
|
452 else { |
|
453 out.set(it->first, false); |
|
454 } |
|
455 } |
|
456 return tree_value; |
|
457 } |
|
458 |
|
459 |
|
460 template <typename Sequence> |
|
461 struct PairComp { |
|
462 typedef typename Sequence::value_type Value; |
|
463 bool operator()(const Value& left, const Value& right) { |
|
464 return left.second < right.second; |
|
465 } |
|
466 }; |
|
467 |
|
468 template <typename In, typename Enable = void> |
|
469 struct SequenceInputIndicator { |
|
470 static const bool value = false; |
|
471 }; |
|
472 |
|
473 template <typename In> |
|
474 struct SequenceInputIndicator<In, |
|
475 typename exists<typename In::value_type::first_type>::type> { |
|
476 static const bool value = true; |
|
477 }; |
|
478 |
|
479 template <typename In, typename Enable = void> |
|
480 struct MapInputIndicator { |
|
481 static const bool value = false; |
|
482 }; |
|
483 |
|
484 template <typename In> |
|
485 struct MapInputIndicator<In, |
|
486 typename exists<typename In::Value>::type> { |
|
487 static const bool value = true; |
|
488 }; |
|
489 |
|
490 template <typename In, typename Enable = void> |
|
491 struct SequenceOutputIndicator { |
|
492 static const bool value = false; |
|
493 }; |
|
494 |
|
495 template <typename Out> |
|
496 struct SequenceOutputIndicator<Out, |
|
497 typename exists<typename Out::value_type>::type> { |
|
498 static const bool value = true; |
|
499 }; |
|
500 |
|
501 template <typename Out, typename Enable = void> |
|
502 struct MapOutputIndicator { |
|
503 static const bool value = false; |
|
504 }; |
|
505 |
|
506 template <typename Out> |
|
507 struct MapOutputIndicator<Out, |
|
508 typename exists<typename Out::Value>::type> { |
|
509 static const bool value = true; |
|
510 }; |
|
511 |
|
512 template <typename In, typename InEnable = void> |
|
513 struct KruskalValueSelector {}; |
|
514 |
|
515 template <typename In> |
|
516 struct KruskalValueSelector<In, |
|
517 typename enable_if<SequenceInputIndicator<In>, void>::type> |
|
518 { |
|
519 typedef typename In::value_type::second_type Value; |
|
520 }; |
|
521 |
|
522 template <typename In> |
|
523 struct KruskalValueSelector<In, |
|
524 typename enable_if<MapInputIndicator<In>, void>::type> |
|
525 { |
|
526 typedef typename In::Value Value; |
|
527 }; |
|
528 |
|
529 template <typename Graph, typename In, typename Out, |
|
530 typename InEnable = void> |
|
531 struct KruskalInputSelector {}; |
|
532 |
|
533 template <typename Graph, typename In, typename Out, |
|
534 typename InEnable = void> |
|
535 struct KruskalOutputSelector {}; |
|
536 |
|
537 template <typename Graph, typename In, typename Out> |
|
538 struct KruskalInputSelector<Graph, In, Out, |
|
539 typename enable_if<SequenceInputIndicator<In>, void>::type > |
|
540 { |
|
541 typedef typename In::value_type::second_type Value; |
|
542 |
|
543 static Value kruskal(const Graph& graph, const In& in, Out& out) { |
|
544 return KruskalOutputSelector<Graph, In, Out>:: |
|
545 kruskal(graph, in, out); |
|
546 } |
|
547 |
|
548 }; |
|
549 |
|
550 template <typename Graph, typename In, typename Out> |
|
551 struct KruskalInputSelector<Graph, In, Out, |
|
552 typename enable_if<MapInputIndicator<In>, void>::type > |
|
553 { |
|
554 typedef typename In::Value Value; |
|
555 static Value kruskal(const Graph& graph, const In& in, Out& out) { |
|
556 typedef typename In::Key MapEdge; |
|
557 typedef typename In::Value Value; |
|
558 typedef typename ItemSetTraits<Graph, MapEdge>::ItemIt MapEdgeIt; |
|
559 typedef std::vector<std::pair<MapEdge, Value> > Sequence; |
|
560 Sequence seq; |
|
561 |
|
562 for (MapEdgeIt it(graph); it != INVALID; ++it) { |
|
563 seq.push_back(make_pair(it, in[it])); |
|
564 } |
|
565 |
|
566 std::sort(seq.begin(), seq.end(), PairComp<Sequence>()); |
|
567 return KruskalOutputSelector<Graph, Sequence, Out>:: |
|
568 kruskal(graph, seq, out); |
|
569 } |
|
570 }; |
|
571 |
|
572 template <typename Graph, typename In, typename Out> |
|
573 struct KruskalOutputSelector<Graph, In, Out, |
|
574 typename enable_if<SequenceOutputIndicator<Out>, void>::type > |
|
575 { |
|
576 typedef typename In::value_type::second_type Value; |
|
577 |
|
578 static Value kruskal(const Graph& graph, const In& in, Out& out) { |
|
579 typedef StoreBoolMap<Out> Map; |
|
580 Map map(out); |
|
581 return _kruskal_bits::kruskal(graph, in, map); |
|
582 } |
|
583 |
|
584 }; |
|
585 |
|
586 template <typename Graph, typename In, typename Out> |
|
587 struct KruskalOutputSelector<Graph, In, Out, |
|
588 typename enable_if<MapOutputIndicator<Out>, void>::type > |
|
589 { |
|
590 typedef typename In::value_type::second_type Value; |
|
591 |
|
592 static Value kruskal(const Graph& graph, const In& in, Out& out) { |
|
593 return _kruskal_bits::kruskal(graph, in, out); |
|
594 } |
|
595 }; |
|
596 |
|
597 } |
|
598 |
|
599 /// \ingroup spantree |
|
600 /// |
|
601 /// \brief Kruskal's algorithm to find a minimum cost tree of a graph. |
|
602 /// |
42 /// This function runs Kruskal's algorithm to find a minimum cost tree. |
603 /// This function runs Kruskal's algorithm to find a minimum cost tree. |
43 /// Due to hard C++ hacking, it accepts various input and output types. |
604 /// Due to hard C++ hacking, it accepts various input and output types. |
44 /// |
605 /// |
45 /// \param g The graph the algorithm runs on. |
606 /// \param g The graph the algorithm runs on. |
46 /// It can be either \ref concepts::Graph "directed" or |
607 /// It can be either \ref concepts::Graph "directed" or |
48 /// If the graph is directed, the algorithm consider it to be |
609 /// If the graph is directed, the algorithm consider it to be |
49 /// undirected by disregarding the direction of the edges. |
610 /// undirected by disregarding the direction of the edges. |
50 /// |
611 /// |
51 /// \param in This object is used to describe the edge costs. It can be one |
612 /// \param in This object is used to describe the edge costs. It can be one |
52 /// of the following choices. |
613 /// of the following choices. |
53 /// - An STL compatible 'Forward Container' |
614 /// |
54 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, |
615 /// - An STL compatible 'Forward Container' with |
55 /// where \c X is the type of the costs. The pairs indicates the edges along |
616 /// <tt>std::pair<GR::UEdge,X></tt> or |
56 /// with the assigned cost. <em>They must be in a |
617 /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where |
|
618 /// \c X is the type of the costs. The pairs indicates the edges |
|
619 /// along with the assigned cost. <em>They must be in a |
57 /// cost-ascending order.</em> |
620 /// cost-ascending order.</em> |
58 /// - Any readable Edge map. The values of the map indicate the edge costs. |
621 /// - Any readable Edge map. The values of the map indicate the edge costs. |
59 /// |
622 /// |
60 /// \retval out Here we also have a choise. |
623 /// \retval out Here we also have a choise. |
61 /// - It can be a writable \c bool edge map. |
624 /// - It can be a writable \c bool edge map. After running the |
62 /// After running the algorithm |
625 /// algorithm this will contain the found minimum cost spanning |
63 /// this will contain the found minimum cost spanning tree: the value of an |
626 /// tree: the value of an edge will be set to \c true if it belongs |
64 /// edge will be set to \c true if it belongs to the tree, otherwise it will |
627 /// to the tree, otherwise it will be set to \c false. The value of |
65 /// be set to \c false. The value of each edge will be set exactly once. |
628 /// each edge will be set exactly once. |
66 /// - It can also be an iteraror of an STL Container with |
629 /// - It can also be an iteraror of an STL Container with |
67 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>. |
630 /// <tt>GR::UEdge</tt> or <tt>GR::Edge</tt> as its |
68 /// The algorithm copies the elements of the found tree into this sequence. |
631 /// <tt>value_type</tt>. The algorithm copies the elements of the |
69 /// For example, if we know that the spanning tree of the graph \c g has |
632 /// found tree into this sequence. For example, if we know that the |
70 /// say 53 edges, then |
633 /// spanning tree of the graph \c g has say 53 edges, then we can |
71 /// we can put its edges into an STL vector \c tree with a code like this. |
634 /// put its edges into an STL vector \c tree with a code like this. |
72 ///\code |
635 ///\code |
73 /// std::vector<Edge> tree(53); |
636 /// std::vector<Edge> tree(53); |
74 /// kruskal(g,cost,tree.begin()); |
637 /// kruskal(g,cost,tree.begin()); |
75 ///\endcode |
638 ///\endcode |
76 /// Or if we don't know in advance the size of the tree, we can write this. |
639 /// Or if we don't know in advance the size of the tree, we can |
77 ///\code |
640 /// write this. |
78 /// std::vector<Edge> tree; |
641 ///\code std::vector<Edge> tree; |
79 /// kruskal(g,cost,std::back_inserter(tree)); |
642 /// kruskal(g,cost,std::back_inserter(tree)); |
80 ///\endcode |
643 ///\endcode |
81 /// |
644 /// |
82 /// \return The cost of the found tree. |
645 /// \return The total cost of the found tree. |
83 /// |
646 /// |
84 /// \warning If kruskal runs on an |
647 /// \warning If kruskal runs on an be consistent of using the same |
85 /// \ref lemon::concepts::UGraph "undirected graph", be sure that the |
648 /// Edge type for input and output. |
86 /// map storing the tree is also undirected |
|
87 /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the |
|
88 /// half of the edges will not be set. |
|
89 /// |
649 /// |
90 |
650 |
91 #ifdef DOXYGEN |
651 #ifdef DOXYGEN |
92 template <class GR, class IN, class OUT> |
652 template <class Graph, class In, class Out> |
93 CostType |
653 Value kruskal(GR const& g, const In& in, Out& out) |
94 kruskal(GR const& g, IN const& in, |
654 #else |
95 OUT& out) |
655 template <class Graph, class In, class Out> |
96 #else |
656 inline typename _kruskal_bits::KruskalValueSelector<In>::Value |
97 template <class GR, class IN, class OUT> |
657 kruskal(const Graph& graph, const In& in, Out& out) |
98 typename IN::value_type::second_type |
|
99 kruskal(GR const& g, IN const& in, |
|
100 OUT& out, |
|
101 // typename IN::value_type::first_type = typename GR::Edge() |
|
102 // ,typename OUT::Key = OUT::Key() |
|
103 // //,typename OUT::Key = typename GR::Edge() |
|
104 const typename IN::value_type::first_type * = |
|
105 reinterpret_cast<const typename IN::value_type::first_type*>(0), |
|
106 const typename OUT::Key * = |
|
107 reinterpret_cast<const typename OUT::Key*>(0) |
|
108 ) |
|
109 #endif |
658 #endif |
110 { |
659 { |
111 typedef typename IN::value_type::second_type EdgeCost; |
660 return _kruskal_bits::KruskalInputSelector<Graph, In, Out>:: |
112 typedef typename GR::template NodeMap<int> NodeIntMap; |
661 kruskal(graph, in, out); |
113 typedef typename GR::Node Node; |
|
114 |
|
115 NodeIntMap comp(g); |
|
116 UnionFind<NodeIntMap> uf(comp); |
|
117 for (typename GR::NodeIt it(g); it != INVALID; ++it) { |
|
118 uf.insert(it); |
|
119 } |
|
120 |
|
121 EdgeCost tot_cost = 0; |
|
122 for (typename IN::const_iterator p = in.begin(); |
|
123 p!=in.end(); ++p ) { |
|
124 if ( uf.join(g.target((*p).first), |
|
125 g.source((*p).first)) ) { |
|
126 out.set((*p).first, true); |
|
127 tot_cost += (*p).second; |
|
128 } |
|
129 else { |
|
130 out.set((*p).first, false); |
|
131 } |
|
132 } |
|
133 return tot_cost; |
|
134 } |
662 } |
135 |
663 |
136 |
664 |
137 /// @} |
|
138 |
|
139 |
665 |
140 /* A work-around for running Kruskal with const-reference bool maps... */ |
666 |
141 |
667 template <class Graph, class In, class Out> |
142 /// Helper class for calling kruskal with "constant" output map. |
668 inline typename _kruskal_bits::KruskalValueSelector<In>::Value |
143 |
669 kruskal(const Graph& graph, const In& in, const Out& out) |
144 /// Helper class for calling kruskal with output maps constructed |
|
145 /// on-the-fly. |
|
146 /// |
|
147 /// A typical examle is the following call: |
|
148 /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>. |
|
149 /// Here, the third argument is a temporary object (which wraps around an |
|
150 /// iterator with a writable bool map interface), and thus by rules of C++ |
|
151 /// is a \c const object. To enable call like this exist this class and |
|
152 /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt> |
|
153 /// third argument. |
|
154 template<class Map> |
|
155 class NonConstMapWr { |
|
156 const Map &m; |
|
157 public: |
|
158 typedef typename Map::Key Key; |
|
159 typedef typename Map::Value Value; |
|
160 |
|
161 NonConstMapWr(const Map &_m) : m(_m) {} |
|
162 |
|
163 template<class Key> |
|
164 void set(Key const& k, Value const &v) const { m.set(k,v); } |
|
165 }; |
|
166 |
|
167 template <class GR, class IN, class OUT> |
|
168 inline |
|
169 typename IN::value_type::second_type |
|
170 kruskal(GR const& g, IN const& edges, OUT const& out_map, |
|
171 // typename IN::value_type::first_type = typename GR::Edge(), |
|
172 // typename OUT::Key = GR::Edge() |
|
173 const typename IN::value_type::first_type * = |
|
174 reinterpret_cast<const typename IN::value_type::first_type*>(0), |
|
175 const typename OUT::Key * = |
|
176 reinterpret_cast<const typename OUT::Key*>(0) |
|
177 ) |
|
178 { |
670 { |
179 NonConstMapWr<OUT> map_wr(out_map); |
671 return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>:: |
180 return kruskal(g, edges, map_wr); |
672 kruskal(graph, in, out); |
181 } |
673 } |
182 |
674 |
183 /* ** ** Input-objects ** ** */ |
|
184 |
|
185 /// Kruskal's input source. |
|
186 |
|
187 /// Kruskal's input source. |
|
188 /// |
|
189 /// In most cases you possibly want to use the \ref kruskal() instead. |
|
190 /// |
|
191 /// \sa makeKruskalMapInput() |
|
192 /// |
|
193 ///\param GR The type of the graph the algorithm runs on. |
|
194 ///\param Map An edge map containing the cost of the edges. |
|
195 ///\par |
|
196 ///The cost type can be any type satisfying |
|
197 ///the STL 'LessThan comparable' |
|
198 ///concept if it also has an operator+() implemented. (It is necessary for |
|
199 ///computing the total cost of the tree). |
|
200 /// |
|
201 template<class GR, class Map> |
|
202 class KruskalMapInput |
|
203 : public std::vector< std::pair<typename GR::Edge, |
|
204 typename Map::Value> > { |
|
205 |
|
206 public: |
|
207 typedef std::vector< std::pair<typename GR::Edge, |
|
208 typename Map::Value> > Parent; |
|
209 typedef typename Parent::value_type value_type; |
|
210 |
|
211 private: |
|
212 class comparePair { |
|
213 public: |
|
214 bool operator()(const value_type& a, |
|
215 const value_type& b) { |
|
216 return a.second < b.second; |
|
217 } |
|
218 }; |
|
219 |
|
220 template<class _GR> |
|
221 typename enable_if<UndirectedTagIndicator<_GR>,void>::type |
|
222 fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) |
|
223 { |
|
224 for(typename GR::UEdgeIt e(g);e!=INVALID;++e) |
|
225 push_back(value_type(g.direct(e, true), m[e])); |
|
226 } |
|
227 |
|
228 template<class _GR> |
|
229 typename disable_if<UndirectedTagIndicator<_GR>,void>::type |
|
230 fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) |
|
231 { |
|
232 for(typename GR::EdgeIt e(g);e!=INVALID;++e) |
|
233 push_back(value_type(e, m[e])); |
|
234 } |
|
235 |
|
236 |
|
237 public: |
|
238 |
|
239 void sort() { |
|
240 std::sort(this->begin(), this->end(), comparePair()); |
|
241 } |
|
242 |
|
243 KruskalMapInput(GR const& g, Map const& m) { |
|
244 fillWithEdges(g,m); |
|
245 sort(); |
|
246 } |
|
247 }; |
|
248 |
|
249 /// Creates a KruskalMapInput object for \ref kruskal() |
|
250 |
|
251 /// It makes easier to use |
|
252 /// \ref KruskalMapInput by making it unnecessary |
|
253 /// to explicitly give the type of the parameters. |
|
254 /// |
|
255 /// In most cases you possibly |
|
256 /// want to use \ref kruskal() instead. |
|
257 /// |
|
258 ///\param g The type of the graph the algorithm runs on. |
|
259 ///\param m An edge map containing the cost of the edges. |
|
260 ///\par |
|
261 ///The cost type can be any type satisfying the |
|
262 ///STL 'LessThan Comparable' |
|
263 ///concept if it also has an operator+() implemented. (It is necessary for |
|
264 ///computing the total cost of the tree). |
|
265 /// |
|
266 ///\return An appropriate input source for \ref kruskal(). |
|
267 /// |
|
268 template<class GR, class Map> |
|
269 inline |
|
270 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m) |
|
271 { |
|
272 return KruskalMapInput<GR,Map>(g,m); |
|
273 } |
|
274 |
|
275 |
|
276 |
|
277 /* ** ** Output-objects: simple writable bool maps ** ** */ |
|
278 |
|
279 |
|
280 |
|
281 /// A writable bool-map that makes a sequence of "true" keys |
|
282 |
|
283 /// A writable bool-map that creates a sequence out of keys that receives |
|
284 /// the value "true". |
|
285 /// |
|
286 /// \sa makeKruskalSequenceOutput() |
|
287 /// |
|
288 /// Very often, when looking for a min cost spanning tree, we want as |
|
289 /// output a container containing the edges of the found tree. For this |
|
290 /// purpose exist this class that wraps around an STL iterator with a |
|
291 /// writable bool map interface. When a key gets value "true" this key |
|
292 /// is added to sequence pointed by the iterator. |
|
293 /// |
|
294 /// A typical usage: |
|
295 ///\code |
|
296 /// std::vector<Graph::Edge> v; |
|
297 /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v))); |
|
298 ///\endcode |
|
299 /// |
|
300 /// For the most common case, when the input is given by a simple edge |
|
301 /// map and the output is a sequence of the tree edges, a special |
|
302 /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut(). |
|
303 /// |
|
304 /// \warning Not a regular property map, as it doesn't know its Key |
|
305 |
|
306 template<class Iterator> |
|
307 class KruskalSequenceOutput { |
|
308 mutable Iterator it; |
|
309 |
|
310 public: |
|
311 typedef typename std::iterator_traits<Iterator>::value_type Key; |
|
312 typedef bool Value; |
|
313 |
|
314 KruskalSequenceOutput(Iterator const &_it) : it(_it) {} |
|
315 |
|
316 template<typename Key> |
|
317 void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} } |
|
318 }; |
|
319 |
|
320 template<class Iterator> |
|
321 inline |
|
322 KruskalSequenceOutput<Iterator> |
|
323 makeKruskalSequenceOutput(Iterator it) { |
|
324 return KruskalSequenceOutput<Iterator>(it); |
|
325 } |
|
326 |
|
327 |
|
328 |
|
329 /* ** ** Wrapper funtions ** ** */ |
|
330 |
|
331 // \brief Wrapper function to kruskal(). |
|
332 // Input is from an edge map, output is a plain bool map. |
|
333 // |
|
334 // Wrapper function to kruskal(). |
|
335 // Input is from an edge map, output is a plain bool map. |
|
336 // |
|
337 // \param g The type of the graph the algorithm runs on. |
|
338 // \param in An edge map containing the cost of the edges. |
|
339 // \par |
|
340 // The cost type can be any type satisfying the |
|
341 // STL 'LessThan Comparable' |
|
342 // concept if it also has an operator+() implemented. (It is necessary for |
|
343 // computing the total cost of the tree). |
|
344 // |
|
345 // \retval out This must be a writable \c bool edge map. |
|
346 // After running the algorithm |
|
347 // this will contain the found minimum cost spanning tree: the value of an |
|
348 // edge will be set to \c true if it belongs to the tree, otherwise it will |
|
349 // be set to \c false. The value of each edge will be set exactly once. |
|
350 // |
|
351 // \return The cost of the found tree. |
|
352 |
|
353 template <class GR, class IN, class RET> |
|
354 inline |
|
355 typename IN::Value |
|
356 kruskal(GR const& g, |
|
357 IN const& in, |
|
358 RET &out, |
|
359 // typename IN::Key = typename GR::Edge(), |
|
360 //typename IN::Key = typename IN::Key (), |
|
361 // typename RET::Key = typename GR::Edge() |
|
362 const typename IN::Key * = |
|
363 reinterpret_cast<const typename IN::Key*>(0), |
|
364 const typename RET::Key * = |
|
365 reinterpret_cast<const typename RET::Key*>(0) |
|
366 ) |
|
367 { |
|
368 return kruskal(g, |
|
369 KruskalMapInput<GR,IN>(g,in), |
|
370 out); |
|
371 } |
|
372 |
|
373 // \brief Wrapper function to kruskal(). |
|
374 // Input is from an edge map, output is an STL Sequence. |
|
375 // |
|
376 // Wrapper function to kruskal(). |
|
377 // Input is from an edge map, output is an STL Sequence. |
|
378 // |
|
379 // \param g The type of the graph the algorithm runs on. |
|
380 // \param in An edge map containing the cost of the edges. |
|
381 // \par |
|
382 // The cost type can be any type satisfying the |
|
383 // STL 'LessThan Comparable' |
|
384 // concept if it also has an operator+() implemented. (It is necessary for |
|
385 // computing the total cost of the tree). |
|
386 // |
|
387 // \retval out This must be an iteraror of an STL Container with |
|
388 // <tt>GR::Edge</tt> as its <tt>value_type</tt>. |
|
389 // The algorithm copies the elements of the found tree into this sequence. |
|
390 // For example, if we know that the spanning tree of the graph \c g has |
|
391 // say 53 edges, then |
|
392 // we can put its edges into an STL vector \c tree with a code like this. |
|
393 //\code |
|
394 // std::vector<Edge> tree(53); |
|
395 // kruskal(g,cost,tree.begin()); |
|
396 //\endcode |
|
397 // Or if we don't know in advance the size of the tree, we can write this. |
|
398 //\code |
|
399 // std::vector<Edge> tree; |
|
400 // kruskal(g,cost,std::back_inserter(tree)); |
|
401 //\endcode |
|
402 // |
|
403 // \return The cost of the found tree. |
|
404 // |
|
405 // \bug its name does not follow the coding style. |
|
406 |
|
407 template <class GR, class IN, class RET> |
|
408 inline |
|
409 typename IN::Value |
|
410 kruskal(const GR& g, |
|
411 const IN& in, |
|
412 RET out, |
|
413 const typename RET::value_type * = |
|
414 reinterpret_cast<const typename RET::value_type*>(0) |
|
415 ) |
|
416 { |
|
417 KruskalSequenceOutput<RET> _out(out); |
|
418 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out); |
|
419 } |
|
420 |
|
421 template <class GR, class IN, class RET> |
|
422 inline |
|
423 typename IN::Value |
|
424 kruskal(const GR& g, |
|
425 const IN& in, |
|
426 RET *out |
|
427 ) |
|
428 { |
|
429 KruskalSequenceOutput<RET*> _out(out); |
|
430 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out); |
|
431 } |
|
432 |
|
433 /// @} |
|
434 |
|
435 } //namespace lemon |
675 } //namespace lemon |
436 |
676 |
437 #endif //LEMON_KRUSKAL_H |
677 #endif //LEMON_KRUSKAL_H |