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

/**

@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.

///

///\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 concept::StaticGraph "directed" or 

  /// \ref concept::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.

  /// - Is 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 a 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 is run on an

  /// \ref lemon::concept::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, -1);

    UnionFind<Node,NodeIntMap> uf(comp); 

    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 a 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