COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 1970:bd88ea06ab69

Last change on this file since 1970:bd88ea06ab69 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

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