/* -*- C++ -*- * * This file is a part of LEMON, a generic C++ optimization library * * Copyright (C) 2003-2006 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). * * Permission to use, modify and distribute this software is granted * provided that this copyright notice appears in all copies. For * precise terms see the accompanying LICENSE file. * * This software is provided "AS IS" with no warranty of any kind, * express or implied, and with no claim as to its suitability for any * purpose. * */ #ifndef LEMON_KRUSKAL_H #define LEMON_KRUSKAL_H #include #include #include #include #include ///\ingroup spantree ///\file ///\brief Kruskal's algorithm to compute a minimum cost tree /// ///Kruskal's algorithm to compute a minimum cost tree. /// ///\todo The file still needs some clean-up. namespace lemon { /// \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. /// Due to hard C++ hacking, it accepts various input and output types. /// /// \param g The graph the algorithm runs on. /// It can be either \ref concept::Graph "directed" or /// \ref concept::UGraph "undirected". /// If the graph is directed, the algorithm consider it to be /// undirected by disregarding the direction of the edges. /// /// \param in This object is used to describe the edge costs. It can be one /// of the following choices. /// - An STL compatible 'Forward Container' /// with std::pair as its value_type, /// where \c X is the type of the costs. The pairs indicates the edges along /// with the assigned cost. They must be in a /// cost-ascending order. /// - Any readable Edge map. The values of the map indicate the edge costs. /// /// \retval out Here we also have a choise. /// - It can be a writable \c bool edge map. /// 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. /// - It can also be an iteraror of an STL Container with /// GR::Edge as its value_type. /// The algorithm copies the elements of the found tree into this sequence. /// For example, if we know that the spanning tree of the graph \c g has /// say 53 edges, then /// we can put its edges into an STL vector \c tree with a code like this. ///\code /// std::vector tree(53); /// kruskal(g,cost,tree.begin()); ///\endcode /// Or if we don't know in advance the size of the tree, we can write this. ///\code /// std::vector tree; /// kruskal(g,cost,std::back_inserter(tree)); ///\endcode /// /// \return The cost of the found tree. /// /// \warning If kruskal runs on an /// \ref lemon::concept::UGraph "undirected graph", be sure that the /// map storing the tree is also undirected /// (e.g. ListUGraph::UEdgeMap, otherwise the values of the /// half of the edges will not be set. /// /// \todo Discuss the case of undirected graphs: In this case the algorithm /// also require Edges instead of UEdges, as some /// people would expect. So, one should be careful not to add both of the /// Edges belonging to a certain UEdge. /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.) #ifdef DOXYGEN template typename IN::value_type::second_type kruskal(GR const& g, IN const& in, OUT& out) #else template typename IN::value_type::second_type kruskal(GR const& g, IN const& in, OUT& out, // typename IN::value_type::first_type = typename GR::Edge() // ,typename OUT::Key = OUT::Key() // //,typename OUT::Key = typename GR::Edge() const typename IN::value_type::first_type * = (const typename IN::value_type::first_type *)(0), const typename OUT::Key * = (const typename OUT::Key *)(0) ) #endif { typedef typename IN::value_type::second_type EdgeCost; typedef typename GR::template NodeMap NodeIntMap; typedef typename GR::Node Node; NodeIntMap comp(g); UnionFind uf(comp); for (typename GR::NodeIt it(g); it != INVALID; ++it) { uf.insert(it); } EdgeCost tot_cost = 0; for (typename IN::const_iterator p = in.begin(); p!=in.end(); ++p ) { if ( uf.join(g.target((*p).first), g.source((*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... */ /// Helper class for calling kruskal with "constant" output map. /// Helper class for calling kruskal with output maps constructed /// on-the-fly. /// /// A typical examle is the following call: /// kruskal(g, some_input, makeSequenceOutput(iterator)). /// Here, the third argument is a temporary object (which wraps around an /// iterator with a writable bool map interface), and thus by rules of C++ /// is a \c const object. To enable call like this exist this class and /// the prototype of the \ref kruskal() function with const& OUT /// third argument. template class NonConstMapWr { const Map &m; public: typedef typename Map::Key Key; typedef typename Map::Value Value; NonConstMapWr(const Map &_m) : m(_m) {} template void set(Key const& k, Value const &v) const { m.set(k,v); } }; template inline typename IN::value_type::second_type kruskal(GR const& g, IN const& edges, OUT const& out_map, // typename IN::value_type::first_type = typename GR::Edge(), // typename OUT::Key = GR::Edge() const typename IN::value_type::first_type * = (const typename IN::value_type::first_type *)(0), const typename OUT::Key * = (const typename OUT::Key *)(0) ) { NonConstMapWr map_wr(out_map); return kruskal(g, edges, map_wr); } /* ** ** Input-objects ** ** */ /// Kruskal's input source. /// Kruskal's input source. /// /// In most cases you possibly want to use the \ref kruskal() instead. /// /// \sa makeKruskalMapInput() /// ///\param GR The type of the graph the algorithm runs on. ///\param Map An edge map containing the cost of the edges. ///\par ///The cost type can be any type satisfying ///the STL 'LessThan comparable' ///concept if it also has an operator+() implemented. (It is necessary for ///computing the total cost of the tree). /// template class KruskalMapInput : public std::vector< std::pair > { public: typedef std::vector< std::pair > Parent; typedef typename Parent::value_type value_type; private: class comparePair { public: bool operator()(const value_type& a, const value_type& b) { return a.second < b.second; } }; template typename enable_if,void>::type fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) { for(typename GR::UEdgeIt e(g);e!=INVALID;++e) push_back(value_type(g.direct(e, true), m[e])); } template typename disable_if,void>::type fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) { for(typename GR::EdgeIt e(g);e!=INVALID;++e) push_back(value_type(e, m[e])); } public: void sort() { std::sort(this->begin(), this->end(), comparePair()); } KruskalMapInput(GR const& g, Map const& m) { fillWithEdges(g,m); sort(); } }; /// Creates a KruskalMapInput object for \ref kruskal() /// It makes easier to use /// \ref KruskalMapInput by making it unnecessary /// to explicitly give the type of the parameters. /// /// In most cases you possibly /// want to use \ref kruskal() instead. /// ///\param g The type of the graph the algorithm runs on. ///\param m An edge map containing the cost of the edges. ///\par ///The cost type can be any type satisfying the ///STL 'LessThan Comparable' ///concept if it also has an operator+() implemented. (It is necessary for ///computing the total cost of the tree). /// ///\return An appropriate input source for \ref kruskal(). /// template inline KruskalMapInput makeKruskalMapInput(const GR &g,const Map &m) { return KruskalMapInput(g,m); } /* ** ** Output-objects: simple writable bool maps ** ** */ /// 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". /// /// \sa makeKruskalSequenceOutput() /// /// Very often, when looking for a min cost spanning tree, we want as /// output a container containing the edges of the found tree. For this /// purpose exist this class that wraps around an STL iterator with a /// writable bool map interface. When a key gets value "true" this key /// is added to sequence pointed by the iterator. /// /// A typical usage: ///\code /// std::vector v; /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v))); ///\endcode /// /// For the most common case, when the input is given by a simple edge /// map and the output is a sequence of the tree edges, a special /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut(). /// /// \warning Not a regular property map, as it doesn't know its Key template class KruskalSequenceOutput { mutable Iterator it; public: typedef typename std::iterator_traits::value_type Key; typedef bool Value; KruskalSequenceOutput(Iterator const &_it) : it(_it) {} template void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} } }; template inline KruskalSequenceOutput makeKruskalSequenceOutput(Iterator it) { return KruskalSequenceOutput(it); } /* ** ** Wrapper funtions ** ** */ // \brief Wrapper function to kruskal(). // Input is from an edge map, output is a plain bool map. // // Wrapper function to kruskal(). // Input is from an edge map, output is a plain bool map. // // \param g The type of the graph the algorithm runs on. // \param in An edge map containing the cost of the edges. // \par // The cost type can be any type satisfying the // STL 'LessThan Comparable' // concept if it also has an operator+() implemented. (It is necessary for // computing the total cost of the tree). // // \retval out This must be a writable \c bool edge map. // 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. // // \return The cost of the found tree. template inline typename IN::Value kruskal(GR const& g, IN const& in, RET &out, // typename IN::Key = typename GR::Edge(), //typename IN::Key = typename IN::Key (), // typename RET::Key = typename GR::Edge() const typename IN::Key * = (const typename IN::Key *)(0), const typename RET::Key * = (const typename RET::Key *)(0) ) { return kruskal(g, KruskalMapInput(g,in), out); } // \brief Wrapper function to kruskal(). // Input is from an edge map, output is an STL Sequence. // // Wrapper function to kruskal(). // Input is from an edge map, output is an STL Sequence. // // \param g The type of the graph the algorithm runs on. // \param in An edge map containing the cost of the edges. // \par // The cost type can be any type satisfying the // STL 'LessThan Comparable' // concept if it also has an operator+() implemented. (It is necessary for // computing the total cost of the tree). // // \retval out This must be an iteraror of an STL Container with // GR::Edge as its value_type. // The algorithm copies the elements of the found tree into this sequence. // For example, if we know that the spanning tree of the graph \c g has // say 53 edges, then // we can put its edges into an STL vector \c tree with a code like this. //\code // std::vector tree(53); // kruskal(g,cost,tree.begin()); //\endcode // Or if we don't know in advance the size of the tree, we can write this. //\code // std::vector tree; // kruskal(g,cost,std::back_inserter(tree)); //\endcode // // \return The cost of the found tree. // // \bug its name does not follow the coding style. template inline typename IN::Value kruskal(const GR& g, const IN& in, RET out, const typename RET::value_type * = (const typename RET::value_type *)(0) ) { KruskalSequenceOutput _out(out); return kruskal(g, KruskalMapInput(g, in), _out); } template inline typename IN::Value kruskal(const GR& g, const IN& in, RET *out ) { KruskalSequenceOutput _out(out); return kruskal(g, KruskalMapInput(g, in), _out); } /// @} } //namespace lemon #endif //LEMON_KRUSKAL_H