src/lemon/kruskal.h
author deba
Fri, 04 Mar 2005 17:16:01 +0000
changeset 1192 aa4483befa56
parent 987 87f7c54892df
child 1274 5676e48ca026
permissions -rw-r--r--
Adding GraphEdgeSet and GraphNodeSet classes to graph_utils.h.
     1 /* -*- C++ -*-
     2  * src/lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
     3  *
     4  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     5  * (Egervary Combinatorial Optimization Research Group, EGRES).
     6  *
     7  * Permission to use, modify and distribute this software is granted
     8  * provided that this copyright notice appears in all copies. For
     9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
    16 
    17 #ifndef LEMON_KRUSKAL_H
    18 #define LEMON_KRUSKAL_H
    19 
    20 #include <algorithm>
    21 #include <lemon/unionfind.h>
    22 
    23 /**
    24 @defgroup spantree Minimum Cost Spanning Tree Algorithms
    25 @ingroup galgs
    26 \brief This group containes the algorithms for finding a minimum cost spanning
    27 tree in a graph
    28 
    29 This group containes the algorithms for finding a minimum cost spanning
    30 tree in a graph
    31 */
    32 
    33 ///\ingroup spantree
    34 ///\file
    35 ///\brief Kruskal's algorithm to compute a minimum cost tree
    36 ///
    37 ///Kruskal's algorithm to compute a minimum cost tree.
    38 
    39 namespace lemon {
    40 
    41   /// \addtogroup spantree
    42   /// @{
    43 
    44   /// Kruskal's algorithm to find a minimum cost tree of a graph.
    45 
    46   /// This function runs Kruskal's algorithm to find a minimum cost tree.
    47   /// \param G The graph the algorithm runs on. The algorithm considers the
    48   /// graph to be undirected, the direction of the edges are not used.
    49   ///
    50   /// \param in This object is used to describe the edge costs. It must
    51   /// be an STL compatible 'Forward Container'
    52   /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
    53   /// where X is the type of the costs. It must contain every edge in
    54   /// cost-ascending order.
    55   ///\par
    56   /// For the sake of simplicity, there is a helper class KruskalMapInput,
    57   /// which converts a
    58   /// simple edge map to an input of this form. Alternatively, you can use
    59   /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
    60   /// the edge costs are given by an edge map.
    61   ///
    62   /// \retval out This must 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   ///
    68   /// \return The cost of the found tree.
    69 
    70   template <class GR, class IN, class OUT>
    71   typename IN::value_type::second_type
    72   kruskal(GR const& G, IN const& in, 
    73 		 OUT& out)
    74   {
    75     typedef typename IN::value_type::second_type EdgeCost;
    76     typedef typename GR::template NodeMap<int> NodeIntMap;
    77     typedef typename GR::Node Node;
    78 
    79     NodeIntMap comp(G, -1);
    80     UnionFind<Node,NodeIntMap> uf(comp); 
    81       
    82     EdgeCost tot_cost = 0;
    83     for (typename IN::const_iterator p = in.begin(); 
    84 	 p!=in.end(); ++p ) {
    85       if ( uf.join(G.target((*p).first),
    86 		   G.source((*p).first)) ) {
    87 	out.set((*p).first, true);
    88 	tot_cost += (*p).second;
    89       }
    90       else {
    91 	out.set((*p).first, false);
    92       }
    93     }
    94     return tot_cost;
    95   }
    96 
    97   /* A work-around for running Kruskal with const-reference bool maps... */
    98 
    99   /// Helper class for calling kruskal with "constant" output map.
   100 
   101   /// Helper class for calling kruskal with output maps constructed
   102   /// on-the-fly.
   103   ///
   104   /// A typical examle is the following call:
   105   /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
   106   /// Here, the third argument is a temporary object (which wraps around an
   107   /// iterator with a writable bool map interface), and thus by rules of C++
   108   /// is a \c const object. To enable call like this exist this class and
   109   /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
   110   /// third argument.
   111   template<class Map>
   112   class NonConstMapWr {
   113     const Map &m;
   114   public:
   115     typedef typename Map::Value Value;
   116 
   117     NonConstMapWr(const Map &_m) : m(_m) {}
   118 
   119     template<class Key>
   120     void set(Key const& k, Value const &v) const { m.set(k,v); }
   121   };
   122 
   123   template <class GR, class IN, class OUT>
   124   inline
   125   typename IN::value_type::second_type
   126   kruskal(GR const& G, IN const& edges, OUT const& out_map)
   127   {
   128     NonConstMapWr<OUT> map_wr(out_map);
   129     return kruskal(G, edges, map_wr);
   130   }  
   131 
   132   /* ** ** Input-objects ** ** */
   133 
   134   /// Kruskal input source.
   135 
   136   /// Kruskal input source.
   137   ///
   138   /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
   139   ///
   140   /// \sa makeKruskalMapInput()
   141   ///
   142   ///\param GR The type of the graph the algorithm runs on.
   143   ///\param Map An edge map containing the cost of the edges.
   144   ///\par
   145   ///The cost type can be any type satisfying
   146   ///the STL 'LessThan comparable'
   147   ///concept if it also has an operator+() implemented. (It is necessary for
   148   ///computing the total cost of the tree).
   149   ///
   150   template<class GR, class Map>
   151   class KruskalMapInput
   152     : public std::vector< std::pair<typename GR::Edge,
   153 				    typename Map::Value> > {
   154     
   155   public:
   156     typedef std::vector< std::pair<typename GR::Edge,
   157 				   typename Map::Value> > Parent;
   158     typedef typename Parent::value_type value_type;
   159 
   160   private:
   161     class comparePair {
   162     public:
   163       bool operator()(const value_type& a,
   164 		      const value_type& b) {
   165 	return a.second < b.second;
   166       }
   167     };
   168 
   169   public:
   170 
   171     void sort() {
   172       std::sort(this->begin(), this->end(), comparePair());
   173     }
   174 
   175     KruskalMapInput(GR const& G, Map const& m) {
   176       typedef typename GR::EdgeIt EdgeIt;
   177       
   178       for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
   179       sort();
   180     }
   181   };
   182 
   183   /// Creates a KruskalMapInput object for \ref kruskal()
   184 
   185   /// It makes is easier to use 
   186   /// \ref KruskalMapInput by making it unnecessary 
   187   /// to explicitly give the type of the parameters.
   188   ///
   189   /// In most cases you possibly
   190   /// want to use the function kruskalEdgeMap() instead.
   191   ///
   192   ///\param G The type of the graph the algorithm runs on.
   193   ///\param m An edge map containing the cost of the edges.
   194   ///\par
   195   ///The cost type can be any type satisfying the
   196   ///STL 'LessThan Comparable'
   197   ///concept if it also has an operator+() implemented. (It is necessary for
   198   ///computing the total cost of the tree).
   199   ///
   200   ///\return An appropriate input source for \ref kruskal().
   201   ///
   202   template<class GR, class Map>
   203   inline
   204   KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
   205   {
   206     return KruskalMapInput<GR,Map>(G,m);
   207   }
   208   
   209   
   210 
   211   /* ** ** Output-objects: simple writable bool maps ** ** */
   212   
   213 
   214 
   215   /// A writable bool-map that makes a sequence of "true" keys
   216 
   217   /// A writable bool-map that creates a sequence out of keys that receives
   218   /// the value "true".
   219   ///
   220   /// \sa makeKruskalSequenceOutput()
   221   ///
   222   /// Very often, when looking for a min cost spanning tree, we want as
   223   /// output a container containing the edges of the found tree. For this
   224   /// purpose exist this class that wraps around an STL iterator with a
   225   /// writable bool map interface. When a key gets value "true" this key
   226   /// is added to sequence pointed by the iterator.
   227   ///
   228   /// A typical usage:
   229   /// \code
   230   /// std::vector<Graph::Edge> v;
   231   /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
   232   /// \endcode
   233   /// 
   234   /// For the most common case, when the input is given by a simple edge
   235   /// map and the output is a sequence of the tree edges, a special
   236   /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
   237   ///
   238   /// \warning Not a regular property map, as it doesn't know its Key
   239 
   240   template<class Iterator>
   241   class KruskalSequenceOutput {
   242     mutable Iterator it;
   243 
   244   public:
   245     typedef bool Value;
   246 
   247     KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
   248 
   249     template<typename Key>
   250     void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
   251   };
   252 
   253   template<class Iterator>
   254   inline
   255   KruskalSequenceOutput<Iterator>
   256   makeKruskalSequenceOutput(Iterator it) {
   257     return KruskalSequenceOutput<Iterator>(it);
   258   }
   259 
   260 
   261 
   262   /* ** ** Wrapper funtions ** ** */
   263 
   264 
   265 
   266   /// \brief Wrapper function to kruskal().
   267   /// Input is from an edge map, output is a plain bool map.
   268   ///
   269   /// Wrapper function to kruskal().
   270   /// Input is from an edge map, output is a plain bool map.
   271   ///
   272   ///\param G The type of the graph the algorithm runs on.
   273   ///\param in An edge map containing the cost of the edges.
   274   ///\par
   275   ///The cost type can be any type satisfying the
   276   ///STL 'LessThan Comparable'
   277   ///concept if it also has an operator+() implemented. (It is necessary for
   278   ///computing the total cost of the tree).
   279   ///
   280   /// \retval out This must be a writable \c bool edge map.
   281   /// After running the algorithm
   282   /// this will contain the found minimum cost spanning tree: the value of an
   283   /// edge will be set to \c true if it belongs to the tree, otherwise it will
   284   /// be set to \c false. The value of each edge will be set exactly once.
   285   ///
   286   /// \return The cost of the found tree.
   287 
   288   template <class GR, class IN, class RET>
   289   inline
   290   typename IN::Value
   291   kruskalEdgeMap(GR const& G,
   292 		 IN const& in,
   293 		 RET &out) {
   294     return kruskal(G,
   295 		   KruskalMapInput<GR,IN>(G,in),
   296 		   out);
   297   }
   298 
   299   /// \brief Wrapper function to kruskal().
   300   /// Input is from an edge map, output is an STL Sequence.
   301   ///
   302   /// Wrapper function to kruskal().
   303   /// Input is from an edge map, output is an STL Sequence.
   304   ///
   305   ///\param G The type of the graph the algorithm runs on.
   306   ///\param in An edge map containing the cost of the edges.
   307   ///\par
   308   ///The cost type can be any type satisfying the
   309   ///STL 'LessThan Comparable'
   310   ///concept if it also has an operator+() implemented. (It is necessary for
   311   ///computing the total cost of the tree).
   312   ///
   313   /// \retval out This must be an iteraror of an STL Container with
   314   /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
   315   /// The algorithm copies the elements of the found tree into this sequence.
   316   /// For example, if we know that the spanning tree of the graph \c G has
   317   /// say 53 edges then
   318   /// we can put its edges into a STL vector \c tree with a code like this.
   319   /// \code
   320   /// std::vector<Edge> tree(53);
   321   /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
   322   /// \endcode
   323   /// Or if we don't know in advance the size of the tree, we can write this.
   324   /// \code
   325   /// std::vector<Edge> tree;
   326   /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
   327   /// \endcode
   328   ///
   329   /// \return The cost of the found tree.
   330   ///
   331   /// \bug its name does not follow the coding style.
   332 
   333   template <class GR, class IN, class RET>
   334   inline
   335   typename IN::Value
   336   kruskalEdgeMap_IteratorOut(const GR& G,
   337 			     const IN& in,
   338 			     RET out)
   339   {
   340     KruskalSequenceOutput<RET> _out(out);
   341     return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
   342   }
   343 
   344   /// @}
   345 
   346 } //namespace lemon
   347 
   348 #endif //LEMON_KRUSKAL_H