lemon/kruskal.h
author athos
Fri, 05 Jan 2007 10:59:18 +0000
changeset 2334 c1e936e6a46b
parent 2260 4274224f8a7d
child 2354 3609c77b77be
permissions -rw-r--r--
I only corrected some errors in the documentation.
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_KRUSKAL_H
    20 #define LEMON_KRUSKAL_H
    21 
    22 #include <algorithm>
    23 #include <vector>
    24 #include <lemon/unionfind.h>
    25 #include <lemon/bits/utility.h>
    26 #include <lemon/bits/traits.h>
    27 
    28 ///\ingroup spantree
    29 ///\file
    30 ///\brief Kruskal's algorithm to compute a minimum cost tree
    31 ///
    32 ///Kruskal's algorithm to compute a minimum cost tree.
    33 ///
    34 ///\todo The file still needs some clean-up.
    35 
    36 namespace lemon {
    37 
    38   /// \addtogroup spantree
    39   /// @{
    40 
    41   /// Kruskal's algorithm to find a minimum cost tree of a graph.
    42 
    43   /// This function runs Kruskal's algorithm to find a minimum cost tree.
    44   /// Due to hard C++ hacking, it accepts various input and output types.
    45   ///
    46   /// \param g The graph the algorithm runs on.
    47   /// It can be either \ref concepts::Graph "directed" or 
    48   /// \ref concepts::UGraph "undirected".
    49   /// If the graph is directed, the algorithm consider it to be 
    50   /// undirected by disregarding the direction of the edges.
    51   ///
    52   /// \param in This object is used to describe the edge costs. It can be one
    53   /// of the following choices.
    54   /// - An STL compatible 'Forward Container'
    55   /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
    56   /// where \c X is the type of the costs. The pairs indicates the edges along
    57   /// with the assigned cost. <em>They must be in a
    58   /// cost-ascending order.</em>
    59   /// - Any readable Edge map. The values of the map indicate the edge costs.
    60   ///
    61   /// \retval out Here we also have a choise.
    62   /// - It can be a writable \c bool edge map. 
    63   /// After running the algorithm
    64   /// this will contain the found minimum cost spanning tree: the value of an
    65   /// edge will be set to \c true if it belongs to the tree, otherwise it will
    66   /// be set to \c false. The value of each edge will be set exactly once.
    67   /// - It can also be an iteraror of an STL Container with
    68   /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
    69   /// The algorithm copies the elements of the found tree into this sequence.
    70   /// For example, if we know that the spanning tree of the graph \c g has
    71   /// say 53 edges, then
    72   /// we can put its edges into an STL vector \c tree with a code like this.
    73   ///\code
    74   /// std::vector<Edge> tree(53);
    75   /// kruskal(g,cost,tree.begin());
    76   ///\endcode
    77   /// Or if we don't know in advance the size of the tree, we can write this.
    78   ///\code
    79   /// std::vector<Edge> tree;
    80   /// kruskal(g,cost,std::back_inserter(tree));
    81   ///\endcode
    82   ///
    83   /// \return The cost of the found tree.
    84   ///
    85   /// \warning If kruskal runs on an
    86   /// \ref lemon::concepts::UGraph "undirected graph", be sure that the
    87   /// map storing the tree is also undirected
    88   /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the
    89   /// half of the edges will not be set.
    90   ///
    91   /// \todo Discuss the case of undirected graphs: In this case the algorithm
    92   /// also require <tt>Edge</tt>s instead of <tt>UEdge</tt>s, as some
    93   /// people would expect. So, one should be careful not to add both of the
    94   /// <tt>Edge</tt>s belonging to a certain <tt>UEdge</tt>.
    95   /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.)
    96 
    97 #ifdef DOXYGEN
    98   template <class GR, class IN, class OUT>
    99   typename IN::value_type::second_type
   100   kruskal(GR const& g, IN const& in, 
   101 	  OUT& out)
   102 #else
   103   template <class GR, class IN, class OUT>
   104   typename IN::value_type::second_type
   105   kruskal(GR const& g, IN const& in, 
   106 	  OUT& out,
   107 // 	  typename IN::value_type::first_type = typename GR::Edge()
   108 // 	  ,typename OUT::Key = OUT::Key()
   109 // 	  //,typename OUT::Key = typename GR::Edge()
   110 	  const typename IN::value_type::first_type * = 
   111 	  (const typename IN::value_type::first_type *)(0),
   112 	  const typename OUT::Key * = (const typename OUT::Key *)(0)
   113 	  )
   114 #endif
   115   {
   116     typedef typename IN::value_type::second_type EdgeCost;
   117     typedef typename GR::template NodeMap<int> NodeIntMap;
   118     typedef typename GR::Node Node;
   119 
   120     NodeIntMap comp(g);
   121     UnionFind<NodeIntMap> uf(comp);
   122     for (typename GR::NodeIt it(g); it != INVALID; ++it) {
   123       uf.insert(it);
   124     }
   125       
   126     EdgeCost tot_cost = 0;
   127     for (typename IN::const_iterator p = in.begin(); 
   128 	 p!=in.end(); ++p ) {
   129       if ( uf.join(g.target((*p).first),
   130 		   g.source((*p).first)) ) {
   131 	out.set((*p).first, true);
   132 	tot_cost += (*p).second;
   133       }
   134       else {
   135 	out.set((*p).first, false);
   136       }
   137     }
   138     return tot_cost;
   139   }
   140 
   141  
   142   /// @}
   143 
   144   
   145   /* A work-around for running Kruskal with const-reference bool maps... */
   146 
   147   /// Helper class for calling kruskal with "constant" output map.
   148 
   149   /// Helper class for calling kruskal with output maps constructed
   150   /// on-the-fly.
   151   ///
   152   /// A typical examle is the following call:
   153   /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.
   154   /// Here, the third argument is a temporary object (which wraps around an
   155   /// iterator with a writable bool map interface), and thus by rules of C++
   156   /// is a \c const object. To enable call like this exist this class and
   157   /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
   158   /// third argument.
   159   template<class Map>
   160   class NonConstMapWr {
   161     const Map &m;
   162   public:
   163     typedef typename Map::Key Key;
   164     typedef typename Map::Value Value;
   165 
   166     NonConstMapWr(const Map &_m) : m(_m) {}
   167 
   168     template<class Key>
   169     void set(Key const& k, Value const &v) const { m.set(k,v); }
   170   };
   171 
   172   template <class GR, class IN, class OUT>
   173   inline
   174   typename IN::value_type::second_type
   175   kruskal(GR const& g, IN const& edges, OUT const& out_map,
   176 // 	  typename IN::value_type::first_type = typename GR::Edge(),
   177 // 	  typename OUT::Key = GR::Edge()
   178 	  const typename IN::value_type::first_type * = 
   179 	  (const typename IN::value_type::first_type *)(0),
   180 	  const typename OUT::Key * = (const typename OUT::Key *)(0)
   181 	  )
   182   {
   183     NonConstMapWr<OUT> map_wr(out_map);
   184     return kruskal(g, edges, map_wr);
   185   }  
   186 
   187   /* ** ** Input-objects ** ** */
   188 
   189   /// Kruskal's input source.
   190  
   191   /// Kruskal's input source.
   192   ///
   193   /// In most cases you possibly want to use the \ref kruskal() instead.
   194   ///
   195   /// \sa makeKruskalMapInput()
   196   ///
   197   ///\param GR The type of the graph the algorithm runs on.
   198   ///\param Map An edge map containing the cost of the edges.
   199   ///\par
   200   ///The cost type can be any type satisfying
   201   ///the STL 'LessThan comparable'
   202   ///concept if it also has an operator+() implemented. (It is necessary for
   203   ///computing the total cost of the tree).
   204   ///
   205   template<class GR, class Map>
   206   class KruskalMapInput
   207     : public std::vector< std::pair<typename GR::Edge,
   208 				    typename Map::Value> > {
   209     
   210   public:
   211     typedef std::vector< std::pair<typename GR::Edge,
   212 				   typename Map::Value> > Parent;
   213     typedef typename Parent::value_type value_type;
   214 
   215   private:
   216     class comparePair {
   217     public:
   218       bool operator()(const value_type& a,
   219 		      const value_type& b) {
   220 	return a.second < b.second;
   221       }
   222     };
   223 
   224     template<class _GR>
   225     typename enable_if<UndirectedTagIndicator<_GR>,void>::type
   226     fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) 
   227     {
   228       for(typename GR::UEdgeIt e(g);e!=INVALID;++e) 
   229 	push_back(value_type(g.direct(e, true), m[e]));
   230     }
   231 
   232     template<class _GR>
   233     typename disable_if<UndirectedTagIndicator<_GR>,void>::type
   234     fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) 
   235     {
   236       for(typename GR::EdgeIt e(g);e!=INVALID;++e) 
   237 	push_back(value_type(e, m[e]));
   238     }
   239     
   240     
   241   public:
   242 
   243     void sort() {
   244       std::sort(this->begin(), this->end(), comparePair());
   245     }
   246 
   247     KruskalMapInput(GR const& g, Map const& m) {
   248       fillWithEdges(g,m); 
   249       sort();
   250     }
   251   };
   252 
   253   /// Creates a KruskalMapInput object for \ref kruskal()
   254 
   255   /// It makes easier to use 
   256   /// \ref KruskalMapInput by making it unnecessary 
   257   /// to explicitly give the type of the parameters.
   258   ///
   259   /// In most cases you possibly
   260   /// want to use \ref kruskal() instead.
   261   ///
   262   ///\param g The type of the graph the algorithm runs on.
   263   ///\param m An edge map containing the cost of the edges.
   264   ///\par
   265   ///The cost type can be any type satisfying the
   266   ///STL 'LessThan Comparable'
   267   ///concept if it also has an operator+() implemented. (It is necessary for
   268   ///computing the total cost of the tree).
   269   ///
   270   ///\return An appropriate input source for \ref kruskal().
   271   ///
   272   template<class GR, class Map>
   273   inline
   274   KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
   275   {
   276     return KruskalMapInput<GR,Map>(g,m);
   277   }
   278   
   279   
   280 
   281   /* ** ** Output-objects: simple writable bool maps ** ** */
   282   
   283 
   284 
   285   /// A writable bool-map that makes a sequence of "true" keys
   286 
   287   /// A writable bool-map that creates a sequence out of keys that receives
   288   /// the value "true".
   289   ///
   290   /// \sa makeKruskalSequenceOutput()
   291   ///
   292   /// Very often, when looking for a min cost spanning tree, we want as
   293   /// output a container containing the edges of the found tree. For this
   294   /// purpose exist this class that wraps around an STL iterator with a
   295   /// writable bool map interface. When a key gets value "true" this key
   296   /// is added to sequence pointed by the iterator.
   297   ///
   298   /// A typical usage:
   299   ///\code
   300   /// std::vector<Graph::Edge> v;
   301   /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
   302   ///\endcode
   303   /// 
   304   /// For the most common case, when the input is given by a simple edge
   305   /// map and the output is a sequence of the tree edges, a special
   306   /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
   307   ///
   308   /// \warning Not a regular property map, as it doesn't know its Key
   309 
   310   template<class Iterator>
   311   class KruskalSequenceOutput {
   312     mutable Iterator it;
   313 
   314   public:
   315     typedef typename std::iterator_traits<Iterator>::value_type Key;
   316     typedef bool Value;
   317 
   318     KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
   319 
   320     template<typename Key>
   321     void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
   322   };
   323 
   324   template<class Iterator>
   325   inline
   326   KruskalSequenceOutput<Iterator>
   327   makeKruskalSequenceOutput(Iterator it) {
   328     return KruskalSequenceOutput<Iterator>(it);
   329   }
   330 
   331 
   332 
   333   /* ** ** Wrapper funtions ** ** */
   334 
   335 //   \brief Wrapper function to kruskal().
   336 //   Input is from an edge map, output is a plain bool map.
   337 //  
   338 //   Wrapper function to kruskal().
   339 //   Input is from an edge map, output is a plain bool map.
   340 //  
   341 //   \param g The type of the graph the algorithm runs on.
   342 //   \param in An edge map containing the cost of the edges.
   343 //   \par
   344 //   The cost type can be any type satisfying the
   345 //   STL 'LessThan Comparable'
   346 //   concept if it also has an operator+() implemented. (It is necessary for
   347 //   computing the total cost of the tree).
   348 //  
   349 //   \retval out This must be a writable \c bool edge map.
   350 //   After running the algorithm
   351 //   this will contain the found minimum cost spanning tree: the value of an
   352 //   edge will be set to \c true if it belongs to the tree, otherwise it will
   353 //   be set to \c false. The value of each edge will be set exactly once.
   354 //  
   355 //   \return The cost of the found tree.
   356 
   357   template <class GR, class IN, class RET>
   358   inline
   359   typename IN::Value
   360   kruskal(GR const& g,
   361 	  IN const& in,
   362 	  RET &out,
   363 	  //	  typename IN::Key = typename GR::Edge(),
   364 	  //typename IN::Key = typename IN::Key (),
   365 	  //	  typename RET::Key = typename GR::Edge()
   366 	  const typename IN::Key *  = (const typename IN::Key *)(0),
   367 	  const typename RET::Key * = (const typename RET::Key *)(0)
   368 	  )
   369   {
   370     return kruskal(g,
   371 		   KruskalMapInput<GR,IN>(g,in),
   372 		   out);
   373   }
   374 
   375 //   \brief Wrapper function to kruskal().
   376 //   Input is from an edge map, output is an STL Sequence.
   377 //  
   378 //   Wrapper function to kruskal().
   379 //   Input is from an edge map, output is an STL Sequence.
   380 //  
   381 //   \param g The type of the graph the algorithm runs on.
   382 //   \param in An edge map containing the cost of the edges.
   383 //   \par
   384 //   The cost type can be any type satisfying the
   385 //   STL 'LessThan Comparable'
   386 //   concept if it also has an operator+() implemented. (It is necessary for
   387 //   computing the total cost of the tree).
   388 //  
   389 //   \retval out This must be an iteraror of an STL Container with
   390 //   <tt>GR::Edge</tt> as its <tt>value_type</tt>.
   391 //   The algorithm copies the elements of the found tree into this sequence.
   392 //   For example, if we know that the spanning tree of the graph \c g has
   393 //   say 53 edges, then
   394 //   we can put its edges into an STL vector \c tree with a code like this.
   395 //\code
   396 //   std::vector<Edge> tree(53);
   397 //   kruskal(g,cost,tree.begin());
   398 //\endcode
   399 //   Or if we don't know in advance the size of the tree, we can write this.
   400 //\code
   401 //   std::vector<Edge> tree;
   402 //   kruskal(g,cost,std::back_inserter(tree));
   403 //\endcode
   404 //  
   405 //   \return The cost of the found tree.
   406 //  
   407 //   \bug its name does not follow the coding style.
   408 
   409   template <class GR, class IN, class RET>
   410   inline
   411   typename IN::Value
   412   kruskal(const GR& g,
   413 	  const IN& in,
   414 	  RET out,
   415 	  const typename RET::value_type * = 
   416 	  (const typename RET::value_type *)(0)
   417 	  )
   418   {
   419     KruskalSequenceOutput<RET> _out(out);
   420     return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
   421   }
   422  
   423   template <class GR, class IN, class RET>
   424   inline
   425   typename IN::Value
   426   kruskal(const GR& g,
   427 	  const IN& in,
   428 	  RET *out
   429 	  )
   430   {
   431     KruskalSequenceOutput<RET*> _out(out);
   432     return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
   433   }
   434  
   435   /// @}
   436 
   437 } //namespace lemon
   438 
   439 #endif //LEMON_KRUSKAL_H