source: lemon-0.x/src/work/johanna/kruskal.h @ 331:f5461f8bc59b

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

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

namespace hugo {

  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
  typename EdgeCostMap::ValueType
  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
           RetEdgeBoolMap &ret_bool_map);

  template <typename Graph, typename EdgeCostMap, typename RetIterator>
  typename EdgeCostMap::ValueType
  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
           RetIterator ret_iterator);

  // FIXME: ret_iterator nem lehet referencia!!!

  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
  typename EdgeCostPairVec::value_type::second_type
  kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
           RetEdgeBoolMap &ret_bool_map);

  template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
  typename EdgeCostPairVec::value_type::second_type
  kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
           RetIterator &ret_iterator);

  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
  int
  kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
           RetEdgeBoolMap &ret_bool_map);

  template <typename Graph, typename EdgePairVec, typename RetIterator>
  int
  kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
           RetIterator &ret_iterator);


  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
            typename RetIterator>
  typename EdgeCostMap::ValueType
  kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);

  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
            typename RetIterator>
  typename EdgeCostPairVec::value_type::second_type
  kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);

  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
            typename RetIterator>
  int
  kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);




  template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
  class MinCostTreeKruskal
  {

    typedef typename Graph::EdgeIt EdgeIt;
    typedef typename Graph::Edge Edge;

  public:
    typedef typename InputEdgeOrder::ValueType EdgeCost;
    
  private:
    Graph const &G;
    InputEdgeOrder const &edges;
    OutputObserver &out_obs;

  public:


    MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, 
                       OutputObserver& _out_obs) : 
      G(_G), edges(_edges), out_obs(_out_obs) {}
  

    EdgeCost run()
    {
      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.joinComponents(G.head(edges.first(p)),
                               G.tail(edges.first(p))) ) {
          out_obs.setTrue(edges.first(p));
          tot_cost += edges.second(p);
        }
        else {
          out_obs.setFalse(edges.first(p));
        }
      }
      return tot_cost;
    }

  };

  
  /* ** ** Output-objektumok (Observerek (?)) ** ** */
  
  template <typename BoolMap>
  class BoolMapOutput {
    BoolMap &bm;
    typedef typename BoolMap::KeyType KeyType;

  public:
    BoolMapOutput(BoolMap &_bm) : bm(_bm) {}

    void setTrue(KeyType const& k) { bm.set(k, true); }
    void setFalse(KeyType const& k) { bm.set(k, false); }
  };

  template <typename Iterator>
  class SequenceOutput {
    Iterator &it;

  public:
    SequenceOutput(Iterator &_it) : it(_it) {}

    template<typename KeyType>
    void setTrue(KeyType const& k) { *it=k; ++it; }
    template<typename KeyType>
    void setFalse(KeyType const& k) {}
  };

  template <typename BoolMap, typename Iterator>
  class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
    typedef BoolMapOutput<BoolMap> BMO;
    typedef SequenceOutput<Iterator> SO;
  public:
    CombinedOutput(BoolMap &_bm, Iterator &_it) :
      BMO(_bm), SO(_it) {}

    template<typename KeyType>
    void setTrue(KeyType const& k) {
      BMO::setTrue(k); 
      SO::setTrue(k);
    }
    template<typename KeyType>
    void setFalse(KeyType const& k) {
      BMO::setFalse(k); 
      SO::setFalse(k);      
    }
  };


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

  template<typename Key, typename Val>
  class PairVec : 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?
    // PairVec(Parent const& p) : Parent(p) {}
    
    void sort() {
      std::sort(begin(), end(), comparePair());
    }

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

      clear();
      for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
        push_back(make_pair(e, m[e]));
      }

      sort();
    }

    int alma() { return 5; /* FIXME */ }

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

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

  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
  typename EdgeCostMap::ValueType
  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
           RetEdgeBoolMap &ret_bool_map) {
    typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
    OutObs out(ret_bool_map);

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

    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
    return mctk.run();
  }

  template <typename Graph, typename EdgeCostMap, typename RetIterator>
  typename EdgeCostMap::ValueType
  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
           RetIterator ret_iterator) {
    typedef SequenceOutput<RetIterator> OutObs;
    OutObs out(ret_iterator);

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

    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
    return mctk.run();    
  }


} //namespace hugo

#endif //HUGO_KRUSKAL_H