beckerjc@150: // -*- c++ -*- //
beckerjc@150: #ifndef HUGO_KRUSKAL_H
beckerjc@150: #define HUGO_KRUSKAL_H
beckerjc@150: 
beckerjc@150: #include "unionfind.h"
beckerjc@150: #include <algorithm>
beckerjc@150: 
beckerjc@150: namespace hugo {
beckerjc@150: 
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
beckerjc@246:   typename EdgeCostMap::ValueType
beckerjc@246:   kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
beckerjc@246: 	   RetEdgeBoolMap &ret_bool_map);
beckerjc@150: 
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetIterator>
beckerjc@246:   typename EdgeCostMap::ValueType
beckerjc@246:   kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
beckerjc@246: 	   RetIterator ret_iterator);
beckerjc@246: 
beckerjc@246:   // FIXME: ret_iterator nem lehet referencia!!!
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
beckerjc@246:   typename EdgeCostPairVec::value_type::second_type
beckerjc@246:   kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
beckerjc@246: 	   RetEdgeBoolMap &ret_bool_map);
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
beckerjc@246:   typename EdgeCostPairVec::value_type::second_type
beckerjc@246:   kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
beckerjc@246: 	   RetIterator &ret_iterator);
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
beckerjc@246:   int
beckerjc@246:   kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
beckerjc@246: 	   RetEdgeBoolMap &ret_bool_map);
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgePairVec, typename RetIterator>
beckerjc@246:   int
beckerjc@246:   kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
beckerjc@246: 	   RetIterator &ret_iterator);
beckerjc@246: 
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
beckerjc@246: 	    typename RetIterator>
beckerjc@246:   typename EdgeCostMap::ValueType
beckerjc@246:   kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
beckerjc@246: 	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
beckerjc@246: 	    typename RetIterator>
beckerjc@246:   typename EdgeCostPairVec::value_type::second_type
beckerjc@246:   kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
beckerjc@246: 	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
beckerjc@246: 	    typename RetIterator>
beckerjc@246:   int
beckerjc@246:   kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
beckerjc@246: 	   RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
beckerjc@246: 
beckerjc@246: 
beckerjc@246: 
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
beckerjc@218:   class MinCostTreeKruskal
beckerjc@218:   {
beckerjc@150: 
beckerjc@218:     typedef typename Graph::EdgeIt EdgeIt;
beckerjc@218:     typedef typename Graph::Edge Edge;
beckerjc@150: 
beckerjc@218:   public:
beckerjc@246:     typedef typename InputEdgeOrder::ValueType EdgeCost;
beckerjc@150:     
beckerjc@218:   private:
beckerjc@218:     Graph const &G;
beckerjc@246:     InputEdgeOrder const &edges;
beckerjc@246:     OutputObserver &out_obs;
beckerjc@150: 
beckerjc@218:   public:
beckerjc@150: 
beckerjc@150: 
beckerjc@246:     MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, 
beckerjc@246: 		       OutputObserver& _out_obs) : 
beckerjc@246:       G(_G), edges(_edges), out_obs(_out_obs) {}
beckerjc@218:   
beckerjc@218: 
beckerjc@246:     EdgeCost run()
beckerjc@218:     {
beckerjc@218:       typedef typename Graph::NodeMap<int> NodeIntMap;
beckerjc@218:       typedef typename Graph::Node Node;
beckerjc@218:       NodeIntMap comp_map(G, -1);
beckerjc@218:       UnionFind<Node,NodeIntMap> uf(comp_map); 
beckerjc@218:       
beckerjc@218:       EdgeCost tot_cost = 0;
beckerjc@246:       for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
beckerjc@246: 	   p!=edges.end(); ++p ) {
beckerjc@246: 	if ( uf.joinComponents(G.head(edges.first(p)),
beckerjc@246: 			       G.tail(edges.first(p))) ) {
beckerjc@246: 	  out_obs.setTrue(edges.first(p));
beckerjc@246: 	  tot_cost += edges.second(p);
beckerjc@218: 	}
beckerjc@218: 	else {
beckerjc@246: 	  out_obs.setFalse(edges.first(p));
beckerjc@218: 	}
beckerjc@218:       }
beckerjc@218:       return tot_cost;
beckerjc@218:     }
beckerjc@150: 
beckerjc@218:   };
beckerjc@150: 
beckerjc@246:   
beckerjc@246:   /* ** ** Output-objektumok (Observerek (?)) ** ** */
beckerjc@246:   
beckerjc@246:   template <typename BoolMap>
beckerjc@246:   class BoolMapOutput {
beckerjc@246:     BoolMap &bm;
beckerjc@246:     typedef typename BoolMap::KeyType KeyType;
beckerjc@246: 
beckerjc@246:   public:
beckerjc@246:     BoolMapOutput(BoolMap &_bm) : bm(_bm) {}
beckerjc@246: 
beckerjc@246:     void setTrue(KeyType const& k) { bm.set(k, true); }
beckerjc@246:     void setFalse(KeyType const& k) { bm.set(k, false); }
beckerjc@246:   };
beckerjc@246: 
beckerjc@246:   template <typename Iterator>
beckerjc@246:   class SequenceOutput {
beckerjc@246:     Iterator &it;
beckerjc@246: 
beckerjc@246:   public:
beckerjc@246:     SequenceOutput(Iterator &_it) : it(_it) {}
beckerjc@246: 
beckerjc@246:     template<typename KeyType>
beckerjc@246:     void setTrue(KeyType const& k) { *it=k; ++it; }
beckerjc@246:     template<typename KeyType>
beckerjc@246:     void setFalse(KeyType const& k) {}
beckerjc@246:   };
beckerjc@246: 
beckerjc@246:   template <typename BoolMap, typename Iterator>
beckerjc@246:   class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
beckerjc@246:     typedef BoolMapOutput<BoolMap> BMO;
beckerjc@246:     typedef SequenceOutput<Iterator> SO;
beckerjc@246:   public:
beckerjc@246:     CombinedOutput(BoolMap &_bm, Iterator &_it) :
beckerjc@246:       BMO(_bm), SO(_it) {}
beckerjc@246: 
beckerjc@246:     template<typename KeyType>
beckerjc@246:     void setTrue(KeyType const& k) {
beckerjc@246:       BMO::setTrue(k); 
beckerjc@246:       SO::setTrue(k);
beckerjc@246:     }
beckerjc@246:     template<typename KeyType>
beckerjc@246:     void setFalse(KeyType const& k) {
beckerjc@246:       BMO::setFalse(k); 
beckerjc@246:       SO::setFalse(k);      
beckerjc@246:     }
beckerjc@246:   };
beckerjc@246: 
beckerjc@246: 
beckerjc@246:   /* ** ** InputSource -ok ** ** */
beckerjc@246: 
beckerjc@246:   template<typename Key, typename Val>
beckerjc@246:   class PairVec : public std::vector< std::pair<Key,Val> > {
beckerjc@246: 
beckerjc@246:   public:
beckerjc@246:     typedef std::vector< std::pair<Key,Val> > Parent;
beckerjc@246:     typedef Key KeyType;
beckerjc@246:     typedef Val ValueType;
beckerjc@246:     typedef std::pair<Key,Val> PairType;
beckerjc@246: 
beckerjc@246:     typedef typename Parent::iterator iterator;
beckerjc@246:     typedef typename Parent::const_iterator const_iterator;
beckerjc@246: 
beckerjc@246: 
beckerjc@246:   private:
beckerjc@246: 
beckerjc@246:     class comparePair {
beckerjc@246:     public:
beckerjc@246:       bool operator()(PairType const& a, PairType const& b) {
beckerjc@246: 	return a.second < b.second;
beckerjc@246:       }
beckerjc@246:     };
beckerjc@246: 
beckerjc@246:   public:
beckerjc@246: 
beckerjc@246:     // FIXME: kell ez?
beckerjc@246:     // PairVec(Parent const& p) : Parent(p) {}
beckerjc@246:     
beckerjc@246:     void sort() {
beckerjc@246:       std::sort(begin(), end(), comparePair());
beckerjc@246:     }
beckerjc@246: 
beckerjc@246:     // FIXME: nem nagyon illik ez ide...
beckerjc@246:     template<typename Graph, typename Map>
beckerjc@246:     void readGraphEdgeMap(Graph const& G, Map const& m) {
beckerjc@246:       typedef typename Graph::EdgeIt EdgeIt;
beckerjc@246: 
beckerjc@246:       clear();
beckerjc@246:       for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
beckerjc@246: 	push_back(make_pair(e, m[e]));
beckerjc@246:       }
beckerjc@246: 
beckerjc@246:       sort();
beckerjc@246:     }
beckerjc@246: 
beckerjc@246:     int alma() { return 5; /* FIXME */ }
beckerjc@246: 
beckerjc@246:     Key const& first(const_iterator i) const { return i->first; }
beckerjc@246:     Key& first(iterator i) { return i->first; }
beckerjc@246: 
beckerjc@246:     Val const& second(const_iterator i) const { return i->second; }
beckerjc@246:     Val& second(iterator i) { return i->second; }
beckerjc@246:   };
beckerjc@246: 
beckerjc@246:   /* ** ** Wrapper fuggvenyek ** ** */
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
beckerjc@246:   typename EdgeCostMap::ValueType
beckerjc@246:   kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
beckerjc@246: 	   RetEdgeBoolMap &ret_bool_map) {
beckerjc@246:     typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
beckerjc@246:     OutObs out(ret_bool_map);
beckerjc@246: 
beckerjc@246:     typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
beckerjc@246:       InputVec;
beckerjc@246:     InputVec iv;
beckerjc@246:     iv.readGraphEdgeMap(G, edge_costs);
beckerjc@246: 
beckerjc@246:     MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
beckerjc@246:     return mctk.run();
beckerjc@246:   }
beckerjc@246: 
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetIterator>
beckerjc@246:   typename EdgeCostMap::ValueType
beckerjc@246:   kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
beckerjc@246: 	   RetIterator ret_iterator) {
beckerjc@246:     typedef SequenceOutput<RetIterator> OutObs;
beckerjc@246:     OutObs out(ret_iterator);
beckerjc@246: 
beckerjc@246:     typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
beckerjc@246:       InputVec;
beckerjc@246:     InputVec iv;
beckerjc@246:     iv.readGraphEdgeMap(G, edge_costs);
beckerjc@246: 
beckerjc@246:     MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
beckerjc@246:     return mctk.run();    
beckerjc@246:   }
beckerjc@246: 
beckerjc@150: 
beckerjc@150: } //namespace hugo
beckerjc@150: 
beckerjc@150: #endif //HUGO_KRUSKAL_H