COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 2162:6831fa007688

Last change on this file since 2162:6831fa007688 was 2111:ea1fa1bc3f6d, checked in by Balazs Dezso, 18 years ago

Removing concepts for extendable and erasable graphs
Renaming StaticGraph? to Graph

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