alpar@906: /* -*- C++ -*- alpar@921: * src/lemon/kruskal.h - Part of LEMON, a generic C++ optimization library alpar@906: * alpar@1164: * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@1359: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@906: * alpar@906: * Permission to use, modify and distribute this software is granted alpar@906: * provided that this copyright notice appears in all copies. For alpar@906: * precise terms see the accompanying LICENSE file. alpar@906: * alpar@906: * This software is provided "AS IS" with no warranty of any kind, alpar@906: * express or implied, and with no claim as to its suitability for any alpar@906: * purpose. alpar@906: * alpar@906: */ alpar@906: alpar@921: #ifndef LEMON_KRUSKAL_H alpar@921: #define LEMON_KRUSKAL_H alpar@810: alpar@810: #include alpar@921: #include alpar@810: alpar@810: /** alpar@810: @defgroup spantree Minimum Cost Spanning Tree Algorithms alpar@810: @ingroup galgs alpar@810: \brief This group containes the algorithms for finding a minimum cost spanning alpar@810: tree in a graph alpar@810: alpar@810: This group containes the algorithms for finding a minimum cost spanning alpar@810: tree in a graph alpar@810: */ alpar@810: alpar@810: ///\ingroup spantree alpar@810: ///\file alpar@810: ///\brief Kruskal's algorithm to compute a minimum cost tree alpar@810: /// alpar@810: ///Kruskal's algorithm to compute a minimum cost tree. alpar@810: alpar@921: namespace lemon { alpar@810: alpar@810: /// \addtogroup spantree alpar@810: /// @{ alpar@810: alpar@810: /// Kruskal's algorithm to find a minimum cost tree of a graph. alpar@810: alpar@810: /// This function runs Kruskal's algorithm to find a minimum cost tree. alpar@810: /// \param G The graph the algorithm runs on. The algorithm considers the alpar@810: /// graph to be undirected, the direction of the edges are not used. alpar@810: /// alpar@810: /// \param in This object is used to describe the edge costs. It must alpar@810: /// be an STL compatible 'Forward Container' alpar@824: /// with std::pair as its value_type, alpar@810: /// where X is the type of the costs. It must contain every edge in alpar@810: /// cost-ascending order. alpar@810: ///\par alpar@810: /// For the sake of simplicity, there is a helper class KruskalMapInput, alpar@810: /// which converts a alpar@810: /// simple edge map to an input of this form. Alternatively, you can use alpar@810: /// the function \ref kruskalEdgeMap to compute the minimum cost tree if alpar@810: /// the edge costs are given by an edge map. alpar@810: /// alpar@810: /// \retval out This must be a writable \c bool edge map. alpar@810: /// After running the algorithm alpar@810: /// this will contain the found minimum cost spanning tree: the value of an alpar@810: /// edge will be set to \c true if it belongs to the tree, otherwise it will alpar@810: /// be set to \c false. The value of each edge will be set exactly once. alpar@810: /// alpar@810: /// \return The cost of the found tree. alpar@810: alpar@824: template alpar@824: typename IN::value_type::second_type alpar@824: kruskal(GR const& G, IN const& in, alpar@824: OUT& out) alpar@810: { alpar@824: typedef typename IN::value_type::second_type EdgeCost; alpar@824: typedef typename GR::template NodeMap NodeIntMap; alpar@824: typedef typename GR::Node Node; alpar@810: alpar@810: NodeIntMap comp(G, -1); alpar@810: UnionFind uf(comp); alpar@810: alpar@810: EdgeCost tot_cost = 0; alpar@824: for (typename IN::const_iterator p = in.begin(); alpar@810: p!=in.end(); ++p ) { alpar@986: if ( uf.join(G.target((*p).first), alpar@986: G.source((*p).first)) ) { alpar@810: out.set((*p).first, true); alpar@810: tot_cost += (*p).second; alpar@810: } alpar@810: else { alpar@810: out.set((*p).first, false); alpar@810: } alpar@810: } alpar@810: return tot_cost; alpar@810: } alpar@810: alpar@810: /* A work-around for running Kruskal with const-reference bool maps... */ alpar@810: klao@885: /// Helper class for calling kruskal with "constant" output map. klao@885: klao@885: /// Helper class for calling kruskal with output maps constructed klao@885: /// on-the-fly. alpar@810: /// klao@885: /// A typical examle is the following call: klao@885: /// kruskal(G, some_input, makeSequenceOutput(iterator)). klao@885: /// Here, the third argument is a temporary object (which wraps around an klao@885: /// iterator with a writable bool map interface), and thus by rules of C++ klao@885: /// is a \c const object. To enable call like this exist this class and klao@885: /// the prototype of the \ref kruskal() function with const& OUT klao@885: /// third argument. alpar@824: template alpar@810: class NonConstMapWr { alpar@810: const Map &m; alpar@810: public: alpar@987: typedef typename Map::Value Value; alpar@810: alpar@810: NonConstMapWr(const Map &_m) : m(_m) {} alpar@810: alpar@987: template alpar@987: void set(Key const& k, Value const &v) const { m.set(k,v); } alpar@810: }; alpar@810: alpar@824: template alpar@810: inline klao@885: typename IN::value_type::second_type klao@885: kruskal(GR const& G, IN const& edges, OUT const& out_map) alpar@810: { alpar@824: NonConstMapWr map_wr(out_map); alpar@810: return kruskal(G, edges, map_wr); alpar@810: } alpar@810: alpar@810: /* ** ** Input-objects ** ** */ alpar@810: zsuzska@1274: /// Kruskal's input source. alpar@810: zsuzska@1274: /// Kruskal's input source. alpar@810: /// alpar@810: /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead. alpar@810: /// alpar@810: /// \sa makeKruskalMapInput() alpar@810: /// alpar@824: ///\param GR The type of the graph the algorithm runs on. alpar@810: ///\param Map An edge map containing the cost of the edges. alpar@810: ///\par alpar@810: ///The cost type can be any type satisfying alpar@810: ///the STL 'LessThan comparable' alpar@810: ///concept if it also has an operator+() implemented. (It is necessary for alpar@810: ///computing the total cost of the tree). alpar@810: /// alpar@824: template alpar@810: class KruskalMapInput alpar@824: : public std::vector< std::pair > { alpar@810: alpar@810: public: alpar@824: typedef std::vector< std::pair > Parent; alpar@810: typedef typename Parent::value_type value_type; alpar@810: alpar@810: private: alpar@810: class comparePair { alpar@810: public: alpar@810: bool operator()(const value_type& a, alpar@810: const value_type& b) { alpar@810: return a.second < b.second; alpar@810: } alpar@810: }; alpar@810: alpar@810: public: alpar@810: alpar@810: void sort() { alpar@810: std::sort(this->begin(), this->end(), comparePair()); alpar@810: } alpar@810: alpar@824: KruskalMapInput(GR const& G, Map const& m) { alpar@824: typedef typename GR::EdgeIt EdgeIt; alpar@810: klao@885: for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e])); alpar@810: sort(); alpar@810: } alpar@810: }; alpar@810: alpar@810: /// Creates a KruskalMapInput object for \ref kruskal() alpar@810: zsuzska@1274: /// It makes easier to use alpar@810: /// \ref KruskalMapInput by making it unnecessary alpar@810: /// to explicitly give the type of the parameters. alpar@810: /// alpar@810: /// In most cases you possibly alpar@810: /// want to use the function kruskalEdgeMap() instead. alpar@810: /// alpar@810: ///\param G The type of the graph the algorithm runs on. alpar@810: ///\param m An edge map containing the cost of the edges. alpar@810: ///\par alpar@810: ///The cost type can be any type satisfying the alpar@810: ///STL 'LessThan Comparable' alpar@810: ///concept if it also has an operator+() implemented. (It is necessary for alpar@810: ///computing the total cost of the tree). alpar@810: /// alpar@810: ///\return An appropriate input source for \ref kruskal(). alpar@810: /// alpar@824: template alpar@810: inline alpar@824: KruskalMapInput makeKruskalMapInput(const GR &G,const Map &m) alpar@810: { alpar@824: return KruskalMapInput(G,m); alpar@810: } alpar@810: alpar@810: klao@885: klao@885: /* ** ** Output-objects: simple writable bool maps ** ** */ alpar@810: klao@885: klao@885: alpar@810: /// A writable bool-map that makes a sequence of "true" keys alpar@810: alpar@810: /// A writable bool-map that creates a sequence out of keys that receives alpar@810: /// the value "true". klao@885: /// klao@885: /// \sa makeKruskalSequenceOutput() klao@885: /// klao@885: /// Very often, when looking for a min cost spanning tree, we want as klao@885: /// output a container containing the edges of the found tree. For this klao@885: /// purpose exist this class that wraps around an STL iterator with a klao@885: /// writable bool map interface. When a key gets value "true" this key klao@885: /// is added to sequence pointed by the iterator. klao@885: /// klao@885: /// A typical usage: klao@885: /// \code klao@885: /// std::vector v; klao@885: /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v))); klao@885: /// \endcode klao@885: /// klao@885: /// For the most common case, when the input is given by a simple edge klao@885: /// map and the output is a sequence of the tree edges, a special klao@885: /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut(). klao@885: /// alpar@987: /// \warning Not a regular property map, as it doesn't know its Key klao@885: alpar@824: template klao@885: class KruskalSequenceOutput { alpar@810: mutable Iterator it; alpar@810: alpar@810: public: alpar@987: typedef bool Value; alpar@810: klao@885: KruskalSequenceOutput(Iterator const &_it) : it(_it) {} alpar@810: alpar@987: template alpar@987: void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} } alpar@810: }; alpar@810: alpar@824: template alpar@810: inline klao@885: KruskalSequenceOutput klao@885: makeKruskalSequenceOutput(Iterator it) { klao@885: return KruskalSequenceOutput(it); alpar@810: } alpar@810: klao@885: klao@885: alpar@810: /* ** ** Wrapper funtions ** ** */ alpar@810: alpar@810: klao@885: alpar@810: /// \brief Wrapper function to kruskal(). alpar@810: /// Input is from an edge map, output is a plain bool map. alpar@810: /// alpar@810: /// Wrapper function to kruskal(). alpar@810: /// Input is from an edge map, output is a plain bool map. alpar@810: /// alpar@810: ///\param G The type of the graph the algorithm runs on. alpar@810: ///\param in An edge map containing the cost of the edges. alpar@810: ///\par alpar@810: ///The cost type can be any type satisfying the alpar@810: ///STL 'LessThan Comparable' alpar@810: ///concept if it also has an operator+() implemented. (It is necessary for alpar@810: ///computing the total cost of the tree). alpar@810: /// alpar@810: /// \retval out This must be a writable \c bool edge map. alpar@810: /// After running the algorithm alpar@810: /// this will contain the found minimum cost spanning tree: the value of an alpar@810: /// edge will be set to \c true if it belongs to the tree, otherwise it will alpar@810: /// be set to \c false. The value of each edge will be set exactly once. alpar@810: /// alpar@810: /// \return The cost of the found tree. alpar@810: alpar@824: template alpar@810: inline alpar@987: typename IN::Value alpar@824: kruskalEdgeMap(GR const& G, alpar@824: IN const& in, alpar@824: RET &out) { alpar@810: return kruskal(G, alpar@824: KruskalMapInput(G,in), alpar@810: out); alpar@810: } alpar@810: alpar@810: /// \brief Wrapper function to kruskal(). alpar@810: /// Input is from an edge map, output is an STL Sequence. alpar@810: /// alpar@810: /// Wrapper function to kruskal(). alpar@810: /// Input is from an edge map, output is an STL Sequence. alpar@810: /// alpar@810: ///\param G The type of the graph the algorithm runs on. alpar@810: ///\param in An edge map containing the cost of the edges. alpar@810: ///\par alpar@810: ///The cost type can be any type satisfying the alpar@810: ///STL 'LessThan Comparable' alpar@810: ///concept if it also has an operator+() implemented. (It is necessary for alpar@810: ///computing the total cost of the tree). alpar@810: /// alpar@810: /// \retval out This must be an iteraror of an STL Container with alpar@824: /// GR::Edge as its value_type. alpar@810: /// The algorithm copies the elements of the found tree into this sequence. alpar@810: /// For example, if we know that the spanning tree of the graph \c G has alpar@810: /// say 53 edges then alpar@824: /// we can put its edges into a STL vector \c tree with a code like this. alpar@810: /// \code alpar@810: /// std::vector tree(53); alpar@810: /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin()); alpar@810: /// \endcode alpar@810: /// Or if we don't know in advance the size of the tree, we can write this. alpar@810: /// \code alpar@810: /// std::vector tree; alpar@810: /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree)); alpar@810: /// \endcode alpar@810: /// alpar@810: /// \return The cost of the found tree. alpar@810: /// alpar@810: /// \bug its name does not follow the coding style. klao@885: alpar@824: template alpar@810: inline alpar@987: typename IN::Value alpar@824: kruskalEdgeMap_IteratorOut(const GR& G, alpar@824: const IN& in, alpar@824: RET out) alpar@810: { klao@885: KruskalSequenceOutput _out(out); klao@885: return kruskal(G, KruskalMapInput(G, in), _out); alpar@810: } alpar@810: alpar@810: /// @} alpar@810: alpar@921: } //namespace lemon alpar@810: alpar@921: #endif //LEMON_KRUSKAL_H