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