source: lemon-0.x/src/hugo/kruskal.h @ 901:69a8e672acb1

// -*- 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<GR::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 <class GR, class IN, class OUT>
  typename IN::value_type::second_type
  kruskal(GR const& G, IN const& in, 
                 OUT& out)
  {
    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.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... */

  /// 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::ValueType ValueType;

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

    template<class KeyType>
    void set(KeyType const& k, ValueType 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)
  {
    NonConstMapWr<OUT> 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 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::ValueType> > {
    
  public:
    typedef std::vector< std::pair<typename GR::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(GR const& G, Map const& m) {
      typedef typename GR::EdgeIt EdgeIt;
      
      for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(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<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 KeyType

  template<class Iterator>
  class KruskalSequenceOutput {
    mutable Iterator it;

  public:
    typedef bool ValueType;

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

    template<typename KeyType>
    void set(KeyType 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::ValueType
  kruskalEdgeMap(GR const& G,
                 IN const& in,
                 RET &out) {
    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);
  /// 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 <class GR, class IN, class RET>
  inline
  typename IN::ValueType
  kruskalEdgeMap_IteratorOut(const GR& G,
                             const IN& in,
                             RET out)
  {
    KruskalSequenceOutput<RET> _out(out);
    return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
  }

  /// @}

} //namespace hugo

#endif //HUGO_KRUSKAL_H