00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #ifndef LEMON_KRUSKAL_H
00018 #define LEMON_KRUSKAL_H
00019
00020 #include <algorithm>
00021 #include <lemon/unionfind.h>
00022
00033
00034
00035
00036
00037
00038
00039 namespace lemon {
00040
00043
00045
00069
00070 template <class GR, class IN, class OUT>
00071 typename IN::value_type::second_type
00072 kruskal(GR const& G, IN const& in,
00073 OUT& out)
00074 {
00075 typedef typename IN::value_type::second_type EdgeCost;
00076 typedef typename GR::template NodeMap<int> NodeIntMap;
00077 typedef typename GR::Node Node;
00078
00079 NodeIntMap comp(G, -1);
00080 UnionFind<Node,NodeIntMap> uf(comp);
00081
00082 EdgeCost tot_cost = 0;
00083 for (typename IN::const_iterator p = in.begin();
00084 p!=in.end(); ++p ) {
00085 if ( uf.join(G.target((*p).first),
00086 G.source((*p).first)) ) {
00087 out.set((*p).first, true);
00088 tot_cost += (*p).second;
00089 }
00090 else {
00091 out.set((*p).first, false);
00092 }
00093 }
00094 return tot_cost;
00095 }
00096
00097
00098
00100
00111 template<class Map>
00112 class NonConstMapWr {
00113 const Map &m;
00114 public:
00115 typedef typename Map::Value Value;
00116
00117 NonConstMapWr(const Map &_m) : m(_m) {}
00118
00119 template<class Key>
00120 void set(Key const& k, Value const &v) const { m.set(k,v); }
00121 };
00122
00123 template <class GR, class IN, class OUT>
00124 inline
00125 typename IN::value_type::second_type
00126 kruskal(GR const& G, IN const& edges, OUT const& out_map)
00127 {
00128 NonConstMapWr<OUT> map_wr(out_map);
00129 return kruskal(G, edges, map_wr);
00130 }
00131
00132
00133
00135
00150 template<class GR, class Map>
00151 class KruskalMapInput
00152 : public std::vector< std::pair<typename GR::Edge,
00153 typename Map::Value> > {
00154
00155 public:
00156 typedef std::vector< std::pair<typename GR::Edge,
00157 typename Map::Value> > Parent;
00158 typedef typename Parent::value_type value_type;
00159
00160 private:
00161 class comparePair {
00162 public:
00163 bool operator()(const value_type& a,
00164 const value_type& b) {
00165 return a.second < b.second;
00166 }
00167 };
00168
00169 public:
00170
00171 void sort() {
00172 std::sort(this->begin(), this->end(), comparePair());
00173 }
00174
00175 KruskalMapInput(GR const& G, Map const& m) {
00176 typedef typename GR::EdgeIt EdgeIt;
00177
00178 for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
00179 sort();
00180 }
00181 };
00182
00184
00202 template<class GR, class Map>
00203 inline
00204 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
00205 {
00206 return KruskalMapInput<GR,Map>(G,m);
00207 }
00208
00209
00210
00211
00212
00213
00214
00216
00239
00240 template<class Iterator>
00241 class KruskalSequenceOutput {
00242 mutable Iterator it;
00243
00244 public:
00245 typedef bool Value;
00246
00247 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
00248
00249 template<typename Key>
00250 void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
00251 };
00252
00253 template<class Iterator>
00254 inline
00255 KruskalSequenceOutput<Iterator>
00256 makeKruskalSequenceOutput(Iterator it) {
00257 return KruskalSequenceOutput<Iterator>(it);
00258 }
00259
00260
00261
00262
00263
00264
00265
00287
00288 template <class GR, class IN, class RET>
00289 inline
00290 typename IN::Value
00291 kruskalEdgeMap(GR const& G,
00292 IN const& in,
00293 RET &out) {
00294 return kruskal(G,
00295 KruskalMapInput<GR,IN>(G,in),
00296 out);
00297 }
00298
00332
00333 template <class GR, class IN, class RET>
00334 inline
00335 typename IN::Value
00336 kruskalEdgeMap_IteratorOut(const GR& G,
00337 const IN& in,
00338 RET out)
00339 {
00340 KruskalSequenceOutput<RET> _out(out);
00341 return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
00342 }
00343
00345
00346 }
00347
00348 #endif //LEMON_KRUSKAL_H