00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef LEMON_KRUSKAL_H
00020 #define LEMON_KRUSKAL_H
00021
00022 #include <algorithm>
00023 #include <vector>
00024 #include <lemon/unionfind.h>
00025 #include <lemon/utility.h>
00026
00037
00038
00039
00040
00041
00042
00043
00044
00045 namespace lemon {
00046
00049
00051
00105
00106 #ifdef DOXYGEN
00107 template <class GR, class IN, class OUT>
00108 typename IN::value_type::second_type
00109 kruskal(GR const& g, IN const& in,
00110 OUT& out)
00111 #else
00112 template <class GR, class IN, class OUT>
00113 typename IN::value_type::second_type
00114 kruskal(GR const& g, IN const& in,
00115 OUT& out,
00116
00117
00118
00119 const typename IN::value_type::first_type * =
00120 (const typename IN::value_type::first_type *)(0),
00121 const typename OUT::Key * = (const typename OUT::Key *)(0)
00122 )
00123 #endif
00124 {
00125 typedef typename IN::value_type::second_type EdgeCost;
00126 typedef typename GR::template NodeMap<int> NodeIntMap;
00127 typedef typename GR::Node Node;
00128
00129 NodeIntMap comp(g, -1);
00130 UnionFind<Node,NodeIntMap> uf(comp);
00131
00132 EdgeCost tot_cost = 0;
00133 for (typename IN::const_iterator p = in.begin();
00134 p!=in.end(); ++p ) {
00135 if ( uf.join(g.target((*p).first),
00136 g.source((*p).first)) ) {
00137 out.set((*p).first, true);
00138 tot_cost += (*p).second;
00139 }
00140 else {
00141 out.set((*p).first, false);
00142 }
00143 }
00144 return tot_cost;
00145 }
00146
00147
00149
00150
00151
00152
00154
00165 template<class Map>
00166 class NonConstMapWr {
00167 const Map &m;
00168 public:
00169 typedef typename Map::Key Key;
00170 typedef typename Map::Value Value;
00171
00172 NonConstMapWr(const Map &_m) : m(_m) {}
00173
00174 template<class Key>
00175 void set(Key const& k, Value const &v) const { m.set(k,v); }
00176 };
00177
00178 template <class GR, class IN, class OUT>
00179 inline
00180 typename IN::value_type::second_type
00181 kruskal(GR const& g, IN const& edges, OUT const& out_map,
00182
00183
00184 const typename IN::value_type::first_type * =
00185 (const typename IN::value_type::first_type *)(0),
00186 const typename OUT::Key * = (const typename OUT::Key *)(0)
00187 )
00188 {
00189 NonConstMapWr<OUT> map_wr(out_map);
00190 return kruskal(g, edges, map_wr);
00191 }
00192
00193
00194
00196
00211 template<class GR, class Map>
00212 class KruskalMapInput
00213 : public std::vector< std::pair<typename GR::Edge,
00214 typename Map::Value> > {
00215
00216 public:
00217 typedef std::vector< std::pair<typename GR::Edge,
00218 typename Map::Value> > Parent;
00219 typedef typename Parent::value_type value_type;
00220
00221 private:
00222 class comparePair {
00223 public:
00224 bool operator()(const value_type& a,
00225 const value_type& b) {
00226 return a.second < b.second;
00227 }
00228 };
00229
00230 template<class _GR>
00231 typename enable_if<typename _GR::UTag,void>::type
00232 fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0)
00233 {
00234 for(typename GR::UEdgeIt e(g);e!=INVALID;++e)
00235 push_back(value_type(g.direct(e, true), m[e]));
00236 }
00237
00238 template<class _GR>
00239 typename disable_if<typename _GR::UTag,void>::type
00240 fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1)
00241 {
00242 for(typename GR::EdgeIt e(g);e!=INVALID;++e)
00243 push_back(value_type(e, m[e]));
00244 }
00245
00246
00247 public:
00248
00249 void sort() {
00250 std::sort(this->begin(), this->end(), comparePair());
00251 }
00252
00253 KruskalMapInput(GR const& g, Map const& m) {
00254 fillWithEdges(g,m);
00255 sort();
00256 }
00257 };
00258
00260
00278 template<class GR, class Map>
00279 inline
00280 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
00281 {
00282 return KruskalMapInput<GR,Map>(g,m);
00283 }
00284
00285
00286
00287
00288
00289
00290
00292
00315
00316 template<class Iterator>
00317 class KruskalSequenceOutput {
00318 mutable Iterator it;
00319
00320 public:
00321 typedef typename std::iterator_traits<Iterator>::value_type Key;
00322 typedef bool Value;
00323
00324 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
00325
00326 template<typename Key>
00327 void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
00328 };
00329
00330 template<class Iterator>
00331 inline
00332 KruskalSequenceOutput<Iterator>
00333 makeKruskalSequenceOutput(Iterator it) {
00334 return KruskalSequenceOutput<Iterator>(it);
00335 }
00336
00337
00338
00339
00340
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350
00351
00352
00353
00354
00355
00356
00357
00358
00359
00360
00361
00362
00363 template <class GR, class IN, class RET>
00364 inline
00365 typename IN::Value
00366 kruskal(GR const& g,
00367 IN const& in,
00368 RET &out,
00369
00370
00371
00372 const typename IN::Key * = (const typename IN::Key *)(0),
00373 const typename RET::Key * = (const typename RET::Key *)(0)
00374 )
00375 {
00376 return kruskal(g,
00377 KruskalMapInput<GR,IN>(g,in),
00378 out);
00379 }
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410
00411
00412
00413
00414
00415 template <class GR, class IN, class RET>
00416 inline
00417 typename IN::Value
00418 kruskal(const GR& g,
00419 const IN& in,
00420 RET out,
00421 const typename RET::value_type * =
00422 (const typename RET::value_type *)(0)
00423 )
00424 {
00425 KruskalSequenceOutput<RET> _out(out);
00426 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
00427 }
00428
00429 template <class GR, class IN, class RET>
00430 inline
00431 typename IN::Value
00432 kruskal(const GR& g,
00433 const IN& in,
00434 RET *out
00435 )
00436 {
00437 KruskalSequenceOutput<RET*> _out(out);
00438 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
00439 }
00440
00442
00443 }
00444
00445 #endif //LEMON_KRUSKAL_H