COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 1935:67b38d699ea7

Last change on this file since 1935:67b38d699ea7 was 1909:2d806130e700, checked in by Mihaly Barasz, 18 years ago

Undir -> U transition

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