source: lemon-0.x/src/work/johanna/kruskal.h @ 691:014c2e4eb07b

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

#include <algorithm>
#include <unionfind.h>
#include <for_each_macros.h>

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

namespace hugo {

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

  template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
  typename InputEdgeOrder::ValueType
  Kruskal(Graph const& G, InputEdgeOrder const& edges, 
          OutBoolMap& out_map)
  {
    typedef typename InputEdgeOrder::ValueType EdgeCost;
    typedef typename Graph::NodeMap<int> NodeIntMap;
    typedef typename Graph::Node Node;

    NodeIntMap comp_map(G, -1);
    UnionFind<Node,NodeIntMap> uf(comp_map); 
      
    EdgeCost tot_cost = 0;
    for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
         p!=edges.end(); ++p ) {
      if ( uf.join(G.head(edges.first(p)),
                             G.tail(edges.first(p))) ) {
        out_map.set(edges.first(p), true);
        tot_cost += edges.second(p);
      }
      else {
        out_map.set(edges.first(p), 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 receive
  /// 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 ** ** */

  template<typename Key, typename Val>
  class KruskalPairVec : public std::vector< std::pair<Key,Val> > {

  public:
    typedef std::vector< std::pair<Key,Val> > Parent;
    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()(PairType const& a, PairType const& b) {
        return a.second < b.second;
      }
    };

  public:

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

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

      clear();
      FOR_EACH_LOC(EdgeIt, e, G) {
      // 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 Map>
  class KruskalMapVec : public std::vector<typename Map::KeyType> {
  public:

    typedef typename Map::KeyType KeyType;
    typedef typename Map::ValueType ValueType;

    typedef typename std::vector<KeyType> Parent;
    typedef typename Parent::iterator iterator;
    typedef typename Parent::const_iterator const_iterator;

  private:

    const Map &m;

    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_EACH_LOC(EdgeIt, e, G) {
      // 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.
  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
  inline
  typename EdgeCostMap::ValueType
  Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
                                   EdgeCostMap const& edge_costs,
                                   RetEdgeBoolMap &ret_bool_map) {

    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
      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.
  template <typename Graph, typename EdgeCostMap, typename RetIterator>
  inline
  typename EdgeCostMap::ValueType
  Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
                                    EdgeCostMap const& edge_costs,
                                    RetIterator ret_iterator) {
    typedef SequenceOutput<RetIterator> OutMap;
    OutMap out(ret_iterator);

    typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
      InputVec;
    InputVec iv(G, edge_costs);

    return Kruskal(G, iv, out);
  }


} //namespace hugo

#endif //HUGO_KRUSKAL_H