COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 12 years ago

Happy New Year to all source files!

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