source: lemon-0.x/src/work/johanna/kruskal.h @ 756:c54cf1e83039

// -*- c++ -*- //
#ifndef HUGO_KRUSKAL_H
#define HUGO_KRUSKAL_H

#include <algorithm>
#include <hugo/unionfind.h>

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

namespace hugo {

  /// 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.
  /// \param in This object is used to describe the edge costs. It must
  /// be an STL 'forward container'
  /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
  /// where X is the type of the costs. It must contain every edge in
  /// cost-ascending order.
  /// \retval out This must be a writeable EdgeMap. 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.\n
  /// For the sake of simplicity, there is a helper class KruskalPairVec,
  /// which converts a
  /// simple EdgeMap 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 EdgeMap.
  /// \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... */

  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);
  }  

  
  /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
  
  /// 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

  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);
  }

  /* ** ** InputSource -ok ** ** */

  /// Kruskal input source.

  /// Kruskal input source.
  ///
  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;
//     typedef Key KeyType;
//     typedef Val ValueType;
//     typedef std::pair<Key,Val> PairType;
//     typedef typename Parent::iterator iterator;
//     typedef typename Parent::const_iterator const_iterator;

  private:
    class comparePair {
    public:
      bool operator()(const value_type& a,
                      const value_type& b) {
        return a.second < b.second;
      }
    };

  public:

    // FIXME: kell ez?
    // KruskalMapInput(Parent const& p) : Parent(p) {}
    
    void sort() {
      std::sort(this->begin(), this->end(), comparePair());
    }

    // FIXME: nem nagyon illik ez ide...
    KruskalMapInput(Graph const& G, Map const& m) {
      typedef typename Graph::EdgeIt EdgeIt;
      
      this->clear();
      for(EdgeIt e(G);G.valid(e);G.next(e)) {
        // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
        push_back(make_pair(e, m[e]));
      }
      sort();
    }

//     Key const& first(const_iterator i) const { return i->first; }
//     Key& first(iterator i) { return i->first; }

//     Val const& second(const_iterator i) const { return i->second; }
//     Val& second(iterator i) { return i->second; }
  };


//   template<typename Graph, typename Map>
//   class KruskalMapVec {
//   public:
    
//     typedef std::pair<typename Map::KeyType, Map::ValueType> value_type;
    
//     typedef std::vector<KeyType> Container;
//     Container container;
//     std::vector<typename Map::KeyType> container
//     const Map &m;
    
    
//     class iterator
//     {
//       Container::iterator i;
//     public:
//       iterator &operator ++() {++i;return *this;}
//       valuetype operator *() {return value_type(container(i),m[container(i)]);}
//       bool operator==(iterator b) {return i==b.i;}
//       iterator() {}
//       iterator(Container::iterator _i) i(_i) {}
//     };
//     class const_iterator
//     {
//       Container::const_iterator i;
//     public:
//       iterator &operator ++() {++i;return *this;}
//       valuetype operator *() {return value_type(container(i),m[container(i)]);}
//       bool operator==(iterator b) {return i==b.i;}
//       const_iterator() {}
//       const_iterator(Container::iterator _i) i(_i) {}
//     };

//     iterator begin() { return iterator(container.begin());}
//     const_iterator begin() const { return iterator(container.begin());}
//     iterator end() { return iterator(container.end());}
//     const_iterator end() const { return iterator(container.end());}
    
//   private:
    
//     class compareKeys {
//       const Map &m;
//     public:
//       compareKeys(Map const &_m) : m(_m) {}
//       bool operator()(KeyType const& a, KeyType const& b) {
//      return m[a] < m[b];
//       }
//     };

//   public:

//     KruskalMapVec(Map const& _m) : m(_m) {}

//     void sort() {
//       std::sort(begin(), end(), compareKeys(m));
//     }

//     // FIXME: nem nagyon illik ez ide...
//     template<typename Graph>
//     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
//       typedef typename Graph::EdgeIt EdgeIt;

//       clear();
//       for(EdgeIt e(G);G.valid(e);G.next(e)) {
//       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) 
//      push_back(e);
//       }
//       sort();
//     }

//     KeyType const& first(const_iterator i) const { return *i; }
//     KeyType& first(iterator i) { return *i; }

//     ValueType const& second(const_iterator i) const { return m[*i]; }
//     ValueType& second(iterator i) { return m[*i]; }
//   };


  /* ** ** Wrapper fuggvenyek ** ** */


  /// \brief Wrapper to Kruskal().
  /// Input is from an EdgeMap, output is a plain boolmap.

  ///\todo some more words would be nice here.
  ///
  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
  inline
  typename EdgeCostMap::ValueType
  kruskalEdgeMap(Graph const& G,
                        EdgeCostMap const& edge_costs,
                        RetEdgeBoolMap &ret_bool_map) {
    
    typedef KruskalMapInput<Graph,EdgeCostMap> InputVec;
    
    InputVec iv(G, edge_costs);
    return kruskal(G, iv, ret_bool_map);
  }


  /// \brief Wrapper to Kruskal().
  /// Input is from an EdgeMap, output is to a sequence.

  ///\todo it does not follow the naming convention.
  ///
  template <typename Graph, typename EdgeCostMap, typename RetIterator>
  inline
  typename EdgeCostMap::ValueType
  kruskalEdgeMap_IteratorOut(const Graph& G,
                             const EdgeCostMap& edge_costs,
                             RetIterator ret_iterator)
  {
    typedef typename EdgeCostMap::ValueType ValueType;
    
    typedef SequenceOutput<RetIterator> OutMap;
    OutMap out(ret_iterator);

    typedef KruskalMapInput<Graph, EdgeCostMap> InputVec;

    InputVec iv(G, edge_costs);

    return kruskal(G, iv, out);
  }


} //namespace hugo

#endif //HUGO_KRUSKAL_H