/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2006

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #ifndef LEMON_KRUSKAL_H

 #define LEMON_KRUSKAL_H

 #include <algorithm>

 #include <vector>

 #include <lemon/unionfind.h>

 #include <lemon/bits/utility.h>

 #include <lemon/bits/traits.h>

 ///\ingroup spantree

 ///\file

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

 ///

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

 ///

 ///\todo The file still needs some clean-up.

 namespace lemon {

   /// \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.

   /// Due to hard C++ hacking, it accepts various input and output types.

   ///

   /// \param g The graph the algorithm runs on.

   /// It can be either \ref concepts::Graph "directed" or 

   /// \ref concepts::UGraph "undirected".

   /// If the graph is directed, the algorithm consider it to be 

   /// undirected by disregarding the direction of the edges.

   ///

   /// \param in This object is used to describe the edge costs. It can be one

   /// of the following choices.

   /// - An STL compatible 'Forward Container'

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

   /// where \c X is the type of the costs. The pairs indicates the edges along

   /// with the assigned cost. <em>They must be in a

   /// cost-ascending order.</em>

   /// - Any readable Edge map. The values of the map indicate the edge costs.

   ///

   /// \retval out Here we also have a choise.

   /// - It can 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.

   /// - It can also be an iteraror of an STL Container with

   /// <tt>GR::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 an STL vector \c tree with a code like this.

   ///\code

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

   /// kruskal(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;

   /// kruskal(g,cost,std::back_inserter(tree));

   ///\endcode

   ///

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

   ///

   /// \warning If kruskal runs on an

   /// \ref lemon::concepts::UGraph "undirected graph", be sure that the

   /// map storing the tree is also undirected

   /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the

   /// half of the edges will not be set.

   ///

   /// \todo Discuss the case of undirected graphs: In this case the algorithm

   /// also require <tt>Edge</tt>s instead of <tt>UEdge</tt>s, as some

   /// people would expect. So, one should be careful not to add both of the

   /// <tt>Edge</tt>s belonging to a certain <tt>UEdge</tt>.

   /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.)

 #ifdef DOXYGEN

   template <class GR, class IN, class OUT>

   typename IN::value_type::second_type

   kruskal(GR const& g, IN const& in, 

 	  OUT& out)

 #else

   template <class GR, class IN, class OUT>

   typename IN::value_type::second_type

   kruskal(GR const& g, IN const& in, 

 	  OUT& out,

 // 	  typename IN::value_type::first_type = typename GR::Edge()

 // 	  ,typename OUT::Key = OUT::Key()

 // 	  //,typename OUT::Key = typename GR::Edge()

 	  const typename IN::value_type::first_type * = 

 	  (const typename IN::value_type::first_type *)(0),

 	  const typename OUT::Key * = (const typename OUT::Key *)(0)

 	  )

 #endif

   {

     typedef typename IN::value_type::second_type EdgeCost;

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

     typedef typename GR::Node Node;

     NodeIntMap comp(g);

     UnionFind<Node,NodeIntMap> uf(comp);

     for (typename GR::NodeIt it(g); it != INVALID; ++it) {

       uf.insert(it);

     }

     EdgeCost tot_cost = 0;

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

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

       if ( uf.join(g.target((*p).first),

 		   g.source((*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... */

   /// Helper class for calling kruskal with "constant" output map.

   /// Helper class for calling kruskal with output maps constructed

   /// on-the-fly.

   ///

   /// A typical examle is the following call:

   /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.

   /// Here, the third argument is a temporary object (which wraps around an

   /// iterator with a writable bool map interface), and thus by rules of C++

   /// is a \c const object. To enable call like this exist this class and

   /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>

   /// third argument.

   template<class Map>

   class NonConstMapWr {

     const Map &m;

   public:

     typedef typename Map::Key Key;

     typedef typename Map::Value Value;

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

     template<class Key>

     void set(Key const& k, Value const &v) const { m.set(k,v); }

   };

   template <class GR, class IN, class OUT>

   inline

   typename IN::value_type::second_type

   kruskal(GR const& g, IN const& edges, OUT const& out_map,

 // 	  typename IN::value_type::first_type = typename GR::Edge(),

 // 	  typename OUT::Key = GR::Edge()

 	  const typename IN::value_type::first_type * = 

 	  (const typename IN::value_type::first_type *)(0),

 	  const typename OUT::Key * = (const typename OUT::Key *)(0)

 	  )

   {

     NonConstMapWr<OUT> map_wr(out_map);

     return kruskal(g, edges, map_wr);

   }  

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

   /// Kruskal's input source.

   /// Kruskal's input source.

   ///

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

   ///

   /// \sa makeKruskalMapInput()

   ///

   ///\param GR 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<class GR, class Map>

   class KruskalMapInput

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

 				    typename Map::Value> > {

   public:

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

 				   typename Map::Value> > 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;

       }

     };

     template<class _GR>

     typename enable_if<UndirectedTagIndicator<_GR>,void>::type

     fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) 

     {

       for(typename GR::UEdgeIt e(g);e!=INVALID;++e) 

 	push_back(value_type(g.direct(e, true), m[e]));

     }

     template<class _GR>

     typename disable_if<UndirectedTagIndicator<_GR>,void>::type

     fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) 

     {

       for(typename GR::EdgeIt e(g);e!=INVALID;++e) 

 	push_back(value_type(e, m[e]));

     }

   public:

     void sort() {

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

     }

     KruskalMapInput(GR const& g, Map const& m) {

       fillWithEdges(g,m); 

       sort();

     }

   };

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

   /// It makes 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 \ref kruskal() 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<class GR, class Map>

   inline

   KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)

   {

     return KruskalMapInput<GR,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".

   ///

   /// \sa makeKruskalSequenceOutput()

   ///

   /// Very often, when looking for a min cost spanning tree, we want as

   /// output a container containing the edges of the found tree. For this

   /// purpose exist this class that wraps around an STL iterator with a

   /// writable bool map interface. When a key gets value "true" this key

   /// is added to sequence pointed by the iterator.

   ///

   /// A typical usage:

   ///\code

   /// std::vector<Graph::Edge> v;

   /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));

   ///\endcode

   /// 

   /// For the most common case, when the input is given by a simple edge

   /// map and the output is a sequence of the tree edges, a special

   /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().

   ///

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

   template<class Iterator>

   class KruskalSequenceOutput {

     mutable Iterator it;

   public:

     typedef typename std::iterator_traits<Iterator>::value_type Key;

     typedef bool Value;

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

     template<typename Key>

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

   };

   template<class Iterator>

   inline

   KruskalSequenceOutput<Iterator>

   makeKruskalSequenceOutput(Iterator it) {

     return KruskalSequenceOutput<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 <class GR, class IN, class RET>

   inline

   typename IN::Value

   kruskal(GR const& g,

 	  IN const& in,

 	  RET &out,

 	  //	  typename IN::Key = typename GR::Edge(),

 	  //typename IN::Key = typename IN::Key (),

 	  //	  typename RET::Key = typename GR::Edge()

 	  const typename IN::Key *  = (const typename IN::Key *)(0),

 	  const typename RET::Key * = (const typename RET::Key *)(0)

 	  )

   {

     return kruskal(g,

 		   KruskalMapInput<GR,IN>(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>GR::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 an STL vector \c tree with a code like this.

 //\code

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

 //   kruskal(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;

 //   kruskal(g,cost,std::back_inserter(tree));

 //\endcode

 //  

 //   \return The cost of the found tree.

 //  

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

   template <class GR, class IN, class RET>

   inline

   typename IN::Value

   kruskal(const GR& g,

 	  const IN& in,

 	  RET out,

 	  const typename RET::value_type * = 

 	  (const typename RET::value_type *)(0)

 	  )

   {

     KruskalSequenceOutput<RET> _out(out);

     return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);

   }

   template <class GR, class IN, class RET>

   inline

   typename IN::Value

   kruskal(const GR& g,

 	  const IN& in,

 	  RET *out

 	  )

   {

     KruskalSequenceOutput<RET*> _out(out);

     return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);

   }

   /// @}

 } //namespace lemon

 #endif //LEMON_KRUSKAL_H