equal
deleted
inserted
replaced
16 |
16 |
17 #ifndef LEMON_KRUSKAL_H |
17 #ifndef LEMON_KRUSKAL_H |
18 #define LEMON_KRUSKAL_H |
18 #define LEMON_KRUSKAL_H |
19 |
19 |
20 #include <algorithm> |
20 #include <algorithm> |
|
21 #include <vector> |
21 #include <lemon/unionfind.h> |
22 #include <lemon/unionfind.h> |
22 #include<lemon/utility.h> |
23 #include <lemon/utility.h> |
23 |
24 |
24 /** |
25 /** |
25 @defgroup spantree Minimum Cost Spanning Tree Algorithms |
26 @defgroup spantree Minimum Cost Spanning Tree Algorithms |
26 @ingroup galgs |
27 @ingroup galgs |
27 \brief This group containes the algorithms for finding a minimum cost spanning |
28 \brief This group containes the algorithms for finding a minimum cost spanning |
313 template<class Iterator> |
314 template<class Iterator> |
314 class KruskalSequenceOutput { |
315 class KruskalSequenceOutput { |
315 mutable Iterator it; |
316 mutable Iterator it; |
316 |
317 |
317 public: |
318 public: |
318 typedef typename Iterator::value_type Key; |
319 typedef typename std::iterator_traits<Iterator>::value_type Key; |
319 typedef bool Value; |
320 typedef bool Value; |
320 |
321 |
321 KruskalSequenceOutput(Iterator const &_it) : it(_it) {} |
322 KruskalSequenceOutput(Iterator const &_it) : it(_it) {} |
322 |
323 |
323 template<typename Key> |
324 template<typename Key> |
413 inline |
414 inline |
414 typename IN::Value |
415 typename IN::Value |
415 kruskal(const GR& g, |
416 kruskal(const GR& g, |
416 const IN& in, |
417 const IN& in, |
417 RET out, |
418 RET out, |
418 //,typename RET::value_type = typename GR::Edge() |
|
419 //,typename RET::value_type = typename RET::value_type() |
|
420 const typename RET::value_type * = |
419 const typename RET::value_type * = |
421 (const typename RET::value_type *)(0) |
420 (const typename RET::value_type *)(0) |
422 ) |
421 ) |
423 { |
422 { |
424 KruskalSequenceOutput<RET> _out(out); |
423 KruskalSequenceOutput<RET> _out(out); |
425 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out); |
424 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out); |
426 } |
425 } |
427 |
426 |
|
427 template <class GR, class IN, class RET> |
|
428 inline |
|
429 typename IN::Value |
|
430 kruskal(const GR& g, |
|
431 const IN& in, |
|
432 RET *out |
|
433 ) |
|
434 { |
|
435 KruskalSequenceOutput<RET*> _out(out); |
|
436 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out); |
|
437 } |
|
438 |
428 /// @} |
439 /// @} |
429 |
440 |
430 } //namespace lemon |
441 } //namespace lemon |
431 |
442 |
432 #endif //LEMON_KRUSKAL_H |
443 #endif //LEMON_KRUSKAL_H |