beckerjc@150: // -*- c++ -*- //
beckerjc@150: #ifndef HUGO_KRUSKAL_H
beckerjc@150: #define HUGO_KRUSKAL_H
beckerjc@150: 
beckerjc@150: #include <algorithm>
beckerjc@349: #include <unionfind.h>
beckerjc@349: #include <for_each_macros.h>
beckerjc@150: 
alpar@682: ///\file
alpar@682: ///\brief Kruskal's algorithm to compute a minimum cost tree
alpar@682: 
beckerjc@150: namespace hugo {
beckerjc@150: 
beckerjc@349:   /// Kruskal's algorithm to compute a minimum cost tree
beckerjc@150: 
beckerjc@349:   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
beckerjc@349:   typename InputEdgeOrder::ValueType
beckerjc@349:   Kruskal(Graph const& G, InputEdgeOrder const& edges, 
beckerjc@349: 	  OutBoolMap& out_map)
beckerjc@349:   {
beckerjc@349:     typedef typename InputEdgeOrder::ValueType EdgeCost;
beckerjc@349:     typedef typename Graph::NodeMap<int> NodeIntMap;
beckerjc@349:     typedef typename Graph::Node Node;
beckerjc@246: 
beckerjc@349:     NodeIntMap comp_map(G, -1);
beckerjc@349:     UnionFind<Node,NodeIntMap> uf(comp_map); 
beckerjc@349:       
beckerjc@349:     EdgeCost tot_cost = 0;
beckerjc@349:     for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
beckerjc@349: 	 p!=edges.end(); ++p ) {
beckerjc@394:       if ( uf.join(G.head(edges.first(p)),
beckerjc@349: 			     G.tail(edges.first(p))) ) {
beckerjc@349: 	out_map.set(edges.first(p), true);
beckerjc@349: 	tot_cost += edges.second(p);
beckerjc@349:       }
beckerjc@349:       else {
beckerjc@349: 	out_map.set(edges.first(p), false);
beckerjc@349:       }
beckerjc@349:     }
beckerjc@349:     return tot_cost;
beckerjc@349:   }
beckerjc@246: 
beckerjc@352:   /* A work-around for running Kruskal with const-reference bool maps... */
beckerjc@352: 
beckerjc@352:   template<typename Map>
beckerjc@352:   class NonConstMapWr {
beckerjc@352:     const Map &m;
beckerjc@352:   public:
beckerjc@352:     typedef typename Map::ValueType ValueType;
beckerjc@352: 
beckerjc@352:     NonConstMapWr(const Map &_m) : m(_m) {}
beckerjc@352: 
beckerjc@352:     template<typename KeyType>
beckerjc@352:     void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
beckerjc@352:   };
beckerjc@352: 
beckerjc@352:   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
beckerjc@352:   inline
beckerjc@352:   typename InputEdgeOrder::ValueType
beckerjc@352:   Kruskal(Graph const& G, InputEdgeOrder const& edges, 
beckerjc@352: 	  OutBoolMap const& out_map)
beckerjc@352:   {
beckerjc@352:     NonConstMapWr<OutBoolMap> map_wr(out_map);
beckerjc@352:     return Kruskal(G, edges, map_wr);
beckerjc@352:   }  
beckerjc@246: 
beckerjc@349:   
beckerjc@349:   /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
beckerjc@349:   
beckerjc@349:   /// A writable bool-map that makes a sequence of "true" keys
beckerjc@246: 
beckerjc@349:   /// A writable bool-map that creates a sequence out of keys that receive
beckerjc@349:   /// the value "true".
beckerjc@349:   /// \warning Not a regular property map, as it doesn't know its KeyType
beckerjc@246: 
beckerjc@349:   template<typename Iterator>
beckerjc@349:   class SequenceOutput {
beckerjc@352:     mutable Iterator it;
beckerjc@150: 
beckerjc@218:   public:
beckerjc@349:     typedef bool ValueType;
beckerjc@150: 
beckerjc@349:     SequenceOutput(Iterator const &_it) : it(_it) {}
beckerjc@150: 
beckerjc@349:     template<typename KeyType>
beckerjc@352:     void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
beckerjc@218:   };
beckerjc@150: 
beckerjc@349:   template<typename Iterator>
beckerjc@349:   inline
beckerjc@349:   SequenceOutput<Iterator>
beckerjc@349:   makeSequenceOutput(Iterator it) {
beckerjc@349:     return SequenceOutput<Iterator>(it);
beckerjc@349:   }
beckerjc@246: 
beckerjc@246:   /* ** ** InputSource -ok ** ** */
beckerjc@246: 
beckerjc@246:   template<typename Key, typename Val>
beckerjc@349:   class KruskalPairVec : 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:   private:
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@349:     // KruskalPairVec(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@349:     KruskalPairVec(Graph const& G, Map const& m) {
beckerjc@246:       typedef typename Graph::EdgeIt EdgeIt;
beckerjc@246: 
beckerjc@246:       clear();
beckerjc@349:       FOR_EACH_LOC(EdgeIt, e, G) {
beckerjc@349:       // 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:       sort();
beckerjc@246:     }
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@349: 
beckerjc@349:   template <typename Map>
beckerjc@349:   class KruskalMapVec : public std::vector<typename Map::KeyType> {
beckerjc@349:   public:
beckerjc@349: 
beckerjc@349:     typedef typename Map::KeyType KeyType;
beckerjc@349:     typedef typename Map::ValueType ValueType;
beckerjc@349: 
beckerjc@349:     typedef typename std::vector<KeyType> Parent;
beckerjc@349:     typedef typename Parent::iterator iterator;
beckerjc@349:     typedef typename Parent::const_iterator const_iterator;
beckerjc@349: 
beckerjc@349:   private:
beckerjc@349: 
beckerjc@349:     const Map &m;
beckerjc@349: 
beckerjc@349:     class compareKeys {
beckerjc@349:       const Map &m;
beckerjc@349:     public:
beckerjc@349:       compareKeys(Map const &_m) : m(_m) {}
beckerjc@349:       bool operator()(KeyType const& a, KeyType const& b) {
beckerjc@349: 	return m[a] < m[b];
beckerjc@349:       }
beckerjc@349:     };
beckerjc@349: 
beckerjc@349:   public:
beckerjc@349: 
beckerjc@349:     KruskalMapVec(Map const& _m) : m(_m) {}
beckerjc@349: 
beckerjc@349:     void sort() {
beckerjc@349:       std::sort(begin(), end(), compareKeys(m));
beckerjc@349:     }
beckerjc@349: 
beckerjc@349:     // FIXME: nem nagyon illik ez ide...
beckerjc@349:     template<typename Graph>
beckerjc@349:     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
beckerjc@349:       typedef typename Graph::EdgeIt EdgeIt;
beckerjc@349: 
beckerjc@349:       clear();
beckerjc@349:       FOR_EACH_LOC(EdgeIt, e, G) {
beckerjc@349:       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
beckerjc@349: 	push_back(e);
beckerjc@349:       }
beckerjc@349:       sort();
beckerjc@349:     }
beckerjc@349: 
beckerjc@349:     KeyType const& first(const_iterator i) const { return *i; }
beckerjc@349:     KeyType& first(iterator i) { return *i; }
beckerjc@349: 
beckerjc@349:     ValueType const& second(const_iterator i) const { return m[*i]; }
beckerjc@349:     ValueType& second(iterator i) { return m[*i]; }
beckerjc@349:   };
beckerjc@349: 
beckerjc@246:   /* ** ** Wrapper fuggvenyek ** ** */
beckerjc@246: 
beckerjc@349: 
beckerjc@349:   /// \brief Wrapper to Kruskal().
beckerjc@349:   /// Input is from an EdgeMap, output is a plain boolmap.
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
beckerjc@352:   inline
beckerjc@246:   typename EdgeCostMap::ValueType
beckerjc@349:   Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
beckerjc@349: 				   EdgeCostMap const& edge_costs,
beckerjc@349: 				   RetEdgeBoolMap &ret_bool_map) {
beckerjc@246: 
beckerjc@349:     typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
beckerjc@246:       InputVec;
beckerjc@349:     InputVec iv(G, edge_costs);
beckerjc@246: 
beckerjc@349:     return Kruskal(G, iv, ret_bool_map);
beckerjc@246:   }
beckerjc@246: 
beckerjc@349: 
beckerjc@349:   /// \brief Wrapper to Kruskal().
beckerjc@349:   /// Input is from an EdgeMap, output is to a sequence.
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetIterator>
beckerjc@352:   inline
beckerjc@246:   typename EdgeCostMap::ValueType
beckerjc@349:   Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
beckerjc@349: 				    EdgeCostMap const& edge_costs,
beckerjc@349: 				    RetIterator ret_iterator) {
beckerjc@349:     typedef SequenceOutput<RetIterator> OutMap;
beckerjc@349:     OutMap out(ret_iterator);
beckerjc@246: 
beckerjc@349:     typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
beckerjc@246:       InputVec;
beckerjc@349:     InputVec iv(G, edge_costs);
beckerjc@246: 
beckerjc@349:     return Kruskal(G, iv, out);
beckerjc@246:   }
beckerjc@246: 
beckerjc@150: 
beckerjc@150: } //namespace hugo
beckerjc@150: 
beckerjc@150: #endif //HUGO_KRUSKAL_H