# source:lemon-0.x/src/lemon/kruskal.h@948:bc86b64f958e

Last change on this file since 948:bc86b64f958e was 921:818510fa3d99, checked in by Alpar Juttner, 16 years ago

hugo -> lemon

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