beckerjc@150: // -*- c++ -*- //
beckerjc@150: #ifndef HUGO_KRUSKAL_H
beckerjc@150: #define HUGO_KRUSKAL_H
beckerjc@150: 
beckerjc@150: #include <algorithm>
alpar@737: #include <hugo/unionfind.h>
beckerjc@150: 
alpar@758: /**
alpar@758: @defgroup spantree Minimum Cost Spanning Tree Algorithms
alpar@758: \brief This group containes the algorithms for finding a minimum cost spanning
alpar@758: tree in a graph
alpar@758: @ingroup galgs
alpar@758: */
alpar@758: 
alpar@758: ///\ingroup spantree
alpar@682: ///\file
alpar@682: ///\brief Kruskal's algorithm to compute a minimum cost tree
alpar@682: 
beckerjc@150: namespace hugo {
beckerjc@150: 
alpar@758:   /// \addtogroup spantree
alpar@758:   /// @{
alpar@758: 
alpar@737:   /// Kruskal's algorithm to find a minimum cost tree of a graph.
alpar@737: 
alpar@737:   /// This function runs Kruskal's algorithm to find a minimum cost tree.
alpar@737:   /// \param G The graph the algorithm runs on.
alpar@737:   /// \param in This object is used to describe the edge costs. It must
alpar@737:   /// be an STL 'forward container'
alpar@737:   /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
alpar@737:   /// where X is the type of the costs. It must contain every edge in
alpar@737:   /// cost-ascending order.
alpar@737:   /// \retval out This must be a writeable EdgeMap. After running the algorithm
alpar@737:   /// this will contain the found minimum cost spanning tree: the value of an
alpar@737:   /// edge will be set to \c true if it belongs to the tree, otherwise it will
alpar@737:   /// be set to \c false. The value of each edge will be set exactly once.\n
alpar@737:   /// For the sake of simplicity, there is a helper class KruskalPairVec,
alpar@737:   /// which converts a
alpar@737:   /// simple EdgeMap to an input of this form. Alternatively, you can use
alpar@737:   /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
alpar@737:   /// the edge costs are given by an EdgeMap.
alpar@737:   /// \return The cost of the found tree.
beckerjc@150: 
beckerjc@349:   template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
alpar@737:   typename InputEdgeOrder::value_type::second_type
alpar@737:   kruskal(Graph const& G, InputEdgeOrder const& in, 
alpar@737: 		 OutBoolMap& out)
beckerjc@349:   {
alpar@737:     typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
alpar@737:     typedef typename Graph::template NodeMap<int> NodeIntMap;
beckerjc@349:     typedef typename Graph::Node Node;
beckerjc@246: 
alpar@737:     NodeIntMap comp(G, -1);
alpar@737:     UnionFind<Node,NodeIntMap> uf(comp); 
beckerjc@349:       
beckerjc@349:     EdgeCost tot_cost = 0;
alpar@737:     for (typename InputEdgeOrder::const_iterator p = in.begin(); 
alpar@737: 	 p!=in.end(); ++p ) {
alpar@737:       if ( uf.join(G.head((*p).first),
alpar@737: 		   G.tail((*p).first)) ) {
alpar@737: 	out.set((*p).first, true);
alpar@737: 	tot_cost += (*p).second;
beckerjc@349:       }
beckerjc@349:       else {
alpar@737: 	out.set((*p).first, 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
alpar@737:   kruskal(Graph const& G, InputEdgeOrder const& edges, 
beckerjc@352: 	  OutBoolMap const& out_map)
beckerjc@352:   {
beckerjc@352:     NonConstMapWr<OutBoolMap> map_wr(out_map);
alpar@737:     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: 
alpar@737:   /// A writable bool-map that creates a sequence out of keys that receives
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: 
alpar@737:   /// Kruskal input source.
beckerjc@246: 
alpar@737:   /// Kruskal input source.
alpar@737:   ///
alpar@737:   template<typename Graph, typename Map>
alpar@755:   class KruskalMapInput
alpar@737:     : public std::vector< std::pair<typename Graph::Edge,
alpar@737: 				    typename Map::ValueType> > {
alpar@737:     
beckerjc@246:   public:
alpar@737:     typedef std::vector< std::pair<typename Graph::Edge,
alpar@737: 				   typename Map::ValueType> > Parent;
alpar@737:     typedef typename Parent::value_type value_type;
alpar@737: //     typedef Key KeyType;
alpar@737: //     typedef Val ValueType;
alpar@737: //     typedef std::pair<Key,Val> PairType;
alpar@737: //     typedef typename Parent::iterator iterator;
alpar@737: //     typedef typename Parent::const_iterator const_iterator;
beckerjc@246: 
beckerjc@246:   private:
beckerjc@246:     class comparePair {
beckerjc@246:     public:
alpar@737:       bool operator()(const value_type& a,
alpar@737: 		      const value_type& b) {
beckerjc@246: 	return a.second < b.second;
beckerjc@246:       }
beckerjc@246:     };
beckerjc@246: 
beckerjc@246:   public:
beckerjc@246: 
beckerjc@246:     // FIXME: kell ez?
alpar@755:     // KruskalMapInput(Parent const& p) : Parent(p) {}
beckerjc@246:     
beckerjc@246:     void sort() {
alpar@737:       std::sort(this->begin(), this->end(), comparePair());
beckerjc@246:     }
beckerjc@246: 
beckerjc@246:     // FIXME: nem nagyon illik ez ide...
alpar@755:     KruskalMapInput(Graph const& G, Map const& m) {
beckerjc@246:       typedef typename Graph::EdgeIt EdgeIt;
alpar@737:       
alpar@737:       this->clear();
alpar@737:       for(EdgeIt e(G);G.valid(e);G.next(e)) {
alpar@737: 	// 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: 
alpar@737: //     Key const& first(const_iterator i) const { return i->first; }
alpar@737: //     Key& first(iterator i) { return i->first; }
beckerjc@246: 
alpar@737: //     Val const& second(const_iterator i) const { return i->second; }
alpar@737: //     Val& second(iterator i) { return i->second; }
beckerjc@246:   };
beckerjc@246: 
beckerjc@349: 
alpar@755: //   template<typename Graph, typename Map>
alpar@755: //   class KruskalMapVec {
alpar@737: //   public:
alpar@737:     
alpar@755: //     typedef std::pair<typename Map::KeyType, Map::ValueType> value_type;
alpar@755:     
alpar@755: //     typedef std::vector<KeyType> Container;
alpar@755: //     Container container;
alpar@755: //     std::vector<typename Map::KeyType> container
alpar@755: //     const Map &m;
alpar@755:     
alpar@755:     
alpar@755: //     class iterator
alpar@755: //     {
alpar@755: //       Container::iterator i;
alpar@755: //     public:
alpar@755: //       iterator &operator ++() {++i;return *this;}
alpar@755: //       valuetype operator *() {return value_type(container(i),m[container(i)]);}
alpar@755: //       bool operator==(iterator b) {return i==b.i;}
alpar@755: //       iterator() {}
alpar@755: //       iterator(Container::iterator _i) i(_i) {}
alpar@755: //     };
alpar@755: //     class const_iterator
alpar@755: //     {
alpar@755: //       Container::const_iterator i;
alpar@755: //     public:
alpar@755: //       iterator &operator ++() {++i;return *this;}
alpar@755: //       valuetype operator *() {return value_type(container(i),m[container(i)]);}
alpar@755: //       bool operator==(iterator b) {return i==b.i;}
alpar@755: //       const_iterator() {}
alpar@755: //       const_iterator(Container::iterator _i) i(_i) {}
alpar@755: //     };
beckerjc@349: 
alpar@755: //     iterator begin() { return iterator(container.begin());}
alpar@755: //     const_iterator begin() const { return iterator(container.begin());}
alpar@755: //     iterator end() { return iterator(container.end());}
alpar@755: //     const_iterator end() const { return iterator(container.end());}
alpar@755:     
alpar@737: //   private:
alpar@755:     
alpar@737: //     class compareKeys {
alpar@737: //       const Map &m;
alpar@737: //     public:
alpar@737: //       compareKeys(Map const &_m) : m(_m) {}
alpar@737: //       bool operator()(KeyType const& a, KeyType const& b) {
alpar@737: // 	return m[a] < m[b];
alpar@737: //       }
alpar@737: //     };
beckerjc@349: 
alpar@737: //   public:
beckerjc@349: 
alpar@737: //     KruskalMapVec(Map const& _m) : m(_m) {}
beckerjc@349: 
alpar@737: //     void sort() {
alpar@737: //       std::sort(begin(), end(), compareKeys(m));
alpar@737: //     }
beckerjc@349: 
alpar@737: //     // FIXME: nem nagyon illik ez ide...
alpar@737: //     template<typename Graph>
alpar@737: //     KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
alpar@737: //       typedef typename Graph::EdgeIt EdgeIt;
beckerjc@349: 
alpar@737: //       clear();
alpar@737: //       for(EdgeIt e(G);G.valid(e);G.next(e)) {
alpar@737: //       // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) 
alpar@737: // 	push_back(e);
alpar@737: //       }
alpar@737: //       sort();
alpar@737: //     }
beckerjc@349: 
alpar@737: //     KeyType const& first(const_iterator i) const { return *i; }
alpar@737: //     KeyType& first(iterator i) { return *i; }
beckerjc@349: 
alpar@737: //     ValueType const& second(const_iterator i) const { return m[*i]; }
alpar@737: //     ValueType& second(iterator i) { return m[*i]; }
alpar@737: //   };
beckerjc@349: 
alpar@755: 
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.
alpar@737: 
alpar@737:   ///\todo some more words would be nice here.
alpar@737:   ///
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
beckerjc@352:   inline
beckerjc@246:   typename EdgeCostMap::ValueType
alpar@737:   kruskalEdgeMap(Graph const& G,
alpar@737: 			EdgeCostMap const& edge_costs,
alpar@737: 			RetEdgeBoolMap &ret_bool_map) {
alpar@737:     
alpar@755:     typedef KruskalMapInput<Graph,EdgeCostMap> InputVec;
alpar@737:     
beckerjc@349:     InputVec iv(G, edge_costs);
alpar@737:     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.
alpar@737: 
alpar@737:   ///\todo it does not follow the naming convention.
alpar@737:   ///
beckerjc@246:   template <typename Graph, typename EdgeCostMap, typename RetIterator>
beckerjc@352:   inline
beckerjc@246:   typename EdgeCostMap::ValueType
alpar@737:   kruskalEdgeMap_IteratorOut(const Graph& G,
alpar@737: 			     const EdgeCostMap& edge_costs,
alpar@737: 			     RetIterator ret_iterator)
alpar@737:   {
alpar@737:     typedef typename EdgeCostMap::ValueType ValueType;
alpar@737:     
beckerjc@349:     typedef SequenceOutput<RetIterator> OutMap;
beckerjc@349:     OutMap out(ret_iterator);
beckerjc@246: 
alpar@755:     typedef KruskalMapInput<Graph, EdgeCostMap> InputVec;
alpar@737: 
beckerjc@349:     InputVec iv(G, edge_costs);
beckerjc@246: 
alpar@737:     return kruskal(G, iv, out);
beckerjc@246:   }
beckerjc@246: 
alpar@758:   /// @}
beckerjc@150: 
beckerjc@150: } //namespace hugo
beckerjc@150: 
beckerjc@150: #endif //HUGO_KRUSKAL_H