alpar@906: /* -*- C++ -*-
alpar@906:  *
alpar@1956:  * This file is a part of LEMON, a generic C++ optimization library
alpar@1956:  *
alpar@1956:  * Copyright (C) 2003-2006
alpar@1956:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@1359:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@906:  *
alpar@906:  * Permission to use, modify and distribute this software is granted
alpar@906:  * provided that this copyright notice appears in all copies. For
alpar@906:  * precise terms see the accompanying LICENSE file.
alpar@906:  *
alpar@906:  * This software is provided "AS IS" with no warranty of any kind,
alpar@906:  * express or implied, and with no claim as to its suitability for any
alpar@906:  * purpose.
alpar@906:  *
alpar@906:  */
alpar@906: 
alpar@921: #ifndef LEMON_KRUSKAL_H
alpar@921: #define LEMON_KRUSKAL_H
alpar@810: 
alpar@810: #include <algorithm>
klao@1942: #include <vector>
alpar@921: #include <lemon/unionfind.h>
deba@1993: #include <lemon/bits/utility.h>
deba@1993: #include <lemon/bits/traits.h>
alpar@810: 
alpar@810: ///\ingroup spantree
alpar@810: ///\file
alpar@810: ///\brief Kruskal's algorithm to compute a minimum cost tree
alpar@810: ///
alpar@810: ///Kruskal's algorithm to compute a minimum cost tree.
alpar@1557: ///
alpar@1557: ///\todo The file still needs some clean-up.
alpar@810: 
alpar@921: namespace lemon {
alpar@810: 
alpar@810:   /// \addtogroup spantree
alpar@810:   /// @{
alpar@810: 
alpar@810:   /// Kruskal's algorithm to find a minimum cost tree of a graph.
alpar@810: 
alpar@810:   /// This function runs Kruskal's algorithm to find a minimum cost tree.
alpar@1557:   /// Due to hard C++ hacking, it accepts various input and output types.
alpar@1557:   ///
alpar@1555:   /// \param g The graph the algorithm runs on.
deba@2111:   /// It can be either \ref concept::Graph "directed" or 
klao@1909:   /// \ref concept::UGraph "undirected".
alpar@1555:   /// If the graph is directed, the algorithm consider it to be 
alpar@1555:   /// undirected by disregarding the direction of the edges.
alpar@810:   ///
alpar@1557:   /// \param in This object is used to describe the edge costs. It can be one
alpar@1557:   /// of the following choices.
alpar@1557:   /// - An STL compatible 'Forward Container'
alpar@824:   /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
alpar@1557:   /// where \c X is the type of the costs. The pairs indicates the edges along
alpar@1557:   /// with the assigned cost. <em>They must be in a
alpar@1557:   /// cost-ascending order.</em>
alpar@1557:   /// - Any readable Edge map. The values of the map indicate the edge costs.
alpar@810:   ///
alpar@1557:   /// \retval out Here we also have a choise.
alpar@1557:   /// - Is can be a writable \c bool edge map. 
alpar@810:   /// After running the algorithm
alpar@810:   /// this will contain the found minimum cost spanning tree: the value of an
alpar@810:   /// edge will be set to \c true if it belongs to the tree, otherwise it will
alpar@810:   /// be set to \c false. The value of each edge will be set exactly once.
alpar@1557:   /// - It can also be an iteraror of an STL Container with
alpar@1557:   /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
alpar@1557:   /// The algorithm copies the elements of the found tree into this sequence.
alpar@1557:   /// For example, if we know that the spanning tree of the graph \c g has
alpar@1603:   /// say 53 edges, then
alpar@1557:   /// we can put its edges into a STL vector \c tree with a code like this.
alpar@1946:   ///\code
alpar@1557:   /// std::vector<Edge> tree(53);
alpar@1557:   /// kruskal(g,cost,tree.begin());
alpar@1946:   ///\endcode
alpar@1557:   /// Or if we don't know in advance the size of the tree, we can write this.
alpar@1946:   ///\code
alpar@1557:   /// std::vector<Edge> tree;
alpar@1557:   /// kruskal(g,cost,std::back_inserter(tree));
alpar@1946:   ///\endcode
alpar@810:   ///
alpar@810:   /// \return The cost of the found tree.
alpar@1449:   ///
alpar@1631:   /// \warning If kruskal is run on an
klao@1909:   /// \ref lemon::concept::UGraph "undirected graph", be sure that the
alpar@1603:   /// map storing the tree is also undirected
klao@1909:   /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the
alpar@1603:   /// half of the edges will not be set.
alpar@1603:   ///
alpar@1449:   /// \todo Discuss the case of undirected graphs: In this case the algorithm
klao@1909:   /// also require <tt>Edge</tt>s instead of <tt>UEdge</tt>s, as some
alpar@1449:   /// people would expect. So, one should be careful not to add both of the
klao@1909:   /// <tt>Edge</tt>s belonging to a certain <tt>UEdge</tt>.
alpar@1570:   /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.)
alpar@810: 
alpar@1557: #ifdef DOXYGEN
alpar@824:   template <class GR, class IN, class OUT>
alpar@824:   typename IN::value_type::second_type
alpar@1547:   kruskal(GR const& g, IN const& in, 
alpar@1557: 	  OUT& out)
alpar@1557: #else
alpar@1557:   template <class GR, class IN, class OUT>
alpar@1557:   typename IN::value_type::second_type
alpar@1557:   kruskal(GR const& g, IN const& in, 
alpar@1557: 	  OUT& out,
alpar@1557: // 	  typename IN::value_type::first_type = typename GR::Edge()
alpar@1557: // 	  ,typename OUT::Key = OUT::Key()
alpar@1557: // 	  //,typename OUT::Key = typename GR::Edge()
alpar@1557: 	  const typename IN::value_type::first_type * = 
alpar@1557: 	  (const typename IN::value_type::first_type *)(0),
alpar@1557: 	  const typename OUT::Key * = (const typename OUT::Key *)(0)
alpar@1557: 	  )
alpar@1557: #endif
alpar@810:   {
alpar@824:     typedef typename IN::value_type::second_type EdgeCost;
alpar@824:     typedef typename GR::template NodeMap<int> NodeIntMap;
alpar@824:     typedef typename GR::Node Node;
alpar@810: 
deba@2205:     NodeIntMap comp(g);
deba@2205:     UnionFind<Node,NodeIntMap> uf(comp);
deba@2205:     for (typename GR::NodeIt it(g); it != INVALID; ++it) {
deba@2205:       uf.insert(it);
deba@2205:     }
alpar@810:       
alpar@810:     EdgeCost tot_cost = 0;
alpar@824:     for (typename IN::const_iterator p = in.begin(); 
alpar@810: 	 p!=in.end(); ++p ) {
alpar@1547:       if ( uf.join(g.target((*p).first),
alpar@1547: 		   g.source((*p).first)) ) {
alpar@810: 	out.set((*p).first, true);
alpar@810: 	tot_cost += (*p).second;
alpar@810:       }
alpar@810:       else {
alpar@810: 	out.set((*p).first, false);
alpar@810:       }
alpar@810:     }
alpar@810:     return tot_cost;
alpar@810:   }
alpar@810: 
alpar@1557:  
alpar@1557:   /// @}
alpar@1557: 
alpar@1557:   
alpar@810:   /* A work-around for running Kruskal with const-reference bool maps... */
alpar@810: 
klao@885:   /// Helper class for calling kruskal with "constant" output map.
klao@885: 
klao@885:   /// Helper class for calling kruskal with output maps constructed
klao@885:   /// on-the-fly.
alpar@810:   ///
klao@885:   /// A typical examle is the following call:
alpar@1547:   /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.
klao@885:   /// Here, the third argument is a temporary object (which wraps around an
klao@885:   /// iterator with a writable bool map interface), and thus by rules of C++
klao@885:   /// is a \c const object. To enable call like this exist this class and
klao@885:   /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
klao@885:   /// third argument.
alpar@824:   template<class Map>
alpar@810:   class NonConstMapWr {
alpar@810:     const Map &m;
alpar@810:   public:
alpar@1557:     typedef typename Map::Key Key;
alpar@987:     typedef typename Map::Value Value;
alpar@810: 
alpar@810:     NonConstMapWr(const Map &_m) : m(_m) {}
alpar@810: 
alpar@987:     template<class Key>
alpar@987:     void set(Key const& k, Value const &v) const { m.set(k,v); }
alpar@810:   };
alpar@810: 
alpar@824:   template <class GR, class IN, class OUT>
alpar@810:   inline
klao@885:   typename IN::value_type::second_type
alpar@1557:   kruskal(GR const& g, IN const& edges, OUT const& out_map,
alpar@1557: // 	  typename IN::value_type::first_type = typename GR::Edge(),
alpar@1557: // 	  typename OUT::Key = GR::Edge()
alpar@1557: 	  const typename IN::value_type::first_type * = 
alpar@1557: 	  (const typename IN::value_type::first_type *)(0),
alpar@1557: 	  const typename OUT::Key * = (const typename OUT::Key *)(0)
alpar@1557: 	  )
alpar@810:   {
alpar@824:     NonConstMapWr<OUT> map_wr(out_map);
alpar@1547:     return kruskal(g, edges, map_wr);
alpar@810:   }  
alpar@810: 
alpar@810:   /* ** ** Input-objects ** ** */
alpar@810: 
zsuzska@1274:   /// Kruskal's input source.
alpar@1557:  
zsuzska@1274:   /// Kruskal's input source.
alpar@810:   ///
alpar@1570:   /// In most cases you possibly want to use the \ref kruskal() instead.
alpar@810:   ///
alpar@810:   /// \sa makeKruskalMapInput()
alpar@810:   ///
alpar@824:   ///\param GR The type of the graph the algorithm runs on.
alpar@810:   ///\param Map An edge map containing the cost of the edges.
alpar@810:   ///\par
alpar@810:   ///The cost type can be any type satisfying
alpar@810:   ///the STL 'LessThan comparable'
alpar@810:   ///concept if it also has an operator+() implemented. (It is necessary for
alpar@810:   ///computing the total cost of the tree).
alpar@810:   ///
alpar@824:   template<class GR, class Map>
alpar@810:   class KruskalMapInput
alpar@824:     : public std::vector< std::pair<typename GR::Edge,
alpar@987: 				    typename Map::Value> > {
alpar@810:     
alpar@810:   public:
alpar@824:     typedef std::vector< std::pair<typename GR::Edge,
alpar@987: 				   typename Map::Value> > Parent;
alpar@810:     typedef typename Parent::value_type value_type;
alpar@810: 
alpar@810:   private:
alpar@810:     class comparePair {
alpar@810:     public:
alpar@810:       bool operator()(const value_type& a,
alpar@810: 		      const value_type& b) {
alpar@810: 	return a.second < b.second;
alpar@810:       }
alpar@810:     };
alpar@810: 
alpar@1449:     template<class _GR>
deba@1979:     typename enable_if<UndirectedTagIndicator<_GR>,void>::type
alpar@1547:     fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) 
alpar@1449:     {
klao@1909:       for(typename GR::UEdgeIt e(g);e!=INVALID;++e) 
deba@1679: 	push_back(value_type(g.direct(e, true), m[e]));
alpar@1449:     }
alpar@1449: 
alpar@1449:     template<class _GR>
deba@1979:     typename disable_if<UndirectedTagIndicator<_GR>,void>::type
alpar@1547:     fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) 
alpar@1449:     {
alpar@1547:       for(typename GR::EdgeIt e(g);e!=INVALID;++e) 
alpar@1449: 	push_back(value_type(e, m[e]));
alpar@1449:     }
alpar@1449:     
alpar@1449:     
alpar@810:   public:
alpar@810: 
alpar@810:     void sort() {
alpar@810:       std::sort(this->begin(), this->end(), comparePair());
alpar@810:     }
alpar@810: 
alpar@1547:     KruskalMapInput(GR const& g, Map const& m) {
alpar@1547:       fillWithEdges(g,m); 
alpar@810:       sort();
alpar@810:     }
alpar@810:   };
alpar@810: 
alpar@810:   /// Creates a KruskalMapInput object for \ref kruskal()
alpar@810: 
zsuzska@1274:   /// It makes easier to use 
alpar@810:   /// \ref KruskalMapInput by making it unnecessary 
alpar@810:   /// to explicitly give the type of the parameters.
alpar@810:   ///
alpar@810:   /// In most cases you possibly
alpar@1570:   /// want to use \ref kruskal() instead.
alpar@810:   ///
alpar@1547:   ///\param g The type of the graph the algorithm runs on.
alpar@810:   ///\param m An edge map containing the cost of the edges.
alpar@810:   ///\par
alpar@810:   ///The cost type can be any type satisfying the
alpar@810:   ///STL 'LessThan Comparable'
alpar@810:   ///concept if it also has an operator+() implemented. (It is necessary for
alpar@810:   ///computing the total cost of the tree).
alpar@810:   ///
alpar@810:   ///\return An appropriate input source for \ref kruskal().
alpar@810:   ///
alpar@824:   template<class GR, class Map>
alpar@810:   inline
alpar@1547:   KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
alpar@810:   {
alpar@1547:     return KruskalMapInput<GR,Map>(g,m);
alpar@810:   }
alpar@810:   
alpar@810:   
klao@885: 
klao@885:   /* ** ** Output-objects: simple writable bool maps ** ** */
alpar@810:   
klao@885: 
klao@885: 
alpar@810:   /// A writable bool-map that makes a sequence of "true" keys
alpar@810: 
alpar@810:   /// A writable bool-map that creates a sequence out of keys that receives
alpar@810:   /// the value "true".
klao@885:   ///
klao@885:   /// \sa makeKruskalSequenceOutput()
klao@885:   ///
klao@885:   /// Very often, when looking for a min cost spanning tree, we want as
klao@885:   /// output a container containing the edges of the found tree. For this
klao@885:   /// purpose exist this class that wraps around an STL iterator with a
klao@885:   /// writable bool map interface. When a key gets value "true" this key
klao@885:   /// is added to sequence pointed by the iterator.
klao@885:   ///
klao@885:   /// A typical usage:
alpar@1946:   ///\code
klao@885:   /// std::vector<Graph::Edge> v;
klao@885:   /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
alpar@1946:   ///\endcode
klao@885:   /// 
klao@885:   /// For the most common case, when the input is given by a simple edge
klao@885:   /// map and the output is a sequence of the tree edges, a special
klao@885:   /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
klao@885:   ///
alpar@987:   /// \warning Not a regular property map, as it doesn't know its Key
klao@885: 
alpar@824:   template<class Iterator>
klao@885:   class KruskalSequenceOutput {
alpar@810:     mutable Iterator it;
alpar@810: 
alpar@810:   public:
klao@1942:     typedef typename std::iterator_traits<Iterator>::value_type Key;
alpar@987:     typedef bool Value;
alpar@810: 
klao@885:     KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
alpar@810: 
alpar@987:     template<typename Key>
alpar@987:     void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
alpar@810:   };
alpar@810: 
alpar@824:   template<class Iterator>
alpar@810:   inline
klao@885:   KruskalSequenceOutput<Iterator>
klao@885:   makeKruskalSequenceOutput(Iterator it) {
klao@885:     return KruskalSequenceOutput<Iterator>(it);
alpar@810:   }
alpar@810: 
klao@885: 
klao@885: 
alpar@810:   /* ** ** Wrapper funtions ** ** */
alpar@810: 
alpar@1557: //   \brief Wrapper function to kruskal().
alpar@1557: //   Input is from an edge map, output is a plain bool map.
alpar@1557: //  
alpar@1557: //   Wrapper function to kruskal().
alpar@1557: //   Input is from an edge map, output is a plain bool map.
alpar@1557: //  
alpar@1557: //   \param g The type of the graph the algorithm runs on.
alpar@1557: //   \param in An edge map containing the cost of the edges.
alpar@1557: //   \par
alpar@1557: //   The cost type can be any type satisfying the
alpar@1557: //   STL 'LessThan Comparable'
alpar@1557: //   concept if it also has an operator+() implemented. (It is necessary for
alpar@1557: //   computing the total cost of the tree).
alpar@1557: //  
alpar@1557: //   \retval out This must be a writable \c bool edge map.
alpar@1557: //   After running the algorithm
alpar@1557: //   this will contain the found minimum cost spanning tree: the value of an
alpar@1557: //   edge will be set to \c true if it belongs to the tree, otherwise it will
alpar@1557: //   be set to \c false. The value of each edge will be set exactly once.
alpar@1557: //  
alpar@1557: //   \return The cost of the found tree.
alpar@810: 
alpar@824:   template <class GR, class IN, class RET>
alpar@810:   inline
alpar@987:   typename IN::Value
alpar@1557:   kruskal(GR const& g,
alpar@1557: 	  IN const& in,
alpar@1557: 	  RET &out,
alpar@1557: 	  //	  typename IN::Key = typename GR::Edge(),
alpar@1557: 	  //typename IN::Key = typename IN::Key (),
alpar@1557: 	  //	  typename RET::Key = typename GR::Edge()
alpar@1557: 	  const typename IN::Key *  = (const typename IN::Key *)(0),
alpar@1557: 	  const typename RET::Key * = (const typename RET::Key *)(0)
alpar@1557: 	  )
alpar@1557:   {
alpar@1547:     return kruskal(g,
alpar@1547: 		   KruskalMapInput<GR,IN>(g,in),
alpar@810: 		   out);
alpar@810:   }
alpar@810: 
alpar@1557: //   \brief Wrapper function to kruskal().
alpar@1557: //   Input is from an edge map, output is an STL Sequence.
alpar@1557: //  
alpar@1557: //   Wrapper function to kruskal().
alpar@1557: //   Input is from an edge map, output is an STL Sequence.
alpar@1557: //  
alpar@1557: //   \param g The type of the graph the algorithm runs on.
alpar@1557: //   \param in An edge map containing the cost of the edges.
alpar@1557: //   \par
alpar@1557: //   The cost type can be any type satisfying the
alpar@1557: //   STL 'LessThan Comparable'
alpar@1557: //   concept if it also has an operator+() implemented. (It is necessary for
alpar@1557: //   computing the total cost of the tree).
alpar@1557: //  
alpar@1557: //   \retval out This must be an iteraror of an STL Container with
alpar@1557: //   <tt>GR::Edge</tt> as its <tt>value_type</tt>.
alpar@1557: //   The algorithm copies the elements of the found tree into this sequence.
alpar@1557: //   For example, if we know that the spanning tree of the graph \c g has
alpar@1603: //   say 53 edges, then
alpar@1557: //   we can put its edges into a STL vector \c tree with a code like this.
alpar@1946: //\code
alpar@1557: //   std::vector<Edge> tree(53);
alpar@1570: //   kruskal(g,cost,tree.begin());
alpar@1946: //\endcode
alpar@1557: //   Or if we don't know in advance the size of the tree, we can write this.
alpar@1946: //\code
alpar@1557: //   std::vector<Edge> tree;
alpar@1570: //   kruskal(g,cost,std::back_inserter(tree));
alpar@1946: //\endcode
alpar@1557: //  
alpar@1557: //   \return The cost of the found tree.
alpar@1557: //  
alpar@1557: //   \bug its name does not follow the coding style.
klao@885: 
alpar@824:   template <class GR, class IN, class RET>
alpar@810:   inline
alpar@987:   typename IN::Value
alpar@1557:   kruskal(const GR& g,
alpar@1557: 	  const IN& in,
alpar@1557: 	  RET out,
alpar@1557: 	  const typename RET::value_type * = 
alpar@1557: 	  (const typename RET::value_type *)(0)
alpar@1557: 	  )
alpar@810:   {
klao@885:     KruskalSequenceOutput<RET> _out(out);
alpar@1547:     return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
alpar@810:   }
alpar@1557:  
klao@1942:   template <class GR, class IN, class RET>
klao@1942:   inline
klao@1942:   typename IN::Value
klao@1942:   kruskal(const GR& g,
klao@1942: 	  const IN& in,
klao@1942: 	  RET *out
klao@1942: 	  )
klao@1942:   {
klao@1942:     KruskalSequenceOutput<RET*> _out(out);
klao@1942:     return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
klao@1942:   }
klao@1942:  
alpar@810:   /// @}
alpar@810: 
alpar@921: } //namespace lemon
alpar@810: 
alpar@921: #endif //LEMON_KRUSKAL_H