More docs

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