kruskal.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  *
00003  * This file is a part of LEMON, a generic C++ optimization library
00004  *
00005  * Copyright (C) 2003-2006
00006  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00007  * (Egervary Research Group on Combinatorial Optimization, EGRES).
00008  *
00009  * Permission to use, modify and distribute this software is granted
00010  * provided that this copyright notice appears in all copies. For
00011  * precise terms see the accompanying LICENSE file.
00012  *
00013  * This software is provided "AS IS" with no warranty of any kind,
00014  * express or implied, and with no claim as to its suitability for any
00015  * purpose.
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 //        typename IN::value_type::first_type = typename GR::Edge()
00117 //        ,typename OUT::Key = OUT::Key()
00118 //        //,typename OUT::Key = typename GR::Edge()
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   /* A work-around for running Kruskal with const-reference bool maps... */
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 //        typename IN::value_type::first_type = typename GR::Edge(),
00183 //        typename OUT::Key = GR::Edge()
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   /* ** ** Input-objects ** ** */
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   /* ** ** Output-objects: simple writable bool maps ** ** */
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   /* ** ** Wrapper funtions ** ** */
00340 
00341 //   \brief Wrapper function to kruskal().
00342 //   Input is from an edge map, output is a plain bool map.
00343 //  
00344 //   Wrapper function to kruskal().
00345 //   Input is from an edge map, output is a plain bool map.
00346 //  
00347 //   \param g The type of the graph the algorithm runs on.
00348 //   \param in An edge map containing the cost of the edges.
00349 //   \par
00350 //   The cost type can be any type satisfying the
00351 //   STL 'LessThan Comparable'
00352 //   concept if it also has an operator+() implemented. (It is necessary for
00353 //   computing the total cost of the tree).
00354 //  
00355 //   \retval out This must be a writable \c bool edge map.
00356 //   After running the algorithm
00357 //   this will contain the found minimum cost spanning tree: the value of an
00358 //   edge will be set to \c true if it belongs to the tree, otherwise it will
00359 //   be set to \c false. The value of each edge will be set exactly once.
00360 //  
00361 //   \return The cost of the found tree.
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           //      typename IN::Key = typename GR::Edge(),
00370           //typename IN::Key = typename IN::Key (),
00371           //      typename RET::Key = typename GR::Edge()
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 //   \brief Wrapper function to kruskal().
00382 //   Input is from an edge map, output is an STL Sequence.
00383 //  
00384 //   Wrapper function to kruskal().
00385 //   Input is from an edge map, output is an STL Sequence.
00386 //  
00387 //   \param g The type of the graph the algorithm runs on.
00388 //   \param in An edge map containing the cost of the edges.
00389 //   \par
00390 //   The cost type can be any type satisfying the
00391 //   STL 'LessThan Comparable'
00392 //   concept if it also has an operator+() implemented. (It is necessary for
00393 //   computing the total cost of the tree).
00394 //  
00395 //   \retval out This must be an iteraror of an STL Container with
00396 //   <tt>GR::Edge</tt> as its <tt>value_type</tt>.
00397 //   The algorithm copies the elements of the found tree into this sequence.
00398 //   For example, if we know that the spanning tree of the graph \c g has
00399 //   say 53 edges, then
00400 //   we can put its edges into a STL vector \c tree with a code like this.
00401 //\code
00402 //   std::vector<Edge> tree(53);
00403 //   kruskal(g,cost,tree.begin());
00404 //\endcode
00405 //   Or if we don't know in advance the size of the tree, we can write this.
00406 //\code
00407 //   std::vector<Edge> tree;
00408 //   kruskal(g,cost,std::back_inserter(tree));
00409 //\endcode
00410 //  
00411 //   \return The cost of the found tree.
00412 //  
00413 //   \bug its name does not follow the coding style.
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 } //namespace lemon
00444 
00445 #endif //LEMON_KRUSKAL_H

Generated on Fri Feb 3 18:37:59 2006 for LEMON by  doxygen 1.4.6