1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/lemon/kruskal.h Wed Sep 29 15:30:04 2004 +0000
1.3 @@ -0,0 +1,348 @@
1.4 +/* -*- C++ -*-
1.5 + * src/lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
1.6 + *
1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
1.9 + *
1.10 + * Permission to use, modify and distribute this software is granted
1.11 + * provided that this copyright notice appears in all copies. For
1.12 + * precise terms see the accompanying LICENSE file.
1.13 + *
1.14 + * This software is provided "AS IS" with no warranty of any kind,
1.15 + * express or implied, and with no claim as to its suitability for any
1.16 + * purpose.
1.17 + *
1.18 + */
1.19 +
1.20 +#ifndef LEMON_KRUSKAL_H
1.21 +#define LEMON_KRUSKAL_H
1.22 +
1.23 +#include <algorithm>
1.24 +#include <lemon/unionfind.h>
1.25 +
1.26 +/**
1.27 +@defgroup spantree Minimum Cost Spanning Tree Algorithms
1.28 +@ingroup galgs
1.29 +\brief This group containes the algorithms for finding a minimum cost spanning
1.30 +tree in a graph
1.31 +
1.32 +This group containes the algorithms for finding a minimum cost spanning
1.33 +tree in a graph
1.34 +*/
1.35 +
1.36 +///\ingroup spantree
1.37 +///\file
1.38 +///\brief Kruskal's algorithm to compute a minimum cost tree
1.39 +///
1.40 +///Kruskal's algorithm to compute a minimum cost tree.
1.41 +
1.42 +namespace lemon {
1.43 +
1.44 + /// \addtogroup spantree
1.45 + /// @{
1.46 +
1.47 + /// Kruskal's algorithm to find a minimum cost tree of a graph.
1.48 +
1.49 + /// This function runs Kruskal's algorithm to find a minimum cost tree.
1.50 + /// \param G The graph the algorithm runs on. The algorithm considers the
1.51 + /// graph to be undirected, the direction of the edges are not used.
1.52 + ///
1.53 + /// \param in This object is used to describe the edge costs. It must
1.54 + /// be an STL compatible 'Forward Container'
1.55 + /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
1.56 + /// where X is the type of the costs. It must contain every edge in
1.57 + /// cost-ascending order.
1.58 + ///\par
1.59 + /// For the sake of simplicity, there is a helper class KruskalMapInput,
1.60 + /// which converts a
1.61 + /// simple edge map to an input of this form. Alternatively, you can use
1.62 + /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
1.63 + /// the edge costs are given by an edge map.
1.64 + ///
1.65 + /// \retval out This must be a writable \c bool edge map.
1.66 + /// After running the algorithm
1.67 + /// this will contain the found minimum cost spanning tree: the value of an
1.68 + /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.69 + /// be set to \c false. The value of each edge will be set exactly once.
1.70 + ///
1.71 + /// \return The cost of the found tree.
1.72 +
1.73 + template <class GR, class IN, class OUT>
1.74 + typename IN::value_type::second_type
1.75 + kruskal(GR const& G, IN const& in,
1.76 + OUT& out)
1.77 + {
1.78 + typedef typename IN::value_type::second_type EdgeCost;
1.79 + typedef typename GR::template NodeMap<int> NodeIntMap;
1.80 + typedef typename GR::Node Node;
1.81 +
1.82 + NodeIntMap comp(G, -1);
1.83 + UnionFind<Node,NodeIntMap> uf(comp);
1.84 +
1.85 + EdgeCost tot_cost = 0;
1.86 + for (typename IN::const_iterator p = in.begin();
1.87 + p!=in.end(); ++p ) {
1.88 + if ( uf.join(G.head((*p).first),
1.89 + G.tail((*p).first)) ) {
1.90 + out.set((*p).first, true);
1.91 + tot_cost += (*p).second;
1.92 + }
1.93 + else {
1.94 + out.set((*p).first, false);
1.95 + }
1.96 + }
1.97 + return tot_cost;
1.98 + }
1.99 +
1.100 + /* A work-around for running Kruskal with const-reference bool maps... */
1.101 +
1.102 + /// Helper class for calling kruskal with "constant" output map.
1.103 +
1.104 + /// Helper class for calling kruskal with output maps constructed
1.105 + /// on-the-fly.
1.106 + ///
1.107 + /// A typical examle is the following call:
1.108 + /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
1.109 + /// Here, the third argument is a temporary object (which wraps around an
1.110 + /// iterator with a writable bool map interface), and thus by rules of C++
1.111 + /// is a \c const object. To enable call like this exist this class and
1.112 + /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
1.113 + /// third argument.
1.114 + template<class Map>
1.115 + class NonConstMapWr {
1.116 + const Map &m;
1.117 + public:
1.118 + typedef typename Map::ValueType ValueType;
1.119 +
1.120 + NonConstMapWr(const Map &_m) : m(_m) {}
1.121 +
1.122 + template<class KeyType>
1.123 + void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
1.124 + };
1.125 +
1.126 + template <class GR, class IN, class OUT>
1.127 + inline
1.128 + typename IN::value_type::second_type
1.129 + kruskal(GR const& G, IN const& edges, OUT const& out_map)
1.130 + {
1.131 + NonConstMapWr<OUT> map_wr(out_map);
1.132 + return kruskal(G, edges, map_wr);
1.133 + }
1.134 +
1.135 + /* ** ** Input-objects ** ** */
1.136 +
1.137 + /// Kruskal input source.
1.138 +
1.139 + /// Kruskal input source.
1.140 + ///
1.141 + /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
1.142 + ///
1.143 + /// \sa makeKruskalMapInput()
1.144 + ///
1.145 + ///\param GR The type of the graph the algorithm runs on.
1.146 + ///\param Map An edge map containing the cost of the edges.
1.147 + ///\par
1.148 + ///The cost type can be any type satisfying
1.149 + ///the STL 'LessThan comparable'
1.150 + ///concept if it also has an operator+() implemented. (It is necessary for
1.151 + ///computing the total cost of the tree).
1.152 + ///
1.153 + template<class GR, class Map>
1.154 + class KruskalMapInput
1.155 + : public std::vector< std::pair<typename GR::Edge,
1.156 + typename Map::ValueType> > {
1.157 +
1.158 + public:
1.159 + typedef std::vector< std::pair<typename GR::Edge,
1.160 + typename Map::ValueType> > Parent;
1.161 + typedef typename Parent::value_type value_type;
1.162 +
1.163 + private:
1.164 + class comparePair {
1.165 + public:
1.166 + bool operator()(const value_type& a,
1.167 + const value_type& b) {
1.168 + return a.second < b.second;
1.169 + }
1.170 + };
1.171 +
1.172 + public:
1.173 +
1.174 + void sort() {
1.175 + std::sort(this->begin(), this->end(), comparePair());
1.176 + }
1.177 +
1.178 + KruskalMapInput(GR const& G, Map const& m) {
1.179 + typedef typename GR::EdgeIt EdgeIt;
1.180 +
1.181 + for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
1.182 + sort();
1.183 + }
1.184 + };
1.185 +
1.186 + /// Creates a KruskalMapInput object for \ref kruskal()
1.187 +
1.188 + /// It makes is easier to use
1.189 + /// \ref KruskalMapInput by making it unnecessary
1.190 + /// to explicitly give the type of the parameters.
1.191 + ///
1.192 + /// In most cases you possibly
1.193 + /// want to use the function kruskalEdgeMap() instead.
1.194 + ///
1.195 + ///\param G The type of the graph the algorithm runs on.
1.196 + ///\param m An edge map containing the cost of the edges.
1.197 + ///\par
1.198 + ///The cost type can be any type satisfying the
1.199 + ///STL 'LessThan Comparable'
1.200 + ///concept if it also has an operator+() implemented. (It is necessary for
1.201 + ///computing the total cost of the tree).
1.202 + ///
1.203 + ///\return An appropriate input source for \ref kruskal().
1.204 + ///
1.205 + template<class GR, class Map>
1.206 + inline
1.207 + KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
1.208 + {
1.209 + return KruskalMapInput<GR,Map>(G,m);
1.210 + }
1.211 +
1.212 +
1.213 +
1.214 + /* ** ** Output-objects: simple writable bool maps ** ** */
1.215 +
1.216 +
1.217 +
1.218 + /// A writable bool-map that makes a sequence of "true" keys
1.219 +
1.220 + /// A writable bool-map that creates a sequence out of keys that receives
1.221 + /// the value "true".
1.222 + ///
1.223 + /// \sa makeKruskalSequenceOutput()
1.224 + ///
1.225 + /// Very often, when looking for a min cost spanning tree, we want as
1.226 + /// output a container containing the edges of the found tree. For this
1.227 + /// purpose exist this class that wraps around an STL iterator with a
1.228 + /// writable bool map interface. When a key gets value "true" this key
1.229 + /// is added to sequence pointed by the iterator.
1.230 + ///
1.231 + /// A typical usage:
1.232 + /// \code
1.233 + /// std::vector<Graph::Edge> v;
1.234 + /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
1.235 + /// \endcode
1.236 + ///
1.237 + /// For the most common case, when the input is given by a simple edge
1.238 + /// map and the output is a sequence of the tree edges, a special
1.239 + /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
1.240 + ///
1.241 + /// \warning Not a regular property map, as it doesn't know its KeyType
1.242 +
1.243 + template<class Iterator>
1.244 + class KruskalSequenceOutput {
1.245 + mutable Iterator it;
1.246 +
1.247 + public:
1.248 + typedef bool ValueType;
1.249 +
1.250 + KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
1.251 +
1.252 + template<typename KeyType>
1.253 + void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
1.254 + };
1.255 +
1.256 + template<class Iterator>
1.257 + inline
1.258 + KruskalSequenceOutput<Iterator>
1.259 + makeKruskalSequenceOutput(Iterator it) {
1.260 + return KruskalSequenceOutput<Iterator>(it);
1.261 + }
1.262 +
1.263 +
1.264 +
1.265 + /* ** ** Wrapper funtions ** ** */
1.266 +
1.267 +
1.268 +
1.269 + /// \brief Wrapper function to kruskal().
1.270 + /// Input is from an edge map, output is a plain bool map.
1.271 + ///
1.272 + /// Wrapper function to kruskal().
1.273 + /// Input is from an edge map, output is a plain bool map.
1.274 + ///
1.275 + ///\param G The type of the graph the algorithm runs on.
1.276 + ///\param in An edge map containing the cost of the edges.
1.277 + ///\par
1.278 + ///The cost type can be any type satisfying the
1.279 + ///STL 'LessThan Comparable'
1.280 + ///concept if it also has an operator+() implemented. (It is necessary for
1.281 + ///computing the total cost of the tree).
1.282 + ///
1.283 + /// \retval out This must be a writable \c bool edge map.
1.284 + /// After running the algorithm
1.285 + /// this will contain the found minimum cost spanning tree: the value of an
1.286 + /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.287 + /// be set to \c false. The value of each edge will be set exactly once.
1.288 + ///
1.289 + /// \return The cost of the found tree.
1.290 +
1.291 + template <class GR, class IN, class RET>
1.292 + inline
1.293 + typename IN::ValueType
1.294 + kruskalEdgeMap(GR const& G,
1.295 + IN const& in,
1.296 + RET &out) {
1.297 + return kruskal(G,
1.298 + KruskalMapInput<GR,IN>(G,in),
1.299 + out);
1.300 + }
1.301 +
1.302 + /// \brief Wrapper function to kruskal().
1.303 + /// Input is from an edge map, output is an STL Sequence.
1.304 + ///
1.305 + /// Wrapper function to kruskal().
1.306 + /// Input is from an edge map, output is an STL Sequence.
1.307 + ///
1.308 + ///\param G The type of the graph the algorithm runs on.
1.309 + ///\param in An edge map containing the cost of the edges.
1.310 + ///\par
1.311 + ///The cost type can be any type satisfying the
1.312 + ///STL 'LessThan Comparable'
1.313 + ///concept if it also has an operator+() implemented. (It is necessary for
1.314 + ///computing the total cost of the tree).
1.315 + ///
1.316 + /// \retval out This must be an iteraror of an STL Container with
1.317 + /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
1.318 + /// The algorithm copies the elements of the found tree into this sequence.
1.319 + /// For example, if we know that the spanning tree of the graph \c G has
1.320 + /// say 53 edges then
1.321 + /// we can put its edges into a STL vector \c tree with a code like this.
1.322 + /// \code
1.323 + /// std::vector<Edge> tree(53);
1.324 + /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
1.325 + /// \endcode
1.326 + /// Or if we don't know in advance the size of the tree, we can write this.
1.327 + /// \code
1.328 + /// std::vector<Edge> tree;
1.329 + /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
1.330 + /// \endcode
1.331 + ///
1.332 + /// \return The cost of the found tree.
1.333 + ///
1.334 + /// \bug its name does not follow the coding style.
1.335 +
1.336 + template <class GR, class IN, class RET>
1.337 + inline
1.338 + typename IN::ValueType
1.339 + kruskalEdgeMap_IteratorOut(const GR& G,
1.340 + const IN& in,
1.341 + RET out)
1.342 + {
1.343 + KruskalSequenceOutput<RET> _out(out);
1.344 + return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
1.345 + }
1.346 +
1.347 + /// @}
1.348 +
1.349 +} //namespace lemon
1.350 +
1.351 +#endif //LEMON_KRUSKAL_H