Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

kruskal.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
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   /* A work-around for running Kruskal with const-reference bool maps... */
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   /* ** ** Input-objects ** ** */
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   /* ** ** Output-objects: simple writable bool maps ** ** */
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   /* ** ** Wrapper funtions ** ** */
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 } //namespace lemon
00347 
00348 #endif //LEMON_KRUSKAL_H

Generated on Mon Feb 21 15:02:21 2005 for LEMON by  doxygen 1.4.1