// -*- 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