diff -r d8475431bbbb -r 8e85e6bbefdf src/lemon/kruskal.h --- a/src/lemon/kruskal.h Sat May 21 21:04:57 2005 +0000 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,348 +0,0 @@ -/* -*- C++ -*- - * src/lemon/kruskal.h - Part of LEMON, a generic C++ optimization library - * - * Copyright (C) 2005 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 - -/** -@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 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. - /// \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 IN::value_type::second_type - kruskal(GR const& G, IN const& in, - OUT& out) - { - typedef typename IN::value_type::second_type EdgeCost; - typedef typename GR::template NodeMap NodeIntMap; - typedef typename GR::Node Node; - - NodeIntMap comp(G, -1); - UnionFind uf(comp); - - 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::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) - { - 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 kruskalEdgeMap() 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; - } - }; - - public: - - void sort() { - std::sort(this->begin(), this->end(), comparePair()); - } - - KruskalMapInput(GR const& G, Map const& m) { - typedef typename GR::EdgeIt EdgeIt; - - for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e])); - 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 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 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 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 - kruskalEdgeMap(GR const& G, - IN const& in, - RET &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 - /// 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 a STL 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 IN::Value - kruskalEdgeMap_IteratorOut(const GR& G, - const IN& in, - RET out) - { - KruskalSequenceOutput _out(out); - return kruskal(G, KruskalMapInput(G, in), _out); - } - - /// @} - -} //namespace lemon - -#endif //LEMON_KRUSKAL_H