alpar@906: /* -*- C++ -*- alpar@906: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@1956: * Copyright (C) 2003-2006 alpar@1956: * 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 klao@1942: #include alpar@921: #include deba@1993: #include deba@1993: #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@1557: /// alpar@1557: ///\todo The file still needs some clean-up. 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@1557: /// Due to hard C++ hacking, it accepts various input and output types. alpar@1557: /// alpar@1555: /// \param g The graph the algorithm runs on. alpar@1555: /// It can be either \ref concept::StaticGraph "directed" or klao@1909: /// \ref concept::UGraph "undirected". alpar@1555: /// If the graph is directed, the algorithm consider it to be alpar@1555: /// undirected by disregarding the direction of the edges. alpar@810: /// alpar@1557: /// \param in This object is used to describe the edge costs. It can be one alpar@1557: /// of the following choices. alpar@1557: /// - An STL compatible 'Forward Container' alpar@824: /// with std::pair as its value_type, alpar@1557: /// where \c X is the type of the costs. The pairs indicates the edges along alpar@1557: /// with the assigned cost. They must be in a alpar@1557: /// cost-ascending order. alpar@1557: /// - Any readable Edge map. The values of the map indicate the edge costs. alpar@810: /// alpar@1557: /// \retval out Here we also have a choise. alpar@1557: /// - Is can 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@1557: /// - It can also be an iteraror of an STL Container with alpar@1557: /// GR::Edge as its value_type. alpar@1557: /// The algorithm copies the elements of the found tree into this sequence. alpar@1557: /// For example, if we know that the spanning tree of the graph \c g has alpar@1603: /// say 53 edges, then alpar@1557: /// we can put its edges into a STL vector \c tree with a code like this. alpar@1946: ///\code alpar@1557: /// std::vector tree(53); alpar@1557: /// kruskal(g,cost,tree.begin()); alpar@1946: ///\endcode alpar@1557: /// Or if we don't know in advance the size of the tree, we can write this. alpar@1946: ///\code alpar@1557: /// std::vector tree; alpar@1557: /// kruskal(g,cost,std::back_inserter(tree)); alpar@1946: ///\endcode alpar@810: /// alpar@810: /// \return The cost of the found tree. alpar@1449: /// alpar@1631: /// \warning If kruskal is run on an klao@1909: /// \ref lemon::concept::UGraph "undirected graph", be sure that the alpar@1603: /// map storing the tree is also undirected klao@1909: /// (e.g. ListUGraph::UEdgeMap, otherwise the values of the alpar@1603: /// half of the edges will not be set. alpar@1603: /// alpar@1449: /// \todo Discuss the case of undirected graphs: In this case the algorithm klao@1909: /// also require Edges instead of UEdges, as some alpar@1449: /// people would expect. So, one should be careful not to add both of the klao@1909: /// Edges belonging to a certain UEdge. alpar@1570: /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.) alpar@810: alpar@1557: #ifdef DOXYGEN alpar@824: template alpar@824: typename IN::value_type::second_type alpar@1547: kruskal(GR const& g, IN const& in, alpar@1557: OUT& out) alpar@1557: #else alpar@1557: template alpar@1557: typename IN::value_type::second_type alpar@1557: kruskal(GR const& g, IN const& in, alpar@1557: OUT& out, alpar@1557: // typename IN::value_type::first_type = typename GR::Edge() alpar@1557: // ,typename OUT::Key = OUT::Key() alpar@1557: // //,typename OUT::Key = typename GR::Edge() alpar@1557: const typename IN::value_type::first_type * = alpar@1557: (const typename IN::value_type::first_type *)(0), alpar@1557: const typename OUT::Key * = (const typename OUT::Key *)(0) alpar@1557: ) alpar@1557: #endif 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@1547: 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@1547: if ( uf.join(g.target((*p).first), alpar@1547: 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@1557: alpar@1557: /// @} alpar@1557: alpar@1557: 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: alpar@1547: /// 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@1557: typedef typename Map::Key Key; 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 alpar@1557: kruskal(GR const& g, IN const& edges, OUT const& out_map, alpar@1557: // typename IN::value_type::first_type = typename GR::Edge(), alpar@1557: // typename OUT::Key = GR::Edge() alpar@1557: const typename IN::value_type::first_type * = alpar@1557: (const typename IN::value_type::first_type *)(0), alpar@1557: const typename OUT::Key * = (const typename OUT::Key *)(0) alpar@1557: ) alpar@810: { alpar@824: NonConstMapWr map_wr(out_map); alpar@1547: return kruskal(g, edges, map_wr); alpar@810: } alpar@810: alpar@810: /* ** ** Input-objects ** ** */ alpar@810: zsuzska@1274: /// Kruskal's input source. alpar@1557: zsuzska@1274: /// Kruskal's input source. alpar@810: /// alpar@1570: /// In most cases you possibly want to use the \ref kruskal() 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@1449: template deba@1979: typename enable_if,void>::type alpar@1547: fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) alpar@1449: { klao@1909: for(typename GR::UEdgeIt e(g);e!=INVALID;++e) deba@1679: push_back(value_type(g.direct(e, true), m[e])); alpar@1449: } alpar@1449: alpar@1449: template deba@1979: typename disable_if,void>::type alpar@1547: fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) alpar@1449: { alpar@1547: for(typename GR::EdgeIt e(g);e!=INVALID;++e) alpar@1449: push_back(value_type(e, m[e])); alpar@1449: } alpar@1449: alpar@1449: alpar@810: public: alpar@810: alpar@810: void sort() { alpar@810: std::sort(this->begin(), this->end(), comparePair()); alpar@810: } alpar@810: alpar@1547: KruskalMapInput(GR const& g, Map const& m) { alpar@1547: fillWithEdges(g,m); 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@1570: /// want to use \ref kruskal() instead. alpar@810: /// alpar@1547: ///\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@1547: KruskalMapInput makeKruskalMapInput(const GR &g,const Map &m) alpar@810: { alpar@1547: 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: alpar@1946: ///\code klao@885: /// std::vector v; klao@885: /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v))); alpar@1946: ///\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: klao@1942: typedef typename std::iterator_traits::value_type Key; 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@1557: // \brief Wrapper function to kruskal(). alpar@1557: // Input is from an edge map, output is a plain bool map. alpar@1557: // alpar@1557: // Wrapper function to kruskal(). alpar@1557: // Input is from an edge map, output is a plain bool map. alpar@1557: // alpar@1557: // \param g The type of the graph the algorithm runs on. alpar@1557: // \param in An edge map containing the cost of the edges. alpar@1557: // \par alpar@1557: // The cost type can be any type satisfying the alpar@1557: // STL 'LessThan Comparable' alpar@1557: // concept if it also has an operator+() implemented. (It is necessary for alpar@1557: // computing the total cost of the tree). alpar@1557: // alpar@1557: // \retval out This must be a writable \c bool edge map. alpar@1557: // After running the algorithm alpar@1557: // this will contain the found minimum cost spanning tree: the value of an alpar@1557: // edge will be set to \c true if it belongs to the tree, otherwise it will alpar@1557: // be set to \c false. The value of each edge will be set exactly once. alpar@1557: // alpar@1557: // \return The cost of the found tree. alpar@810: alpar@824: template alpar@810: inline alpar@987: typename IN::Value alpar@1557: kruskal(GR const& g, alpar@1557: IN const& in, alpar@1557: RET &out, alpar@1557: // typename IN::Key = typename GR::Edge(), alpar@1557: //typename IN::Key = typename IN::Key (), alpar@1557: // typename RET::Key = typename GR::Edge() alpar@1557: const typename IN::Key * = (const typename IN::Key *)(0), alpar@1557: const typename RET::Key * = (const typename RET::Key *)(0) alpar@1557: ) alpar@1557: { alpar@1547: return kruskal(g, alpar@1547: KruskalMapInput(g,in), alpar@810: out); alpar@810: } alpar@810: alpar@1557: // \brief Wrapper function to kruskal(). alpar@1557: // Input is from an edge map, output is an STL Sequence. alpar@1557: // alpar@1557: // Wrapper function to kruskal(). alpar@1557: // Input is from an edge map, output is an STL Sequence. alpar@1557: // alpar@1557: // \param g The type of the graph the algorithm runs on. alpar@1557: // \param in An edge map containing the cost of the edges. alpar@1557: // \par alpar@1557: // The cost type can be any type satisfying the alpar@1557: // STL 'LessThan Comparable' alpar@1557: // concept if it also has an operator+() implemented. (It is necessary for alpar@1557: // computing the total cost of the tree). alpar@1557: // alpar@1557: // \retval out This must be an iteraror of an STL Container with alpar@1557: // GR::Edge as its value_type. alpar@1557: // The algorithm copies the elements of the found tree into this sequence. alpar@1557: // For example, if we know that the spanning tree of the graph \c g has alpar@1603: // say 53 edges, then alpar@1557: // we can put its edges into a STL vector \c tree with a code like this. alpar@1946: //\code alpar@1557: // std::vector tree(53); alpar@1570: // kruskal(g,cost,tree.begin()); alpar@1946: //\endcode alpar@1557: // Or if we don't know in advance the size of the tree, we can write this. alpar@1946: //\code alpar@1557: // std::vector tree; alpar@1570: // kruskal(g,cost,std::back_inserter(tree)); alpar@1946: //\endcode alpar@1557: // alpar@1557: // \return The cost of the found tree. alpar@1557: // alpar@1557: // \bug its name does not follow the coding style. klao@885: alpar@824: template alpar@810: inline alpar@987: typename IN::Value alpar@1557: kruskal(const GR& g, alpar@1557: const IN& in, alpar@1557: RET out, alpar@1557: const typename RET::value_type * = alpar@1557: (const typename RET::value_type *)(0) alpar@1557: ) alpar@810: { klao@885: KruskalSequenceOutput _out(out); alpar@1547: return kruskal(g, KruskalMapInput(g, in), _out); alpar@810: } alpar@1557: klao@1942: template klao@1942: inline klao@1942: typename IN::Value klao@1942: kruskal(const GR& g, klao@1942: const IN& in, klao@1942: RET *out klao@1942: ) klao@1942: { klao@1942: KruskalSequenceOutput _out(out); klao@1942: return kruskal(g, KruskalMapInput(g, in), _out); klao@1942: } klao@1942: alpar@810: /// @} alpar@810: alpar@921: } //namespace lemon alpar@810: alpar@921: #endif //LEMON_KRUSKAL_H