alpar@810: // -*- c++ -*- //
alpar@810: #ifndef HUGO_KRUSKAL_H
alpar@810: #define HUGO_KRUSKAL_H
alpar@810: 
alpar@810: #include <algorithm>
alpar@810: #include <hugo/unionfind.h>
alpar@810: 
alpar@810: /**
alpar@810: @defgroup spantree Minimum Cost Spanning Tree Algorithms
alpar@810: @ingroup galgs
alpar@810: \brief This group containes the algorithms for finding a minimum cost spanning
alpar@810: tree in a graph
alpar@810: 
alpar@810: This group containes the algorithms for finding a minimum cost spanning
alpar@810: tree in a graph
alpar@810: */
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@810: 
alpar@824: ///\weakgroup spantree
alpar@810: namespace hugo {
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@810:   /// \param G The graph the algorithm runs on. The algorithm considers the
alpar@810:   /// graph to be undirected, the direction of the edges are not used.
alpar@810:   ///
alpar@810:   /// \param in This object is used to describe the edge costs. It must
alpar@810:   /// be an STL compatible 'Forward Container'
alpar@824:   /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
alpar@810:   /// where X is the type of the costs. It must contain every edge in
alpar@810:   /// cost-ascending order.
alpar@810:   ///\par
alpar@810:   /// For the sake of simplicity, there is a helper class KruskalMapInput,
alpar@810:   /// which converts a
alpar@810:   /// simple edge map to an input of this form. Alternatively, you can use
alpar@810:   /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
alpar@810:   /// the edge costs are given by an edge map.
alpar@810:   ///
alpar@810:   /// \retval out This must 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@810:   ///
alpar@810:   /// \return The cost of the found tree.
alpar@810: 
alpar@824:   template <class GR, class IN, class OUT>
alpar@824:   typename IN::value_type::second_type
alpar@824:   kruskal(GR const& G, IN const& in, 
alpar@824: 		 OUT& out)
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: 
alpar@810:     NodeIntMap comp(G, -1);
alpar@810:     UnionFind<Node,NodeIntMap> uf(comp); 
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@810:       if ( uf.join(G.head((*p).first),
alpar@810: 		   G.tail((*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@810:   /* A work-around for running Kruskal with const-reference bool maps... */
alpar@810: 
alpar@812:   ///\bug What is this? Or why doesn't it work?
alpar@810:   ///
alpar@824:   template<class Map>
alpar@810:   class NonConstMapWr {
alpar@810:     const Map &m;
alpar@810:   public:
alpar@810:     typedef typename Map::ValueType ValueType;
alpar@810: 
alpar@810:     NonConstMapWr(const Map &_m) : m(_m) {}
alpar@810: 
alpar@824:     template<class KeyType>
alpar@810:     void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
alpar@810:   };
alpar@810: 
alpar@824:   template <class GR, class IN, class OUT>
alpar@810:   inline
alpar@824:   typename IN::ValueType
alpar@824:   kruskal(GR const& G, IN const& edges, 
alpar@824: 	  OUT const& out_map)
alpar@810:   {
alpar@824:     NonConstMapWr<OUT> map_wr(out_map);
alpar@810:     return kruskal(G, edges, map_wr);
alpar@810:   }  
alpar@810: 
alpar@810:   /* ** ** Input-objects ** ** */
alpar@810: 
alpar@810:   /// Kruskal input source.
alpar@810: 
alpar@810:   /// Kruskal input source.
alpar@810:   ///
alpar@810:   /// In most cases you possibly want to use the \ref kruskalEdgeMap() 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@810: 				    typename Map::ValueType> > {
alpar@810:     
alpar@810:   public:
alpar@824:     typedef std::vector< std::pair<typename GR::Edge,
alpar@810: 				   typename Map::ValueType> > 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@810:   public:
alpar@810: 
alpar@810:     void sort() {
alpar@810:       std::sort(this->begin(), this->end(), comparePair());
alpar@810:     }
alpar@810: 
alpar@824:     KruskalMapInput(GR const& G, Map const& m) {
alpar@824:       typedef typename GR::EdgeIt EdgeIt;
alpar@810:       
alpar@810:       this->clear();
alpar@810:       for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
alpar@810:       sort();
alpar@810:     }
alpar@810:   };
alpar@810: 
alpar@810:   /// Creates a KruskalMapInput object for \ref kruskal()
alpar@810: 
alpar@810:   /// It makes is 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@810:   /// want to use the function kruskalEdgeMap() instead.
alpar@810:   ///
alpar@810:   ///\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@824:   KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
alpar@810:   {
alpar@824:     return KruskalMapInput<GR,Map>(G,m);
alpar@810:   }
alpar@810:   
alpar@810:   
alpar@810:   /* ** ** Output-objects: simple writable bool maps** ** */
alpar@810:   
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".
alpar@810:   /// \warning Not a regular property map, as it doesn't know its KeyType
alpar@810:   /// \bug Missing documentation.
alpar@810:   /// \todo This class may be of wider usage, therefore it could move to
alpar@810:   /// <tt>maps.h</tt>
alpar@824:   template<class Iterator>
alpar@810:   class SequenceOutput {
alpar@810:     mutable Iterator it;
alpar@810: 
alpar@810:   public:
alpar@810:     typedef bool ValueType;
alpar@810: 
alpar@810:     SequenceOutput(Iterator const &_it) : it(_it) {}
alpar@810: 
alpar@810:     template<typename KeyType>
alpar@810:     void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
alpar@810:   };
alpar@810: 
alpar@824:   template<class Iterator>
alpar@810:   inline
alpar@810:   SequenceOutput<Iterator>
alpar@810:   makeSequenceOutput(Iterator it) {
alpar@810:     return SequenceOutput<Iterator>(it);
alpar@810:   }
alpar@810: 
alpar@810:   /* ** ** Wrapper funtions ** ** */
alpar@810: 
alpar@810: 
alpar@810:   /// \brief Wrapper function to kruskal().
alpar@810:   /// Input is from an edge map, output is a plain bool map.
alpar@810:   ///
alpar@810:   /// Wrapper function to kruskal().
alpar@810:   /// Input is from an edge map, output is a plain bool map.
alpar@810:   ///
alpar@810:   ///\param G The type of the graph the algorithm runs on.
alpar@810:   ///\param in 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:   /// \retval out This must 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@810:   ///
alpar@810:   /// \return The cost of the found tree.
alpar@810: 
alpar@810: 
alpar@824:   template <class GR, class IN, class RET>
alpar@810:   inline
alpar@824:   typename IN::ValueType
alpar@824:   kruskalEdgeMap(GR const& G,
alpar@824: 		 IN const& in,
alpar@824: 		 RET &out) {
alpar@810:     return kruskal(G,
alpar@824: 		   KruskalMapInput<GR,IN>(G,in),
alpar@810: 		   out);
alpar@810:   }
alpar@810: 
alpar@810:   /// \brief Wrapper function to kruskal().
alpar@810:   /// Input is from an edge map, output is an STL Sequence.
alpar@810:   ///
alpar@810:   /// Wrapper function to kruskal().
alpar@810:   /// Input is from an edge map, output is an STL Sequence.
alpar@810:   ///
alpar@810:   ///\param G The type of the graph the algorithm runs on.
alpar@810:   ///\param in 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:   /// \retval out This must be an iteraror of an STL Container with
alpar@824:   /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
alpar@810:   /// The algorithm copies the elements of the found tree into this sequence.
alpar@810:   /// For example, if we know that the spanning tree of the graph \c G has
alpar@810:   /// say 53 edges then
alpar@824:   /// we can put its edges into a STL vector \c tree with a code like this.
alpar@810:   /// \code
alpar@810:   /// std::vector<Edge> tree(53);
alpar@810:   /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
alpar@810:   /// \endcode
alpar@810:   /// Or if we don't know in advance the size of the tree, we can write this.
alpar@810:   /// \code
alpar@810:   /// std::vector<Edge> tree;
alpar@810:   /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
alpar@810:   /// \endcode
alpar@810:   ///
alpar@810:   /// \return The cost of the found tree.
alpar@810:   ///
alpar@810:   /// \bug its name does not follow the coding style.
alpar@824:   template <class GR, class IN, class RET>
alpar@810:   inline
alpar@824:   typename IN::ValueType
alpar@824:   kruskalEdgeMap_IteratorOut(const GR& G,
alpar@824: 			     const IN& in,
alpar@824: 			     RET out)
alpar@810:   {
alpar@824:     SequenceOutput<RET> _out(out);
alpar@810:     return kruskal(G,
alpar@824: 		   KruskalMapInput<GR,IN>(G, in),
alpar@810: 		   _out);
alpar@810:   }
alpar@810: 
alpar@810:   /// @}
alpar@810: 
alpar@810: } //namespace hugo
alpar@810: 
alpar@810: #endif //HUGO_KRUSKAL_H