# source:lemon-0.x/lemon/kruskal.h@1555:48769ac7ec32

Last change on this file since 1555:48769ac7ec32 was 1555:48769ac7ec32, checked in by Alpar Juttner, 18 years ago

Doc improvement

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