COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 1461:9f99ede44d59

Last change on this file since 1461:9f99ede44d59 was 1449:ac7e995e47e2, checked in by Alpar Juttner, 19 years ago

Modify kruskal to work correctly with UndirGraphs?.

File size: 11.4 KB
RevLine 
[906]1/* -*- C++ -*-
[1435]2 * lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
[906]3 *
[1164]4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
[1359]5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
[906]6 *
7 * Permission to use, modify and distribute this software is granted
8 * provided that this copyright notice appears in all copies. For
9 * precise terms see the accompanying LICENSE file.
10 *
11 * This software is provided "AS IS" with no warranty of any kind,
12 * express or implied, and with no claim as to its suitability for any
13 * purpose.
14 *
15 */
16
[921]17#ifndef LEMON_KRUSKAL_H
18#define LEMON_KRUSKAL_H
[810]19
20#include <algorithm>
[921]21#include <lemon/unionfind.h>
[1449]22#include<lemon/utility.h>
[810]23
24/**
25@defgroup spantree Minimum Cost Spanning Tree Algorithms
26@ingroup galgs
27\brief This group containes the algorithms for finding a minimum cost spanning
28tree in a graph
29
30This group containes the algorithms for finding a minimum cost spanning
31tree in a graph
32*/
33
34///\ingroup spantree
35///\file
36///\brief Kruskal's algorithm to compute a minimum cost tree
37///
38///Kruskal's algorithm to compute a minimum cost tree.
39
[921]40namespace lemon {
[810]41
42  /// \addtogroup spantree
43  /// @{
44
45  /// Kruskal's algorithm to find a minimum cost tree of a graph.
46
47  /// This function runs Kruskal's algorithm to find a minimum cost tree.
48  /// \param G The graph the algorithm runs on. The algorithm considers the
49  /// graph to be undirected, the direction of the edges are not used.
50  ///
51  /// \param in This object is used to describe the edge costs. It must
52  /// be an STL compatible 'Forward Container'
[824]53  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
[810]54  /// where X is the type of the costs. It must contain every edge in
55  /// cost-ascending order.
56  ///\par
57  /// For the sake of simplicity, there is a helper class KruskalMapInput,
58  /// which converts a
59  /// simple edge map to an input of this form. Alternatively, you can use
60  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
61  /// the edge costs are given by an edge map.
62  ///
63  /// \retval out This must be a writable \c bool edge map.
64  /// After running the algorithm
65  /// this will contain the found minimum cost spanning tree: the value of an
66  /// edge will be set to \c true if it belongs to the tree, otherwise it will
67  /// be set to \c false. The value of each edge will be set exactly once.
68  ///
69  /// \return The cost of the found tree.
[1449]70  ///
71  /// \todo Discuss the case of undirected graphs: In this case the algorithm
72  /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some
73  /// people would expect. So, one should be careful not to add both of the
74  /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
75  /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
[810]76
[824]77  template <class GR, class IN, class OUT>
78  typename IN::value_type::second_type
79  kruskal(GR const& G, IN const& in,
80                 OUT& out)
[810]81  {
[824]82    typedef typename IN::value_type::second_type EdgeCost;
83    typedef typename GR::template NodeMap<int> NodeIntMap;
84    typedef typename GR::Node Node;
[810]85
86    NodeIntMap comp(G, -1);
87    UnionFind<Node,NodeIntMap> uf(comp);
88     
89    EdgeCost tot_cost = 0;
[824]90    for (typename IN::const_iterator p = in.begin();
[810]91         p!=in.end(); ++p ) {
[986]92      if ( uf.join(G.target((*p).first),
93                   G.source((*p).first)) ) {
[810]94        out.set((*p).first, true);
95        tot_cost += (*p).second;
96      }
97      else {
98        out.set((*p).first, false);
99      }
100    }
101    return tot_cost;
102  }
103
104  /* A work-around for running Kruskal with const-reference bool maps... */
105
[885]106  /// Helper class for calling kruskal with "constant" output map.
107
108  /// Helper class for calling kruskal with output maps constructed
109  /// on-the-fly.
[810]110  ///
[885]111  /// A typical examle is the following call:
112  /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
113  /// Here, the third argument is a temporary object (which wraps around an
114  /// iterator with a writable bool map interface), and thus by rules of C++
115  /// is a \c const object. To enable call like this exist this class and
116  /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
117  /// third argument.
[824]118  template<class Map>
[810]119  class NonConstMapWr {
120    const Map &m;
121  public:
[987]122    typedef typename Map::Value Value;
[810]123
124    NonConstMapWr(const Map &_m) : m(_m) {}
125
[987]126    template<class Key>
127    void set(Key const& k, Value const &v) const { m.set(k,v); }
[810]128  };
129
[824]130  template <class GR, class IN, class OUT>
[810]131  inline
[885]132  typename IN::value_type::second_type
133  kruskal(GR const& G, IN const& edges, OUT const& out_map)
[810]134  {
[824]135    NonConstMapWr<OUT> map_wr(out_map);
[810]136    return kruskal(G, edges, map_wr);
137  } 
138
139  /* ** ** Input-objects ** ** */
140
[1274]141  /// Kruskal's input source.
[810]142
[1274]143  /// Kruskal's input source.
[810]144  ///
145  /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
146  ///
147  /// \sa makeKruskalMapInput()
148  ///
[824]149  ///\param GR The type of the graph the algorithm runs on.
[810]150  ///\param Map An edge map containing the cost of the edges.
151  ///\par
152  ///The cost type can be any type satisfying
153  ///the STL 'LessThan comparable'
154  ///concept if it also has an operator+() implemented. (It is necessary for
155  ///computing the total cost of the tree).
156  ///
[824]157  template<class GR, class Map>
[810]158  class KruskalMapInput
[824]159    : public std::vector< std::pair<typename GR::Edge,
[987]160                                    typename Map::Value> > {
[810]161   
162  public:
[824]163    typedef std::vector< std::pair<typename GR::Edge,
[987]164                                   typename Map::Value> > Parent;
[810]165    typedef typename Parent::value_type value_type;
166
167  private:
168    class comparePair {
169    public:
170      bool operator()(const value_type& a,
171                      const value_type& b) {
172        return a.second < b.second;
173      }
174    };
175
[1449]176    template<class _GR>
177    typename enable_if<typename _GR::UndirTag,void>::type
178    fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0)
179    {
180      for(typename GR::UndirEdgeIt e(G);e!=INVALID;++e)
181        push_back(value_type(typename GR::Edge(e,true), m[e]));
182    }
183
184    template<class _GR>
185    typename disable_if<typename _GR::UndirTag,void>::type
186    fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1)
187    {
188      for(typename GR::EdgeIt e(G);e!=INVALID;++e)
189        push_back(value_type(e, m[e]));
190    }
191   
192   
[810]193  public:
194
195    void sort() {
196      std::sort(this->begin(), this->end(), comparePair());
197    }
198
[824]199    KruskalMapInput(GR const& G, Map const& m) {
[1449]200      fillWithEdges(G,m);
[810]201      sort();
202    }
203  };
204
205  /// Creates a KruskalMapInput object for \ref kruskal()
206
[1274]207  /// It makes easier to use
[810]208  /// \ref KruskalMapInput by making it unnecessary
209  /// to explicitly give the type of the parameters.
210  ///
211  /// In most cases you possibly
212  /// want to use the function kruskalEdgeMap() instead.
213  ///
214  ///\param G The type of the graph the algorithm runs on.
215  ///\param m An edge map containing the cost of the edges.
216  ///\par
217  ///The cost type can be any type satisfying the
218  ///STL 'LessThan Comparable'
219  ///concept if it also has an operator+() implemented. (It is necessary for
220  ///computing the total cost of the tree).
221  ///
222  ///\return An appropriate input source for \ref kruskal().
223  ///
[824]224  template<class GR, class Map>
[810]225  inline
[824]226  KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
[810]227  {
[824]228    return KruskalMapInput<GR,Map>(G,m);
[810]229  }
230 
231 
[885]232
233  /* ** ** Output-objects: simple writable bool maps ** ** */
[810]234 
[885]235
236
[810]237  /// A writable bool-map that makes a sequence of "true" keys
238
239  /// A writable bool-map that creates a sequence out of keys that receives
240  /// the value "true".
[885]241  ///
242  /// \sa makeKruskalSequenceOutput()
243  ///
244  /// Very often, when looking for a min cost spanning tree, we want as
245  /// output a container containing the edges of the found tree. For this
246  /// purpose exist this class that wraps around an STL iterator with a
247  /// writable bool map interface. When a key gets value "true" this key
248  /// is added to sequence pointed by the iterator.
249  ///
250  /// A typical usage:
251  /// \code
252  /// std::vector<Graph::Edge> v;
253  /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
254  /// \endcode
255  ///
256  /// For the most common case, when the input is given by a simple edge
257  /// map and the output is a sequence of the tree edges, a special
258  /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
259  ///
[987]260  /// \warning Not a regular property map, as it doesn't know its Key
[885]261
[824]262  template<class Iterator>
[885]263  class KruskalSequenceOutput {
[810]264    mutable Iterator it;
265
266  public:
[987]267    typedef bool Value;
[810]268
[885]269    KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
[810]270
[987]271    template<typename Key>
272    void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
[810]273  };
274
[824]275  template<class Iterator>
[810]276  inline
[885]277  KruskalSequenceOutput<Iterator>
278  makeKruskalSequenceOutput(Iterator it) {
279    return KruskalSequenceOutput<Iterator>(it);
[810]280  }
281
[885]282
283
[810]284  /* ** ** Wrapper funtions ** ** */
285
286
[885]287
[810]288  /// \brief Wrapper function to kruskal().
289  /// Input is from an edge map, output is a plain bool map.
290  ///
291  /// Wrapper function to kruskal().
292  /// Input is from an edge map, output is a plain bool map.
293  ///
294  ///\param G The type of the graph the algorithm runs on.
295  ///\param in An edge map containing the cost of the edges.
296  ///\par
297  ///The cost type can be any type satisfying the
298  ///STL 'LessThan Comparable'
299  ///concept if it also has an operator+() implemented. (It is necessary for
300  ///computing the total cost of the tree).
301  ///
302  /// \retval out This must be a writable \c bool edge map.
303  /// After running the algorithm
304  /// this will contain the found minimum cost spanning tree: the value of an
305  /// edge will be set to \c true if it belongs to the tree, otherwise it will
306  /// be set to \c false. The value of each edge will be set exactly once.
307  ///
308  /// \return The cost of the found tree.
309
[824]310  template <class GR, class IN, class RET>
[810]311  inline
[987]312  typename IN::Value
[824]313  kruskalEdgeMap(GR const& G,
314                 IN const& in,
315                 RET &out) {
[810]316    return kruskal(G,
[824]317                   KruskalMapInput<GR,IN>(G,in),
[810]318                   out);
319  }
320
321  /// \brief Wrapper function to kruskal().
322  /// Input is from an edge map, output is an STL Sequence.
323  ///
324  /// Wrapper function to kruskal().
325  /// Input is from an edge map, output is an STL Sequence.
326  ///
327  ///\param G The type of the graph the algorithm runs on.
328  ///\param in An edge map containing the cost of the edges.
329  ///\par
330  ///The cost type can be any type satisfying the
331  ///STL 'LessThan Comparable'
332  ///concept if it also has an operator+() implemented. (It is necessary for
333  ///computing the total cost of the tree).
334  ///
335  /// \retval out This must be an iteraror of an STL Container with
[824]336  /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
[810]337  /// The algorithm copies the elements of the found tree into this sequence.
338  /// For example, if we know that the spanning tree of the graph \c G has
339  /// say 53 edges then
[824]340  /// we can put its edges into a STL vector \c tree with a code like this.
[810]341  /// \code
342  /// std::vector<Edge> tree(53);
343  /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
344  /// \endcode
345  /// Or if we don't know in advance the size of the tree, we can write this.
346  /// \code
347  /// std::vector<Edge> tree;
348  /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
349  /// \endcode
350  ///
351  /// \return The cost of the found tree.
352  ///
353  /// \bug its name does not follow the coding style.
[885]354
[824]355  template <class GR, class IN, class RET>
[810]356  inline
[987]357  typename IN::Value
[824]358  kruskalEdgeMap_IteratorOut(const GR& G,
359                             const IN& in,
360                             RET out)
[810]361  {
[885]362    KruskalSequenceOutput<RET> _out(out);
363    return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
[810]364  }
365
366  /// @}
367
[921]368} //namespace lemon
[810]369
[921]370#endif //LEMON_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.