1.1 --- a/src/lemon/kruskal.h Sat May 21 21:04:57 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,348 +0,0 @@
1.4 -/* -*- C++ -*-
1.5 - * src/lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
1.6 - *
1.7 - * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.8 - * (Egervary Research Group on Combinatorial Optimization, 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.target((*p).first),
1.89 - G.source((*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::Value Value;
1.119 -
1.120 - NonConstMapWr(const Map &_m) : m(_m) {}
1.121 -
1.122 - template<class Key>
1.123 - void set(Key const& k, Value 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's input source.
1.138 -
1.139 - /// Kruskal's 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::Value> > {
1.157 -
1.158 - public:
1.159 - typedef std::vector< std::pair<typename GR::Edge,
1.160 - typename Map::Value> > 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 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 Key
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 Value;
1.249 -
1.250 - KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
1.251 -
1.252 - template<typename Key>
1.253 - void set(Key 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::Value
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::Value
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