// -*- c++ -*- //

 #ifndef HUGO_KRUSKAL_H

 #define HUGO_KRUSKAL_H

 #include <algorithm>

 #include <hugo/unionfind.h>

 /**

 @defgroup spantree Minimum Cost Spanning Tree Algorithms

 @ingroup galgs

 \brief This group containes the algorithms for finding a minimum cost spanning

 tree in a graph

 This group containes the algorithms for finding a minimum cost spanning

 tree in a graph

 */

 ///\ingroup spantree

 ///\file

 ///\brief Kruskal's algorithm to compute a minimum cost tree

 ///

 ///Kruskal's algorithm to compute a minimum cost tree.

 namespace hugo {

   /// \addtogroup spantree

   /// @{

   /// Kruskal's algorithm to find a minimum cost tree of a graph.

   /// This function runs Kruskal's algorithm to find a minimum cost tree.

   /// \param G The graph the algorithm runs on. The algorithm considers the

   /// graph to be undirected, the direction of the edges are not used.

   ///

   /// \param in This object is used to describe the edge costs. It must

   /// be an STL compatible 'Forward Container'

   /// with <tt>std::pair<Graph::Edge,X></tt> as its <tt>value_type</tt>,

   /// where X is the type of the costs. It must contain every edge in

   /// cost-ascending order.

   ///\par

   /// For the sake of simplicity, there is a helper class KruskalMapInput,

   /// which converts a

   /// simple edge map to an input of this form. Alternatively, you can use

   /// the function \ref kruskalEdgeMap to compute the minimum cost tree if

   /// the edge costs are given by an edge map.

   ///

   /// \retval out This must be a writable \c bool edge map.

   /// After running the algorithm

   /// this will contain the found minimum cost spanning tree: the value of an

   /// edge will be set to \c true if it belongs to the tree, otherwise it will

   /// be set to \c false. The value of each edge will be set exactly once.

   ///

   /// \return The cost of the found tree.

   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>

   typename InputEdgeOrder::value_type::second_type

   kruskal(Graph const& G, InputEdgeOrder const& in, 

 		 OutBoolMap& out)

   {

     typedef typename InputEdgeOrder::value_type::second_type EdgeCost;

     typedef typename Graph::template NodeMap<int> NodeIntMap;

     typedef typename Graph::Node Node;

     NodeIntMap comp(G, -1);

     UnionFind<Node,NodeIntMap> uf(comp); 

     EdgeCost tot_cost = 0;

     for (typename InputEdgeOrder::const_iterator p = in.begin(); 

 	 p!=in.end(); ++p ) {

       if ( uf.join(G.head((*p).first),

 		   G.tail((*p).first)) ) {

 	out.set((*p).first, true);

 	tot_cost += (*p).second;

       }

       else {

 	out.set((*p).first, false);

       }

     }

     return tot_cost;

   }

   /* A work-around for running Kruskal with const-reference bool maps... */

   ///\bug What is this? Or why doesn't it work?

   ///

   template<typename Map>

   class NonConstMapWr {

     const Map &m;

   public:

     typedef typename Map::ValueType ValueType;

     NonConstMapWr(const Map &_m) : m(_m) {}

     template<typename KeyType>

     void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }

   };

   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>

   inline

   typename InputEdgeOrder::ValueType

   kruskal(Graph const& G, InputEdgeOrder const& edges, 

 	  OutBoolMap const& out_map)

   {

     NonConstMapWr<OutBoolMap> map_wr(out_map);

     return kruskal(G, edges, map_wr);

   }  

   /* ** ** Input-objects ** ** */

   /// Kruskal input source.

   /// Kruskal input source.

   ///

   /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.

   ///

   /// \sa makeKruskalMapInput()

   ///

   ///\param Graph The type of the graph the algorithm runs on.

   ///\param Map An edge map containing the cost of the edges.

   ///\par

   ///The cost type can be any type satisfying

   ///the STL 'LessThan comparable'

   ///concept if it also has an operator+() implemented. (It is necessary for

   ///computing the total cost of the tree).

   ///

   template<typename Graph, typename Map>

   class KruskalMapInput

     : public std::vector< std::pair<typename Graph::Edge,

 				    typename Map::ValueType> > {

   public:

     typedef std::vector< std::pair<typename Graph::Edge,

 				   typename Map::ValueType> > Parent;

     typedef typename Parent::value_type value_type;

   private:

     class comparePair {

     public:

       bool operator()(const value_type& a,

 		      const value_type& b) {

 	return a.second < b.second;

       }

     };

   public:

     void sort() {

       std::sort(this->begin(), this->end(), comparePair());

     }

     KruskalMapInput(Graph const& G, Map const& m) {

       typedef typename Graph::EdgeIt EdgeIt;

       this->clear();

       for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));

       sort();

     }

   };

   /// Creates a KruskalMapInput object for \ref kruskal()

   /// It makes is easier to use 

   /// \ref KruskalMapInput by making it unnecessary 

   /// to explicitly give the type of the parameters.

   ///

   /// In most cases you possibly

   /// want to use the function kruskalEdgeMap() instead.

   ///

   ///\param G The type of the graph the algorithm runs on.

   ///\param m An edge map containing the cost of the edges.

   ///\par

   ///The cost type can be any type satisfying the

   ///STL 'LessThan Comparable'

   ///concept if it also has an operator+() implemented. (It is necessary for

   ///computing the total cost of the tree).

   ///

   ///\return An appropriate input source for \ref kruskal().

   ///

   template<typename Graph, typename Map>

   inline

   KruskalMapInput<Graph,Map> makeKruskalMapInput(const Graph &G,const Map &m)

   {

     return KruskalMapInput<Graph,Map>(G,m);

   }

   /* ** ** Output-objects: simple writable bool maps** ** */

   /// A writable bool-map that makes a sequence of "true" keys

   /// A writable bool-map that creates a sequence out of keys that receives

   /// the value "true".

   /// \warning Not a regular property map, as it doesn't know its KeyType

   /// \bug Missing documentation.

   /// \todo This class may be of wider usage, therefore it could move to

   /// <tt>maps.h</tt>

   template<typename Iterator>

   class SequenceOutput {

     mutable Iterator it;

   public:

     typedef bool ValueType;

     SequenceOutput(Iterator const &_it) : it(_it) {}

     template<typename KeyType>

     void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }

   };

   template<typename Iterator>

   inline

   SequenceOutput<Iterator>

   makeSequenceOutput(Iterator it) {

     return SequenceOutput<Iterator>(it);

   }

   /* ** ** Wrapper funtions ** ** */

   /// \brief Wrapper function to kruskal().

   /// Input is from an edge map, output is a plain bool map.

   ///

   /// Wrapper function to kruskal().

   /// Input is from an edge map, output is a plain bool map.

   ///

   ///\param G The type of the graph the algorithm runs on.

   ///\param in An edge map containing the cost of the edges.

   ///\par

   ///The cost type can be any type satisfying the

   ///STL 'LessThan Comparable'

   ///concept if it also has an operator+() implemented. (It is necessary for

   ///computing the total cost of the tree).

   ///

   /// \retval out This must be a writable \c bool edge map.

   /// After running the algorithm

   /// this will contain the found minimum cost spanning tree: the value of an

   /// edge will be set to \c true if it belongs to the tree, otherwise it will

   /// be set to \c false. The value of each edge will be set exactly once.

   ///

   /// \return The cost of the found tree.

   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>

   inline

   typename EdgeCostMap::ValueType

   kruskalEdgeMap(Graph const& G,

 		 EdgeCostMap const& in,

 		 RetEdgeBoolMap &out) {

     return kruskal(G,

 		   KruskalMapInput<Graph,EdgeCostMap>(G,in),

 		   out);

   }

   /// \brief Wrapper function to kruskal().

   /// Input is from an edge map, output is an STL Sequence.

   ///

   /// Wrapper function to kruskal().

   /// Input is from an edge map, output is an STL Sequence.

   ///

   ///\param G The type of the graph the algorithm runs on.

   ///\param in An edge map containing the cost of the edges.

   ///\par

   ///The cost type can be any type satisfying the

   ///STL 'LessThan Comparable'

   ///concept if it also has an operator+() implemented. (It is necessary for

   ///computing the total cost of the tree).

   ///

   /// \retval out This must be an iteraror of an STL Container with

   /// <tt>Graph::Edge</tt> as its <tt>value_type</tt>.

   /// The algorithm copies the elements of the found tree into this sequence.

   /// For example, if we know that the spanning tree of the graph \c G has

   /// say 53 edges then

   /// we can put its edges into a vector \c tree with a code like this.

   /// \code

   /// std::vector<Edge> tree(53);

   /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());

   /// \endcode

   /// Or if we don't know in advance the size of the tree, we can write this.

   /// \code

   /// std::vector<Edge> tree;

   /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));

   /// \endcode

   ///

   /// \return The cost of the found tree.

   ///

   /// \bug its name does not follow the coding style.

   template <typename Graph, typename EdgeCostMap, typename RetIterator>

   inline

   typename EdgeCostMap::ValueType

   kruskalEdgeMap_IteratorOut(const Graph& G,

 			     const EdgeCostMap& in,

 			     RetIterator out)

   {

     SequenceOutput<RetIterator> _out(out);

     return kruskal(G,

 		   KruskalMapInput<Graph, EdgeCostMap>(G, in),

 		   _out);

   }

   /// @}

 } //namespace hugo

 #endif //HUGO_KRUSKAL_H