diff -r ea5ae5266285 -r e9fbc747ca47 src/hugo/kruskal.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/hugo/kruskal.h Mon Sep 06 17:12:00 2004 +0000 @@ -0,0 +1,304 @@ +// -*- c++ -*- // +#ifndef HUGO_KRUSKAL_H +#define HUGO_KRUSKAL_H + +#include +#include + +/** +@defgroup spantree Minimum Cost Spanning Tree Algorithms +@ingroup galgs +\brief This group containes the algorithms for finding a minimum cost spanning +tree in a graph + +This group containes the algorithms for finding a minimum cost spanning +tree in a graph +*/ + +///\ingroup spantree +///\file +///\brief Kruskal's algorithm to compute a minimum cost tree +/// +///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. The algorithm considers the + /// graph to be undirected, the direction of the edges are not used. + /// + /// \param in This object is used to describe the edge costs. It must + /// be an STL compatible 'Forward Container' + /// with std::pair as its value_type, + /// where X is the type of the costs. It must contain every edge in + /// cost-ascending order. + ///\par + /// For the sake of simplicity, there is a helper class KruskalMapInput, + /// which converts a + /// simple edge map 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 edge map. + /// + /// \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 + 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... */ + + ///\bug What is this? Or why doesn't it works? + /// + 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); + } + + /* ** ** Input-objects ** ** */ + + /// Kruskal input source. + + /// Kruskal input source. + /// + /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead. + /// + /// \sa makeKruskalMapInput() + /// + ///\param Graph 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; + } + }; + + public: + + void sort() { + std::sort(this->begin(), this->end(), comparePair()); + } + + KruskalMapInput(Graph const& G, Map const& m) { + typedef typename Graph::EdgeIt EdgeIt; + + this->clear(); + for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e])); + sort(); + } + }; + + /// Creates a KruskalMapInput object for \ref kruskal() + + /// It makes is 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 the function kruskalEdgeMap() 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 Graph &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". + /// \warning Not a regular property map, as it doesn't know its KeyType + /// \bug Missing documentation. + /// \todo This class may be of wider usage, therefore it could move to + /// maps.h + 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); + } + + /* ** ** 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 EdgeCostMap::ValueType + kruskalEdgeMap(Graph const& G, + EdgeCostMap const& in, + RetEdgeBoolMap &out) { + 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 + /// Graph::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 a vector \c tree with a code like this. + /// \code + /// std::vector tree(53); + /// kruskalEdgeMap_IteratorOut(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; + /// kruskalEdgeMap_IteratorOut(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 EdgeCostMap::ValueType + kruskalEdgeMap_IteratorOut(const Graph& G, + const EdgeCostMap& in, + RetIterator out) + { + SequenceOutput _out(out); + return kruskal(G, + KruskalMapInput(G, in), + _out); + } + + /// @} + +} //namespace hugo + +#endif //HUGO_KRUSKAL_H