COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 1981:81c8efe92706

Last change on this file since 1981:81c8efe92706 was 1979:c2992fd74dad, checked in by Balazs Dezso, 18 years ago

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

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