COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 2259:da142c310d02

Last change on this file since 2259:da142c310d02 was 2259:da142c310d02, checked in by Alpar Juttner, 13 years ago

Spellcheck

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