COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 1951:cb7a6e0573bc

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