COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/kruskal.h @ 1461:9f99ede44d59

Last change on this file since 1461:9f99ede44d59 was 1449:ac7e995e47e2, checked in by Alpar Juttner, 19 years ago

Modify kruskal to work correctly with UndirGraphs?.

File size: 11.4 KB
Line 
1/* -*- C++ -*-
2 * lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
3 *
4 * Copyright (C) 2005 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
40namespace lemon {
41
42  /// \addtogroup spantree
43  /// @{
44
45  /// Kruskal's algorithm to find a minimum cost tree of a graph.
46
47  /// This function runs Kruskal's algorithm to find a minimum cost tree.
48  /// \param G The graph the algorithm runs on. The algorithm considers the
49  /// graph to be undirected, the direction of the edges are not used.
50  ///
51  /// \param in This object is used to describe the edge costs. It must
52  /// be an STL compatible 'Forward Container'
53  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
54  /// where X is the type of the costs. It must contain every edge in
55  /// cost-ascending order.
56  ///\par
57  /// For the sake of simplicity, there is a helper class KruskalMapInput,
58  /// which converts a
59  /// simple edge map to an input of this form. Alternatively, you can use
60  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
61  /// the edge costs are given by an edge map.
62  ///
63  /// \retval out This must be a writable \c bool edge map.
64  /// After running the algorithm
65  /// this will contain the found minimum cost spanning tree: the value of an
66  /// edge will be set to \c true if it belongs to the tree, otherwise it will
67  /// be set to \c false. The value of each edge will be set exactly once.
68  ///
69  /// \return The cost of the found tree.
70  ///
71  /// \todo Discuss the case of undirected graphs: In this case the algorithm
72  /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some
73  /// people would expect. So, one should be careful not to add both of the
74  /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
75  /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
76
77  template <class GR, class IN, class OUT>
78  typename IN::value_type::second_type
79  kruskal(GR const& G, IN const& in,
80                 OUT& out)
81  {
82    typedef typename IN::value_type::second_type EdgeCost;
83    typedef typename GR::template NodeMap<int> NodeIntMap;
84    typedef typename GR::Node Node;
85
86    NodeIntMap comp(G, -1);
87    UnionFind<Node,NodeIntMap> uf(comp);
88     
89    EdgeCost tot_cost = 0;
90    for (typename IN::const_iterator p = in.begin();
91         p!=in.end(); ++p ) {
92      if ( uf.join(G.target((*p).first),
93                   G.source((*p).first)) ) {
94        out.set((*p).first, true);
95        tot_cost += (*p).second;
96      }
97      else {
98        out.set((*p).first, false);
99      }
100    }
101    return tot_cost;
102  }
103
104  /* A work-around for running Kruskal with const-reference bool maps... */
105
106  /// Helper class for calling kruskal with "constant" output map.
107
108  /// Helper class for calling kruskal with output maps constructed
109  /// on-the-fly.
110  ///
111  /// A typical examle is the following call:
112  /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
113  /// Here, the third argument is a temporary object (which wraps around an
114  /// iterator with a writable bool map interface), and thus by rules of C++
115  /// is a \c const object. To enable call like this exist this class and
116  /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
117  /// third argument.
118  template<class Map>
119  class NonConstMapWr {
120    const Map &m;
121  public:
122    typedef typename Map::Value Value;
123
124    NonConstMapWr(const Map &_m) : m(_m) {}
125
126    template<class Key>
127    void set(Key const& k, Value const &v) const { m.set(k,v); }
128  };
129
130  template <class GR, class IN, class OUT>
131  inline
132  typename IN::value_type::second_type
133  kruskal(GR const& G, IN const& edges, OUT const& out_map)
134  {
135    NonConstMapWr<OUT> map_wr(out_map);
136    return kruskal(G, edges, map_wr);
137  } 
138
139  /* ** ** Input-objects ** ** */
140
141  /// Kruskal's input source.
142
143  /// Kruskal's input source.
144  ///
145  /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
146  ///
147  /// \sa makeKruskalMapInput()
148  ///
149  ///\param GR The type of the graph the algorithm runs on.
150  ///\param Map An edge map containing the cost of the edges.
151  ///\par
152  ///The cost type can be any type satisfying
153  ///the STL 'LessThan comparable'
154  ///concept if it also has an operator+() implemented. (It is necessary for
155  ///computing the total cost of the tree).
156  ///
157  template<class GR, class Map>
158  class KruskalMapInput
159    : public std::vector< std::pair<typename GR::Edge,
160                                    typename Map::Value> > {
161   
162  public:
163    typedef std::vector< std::pair<typename GR::Edge,
164                                   typename Map::Value> > Parent;
165    typedef typename Parent::value_type value_type;
166
167  private:
168    class comparePair {
169    public:
170      bool operator()(const value_type& a,
171                      const value_type& b) {
172        return a.second < b.second;
173      }
174    };
175
176    template<class _GR>
177    typename enable_if<typename _GR::UndirTag,void>::type
178    fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0)
179    {
180      for(typename GR::UndirEdgeIt e(G);e!=INVALID;++e)
181        push_back(value_type(typename GR::Edge(e,true), m[e]));
182    }
183
184    template<class _GR>
185    typename disable_if<typename _GR::UndirTag,void>::type
186    fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1)
187    {
188      for(typename GR::EdgeIt e(G);e!=INVALID;++e)
189        push_back(value_type(e, m[e]));
190    }
191   
192   
193  public:
194
195    void sort() {
196      std::sort(this->begin(), this->end(), comparePair());
197    }
198
199    KruskalMapInput(GR const& G, Map const& m) {
200      fillWithEdges(G,m);
201      sort();
202    }
203  };
204
205  /// Creates a KruskalMapInput object for \ref kruskal()
206
207  /// It makes easier to use
208  /// \ref KruskalMapInput by making it unnecessary
209  /// to explicitly give the type of the parameters.
210  ///
211  /// In most cases you possibly
212  /// want to use the function kruskalEdgeMap() instead.
213  ///
214  ///\param G The type of the graph the algorithm runs on.
215  ///\param m An edge map containing the cost of the edges.
216  ///\par
217  ///The cost type can be any type satisfying the
218  ///STL 'LessThan Comparable'
219  ///concept if it also has an operator+() implemented. (It is necessary for
220  ///computing the total cost of the tree).
221  ///
222  ///\return An appropriate input source for \ref kruskal().
223  ///
224  template<class GR, class Map>
225  inline
226  KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
227  {
228    return KruskalMapInput<GR,Map>(G,m);
229  }
230 
231 
232
233  /* ** ** Output-objects: simple writable bool maps ** ** */
234 
235
236
237  /// A writable bool-map that makes a sequence of "true" keys
238
239  /// A writable bool-map that creates a sequence out of keys that receives
240  /// the value "true".
241  ///
242  /// \sa makeKruskalSequenceOutput()
243  ///
244  /// Very often, when looking for a min cost spanning tree, we want as
245  /// output a container containing the edges of the found tree. For this
246  /// purpose exist this class that wraps around an STL iterator with a
247  /// writable bool map interface. When a key gets value "true" this key
248  /// is added to sequence pointed by the iterator.
249  ///
250  /// A typical usage:
251  /// \code
252  /// std::vector<Graph::Edge> v;
253  /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
254  /// \endcode
255  ///
256  /// For the most common case, when the input is given by a simple edge
257  /// map and the output is a sequence of the tree edges, a special
258  /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
259  ///
260  /// \warning Not a regular property map, as it doesn't know its Key
261
262  template<class Iterator>
263  class KruskalSequenceOutput {
264    mutable Iterator it;
265
266  public:
267    typedef bool Value;
268
269    KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
270
271    template<typename Key>
272    void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
273  };
274
275  template<class Iterator>
276  inline
277  KruskalSequenceOutput<Iterator>
278  makeKruskalSequenceOutput(Iterator it) {
279    return KruskalSequenceOutput<Iterator>(it);
280  }
281
282
283
284  /* ** ** Wrapper funtions ** ** */
285
286
287
288  /// \brief Wrapper function to kruskal().
289  /// Input is from an edge map, output is a plain bool map.
290  ///
291  /// Wrapper function to kruskal().
292  /// Input is from an edge map, output is a plain bool map.
293  ///
294  ///\param G The type of the graph the algorithm runs on.
295  ///\param in An edge map containing the cost of the edges.
296  ///\par
297  ///The cost type can be any type satisfying the
298  ///STL 'LessThan Comparable'
299  ///concept if it also has an operator+() implemented. (It is necessary for
300  ///computing the total cost of the tree).
301  ///
302  /// \retval out This must be a writable \c bool edge map.
303  /// After running the algorithm
304  /// this will contain the found minimum cost spanning tree: the value of an
305  /// edge will be set to \c true if it belongs to the tree, otherwise it will
306  /// be set to \c false. The value of each edge will be set exactly once.
307  ///
308  /// \return The cost of the found tree.
309
310  template <class GR, class IN, class RET>
311  inline
312  typename IN::Value
313  kruskalEdgeMap(GR const& G,
314                 IN const& in,
315                 RET &out) {
316    return kruskal(G,
317                   KruskalMapInput<GR,IN>(G,in),
318                   out);
319  }
320
321  /// \brief Wrapper function to kruskal().
322  /// Input is from an edge map, output is an STL Sequence.
323  ///
324  /// Wrapper function to kruskal().
325  /// Input is from an edge map, output is an STL Sequence.
326  ///
327  ///\param G The type of the graph the algorithm runs on.
328  ///\param in An edge map containing the cost of the edges.
329  ///\par
330  ///The cost type can be any type satisfying the
331  ///STL 'LessThan Comparable'
332  ///concept if it also has an operator+() implemented. (It is necessary for
333  ///computing the total cost of the tree).
334  ///
335  /// \retval out This must be an iteraror of an STL Container with
336  /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
337  /// The algorithm copies the elements of the found tree into this sequence.
338  /// For example, if we know that the spanning tree of the graph \c G has
339  /// say 53 edges then
340  /// we can put its edges into a STL vector \c tree with a code like this.
341  /// \code
342  /// std::vector<Edge> tree(53);
343  /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
344  /// \endcode
345  /// Or if we don't know in advance the size of the tree, we can write this.
346  /// \code
347  /// std::vector<Edge> tree;
348  /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
349  /// \endcode
350  ///
351  /// \return The cost of the found tree.
352  ///
353  /// \bug its name does not follow the coding style.
354
355  template <class GR, class IN, class RET>
356  inline
357  typename IN::Value
358  kruskalEdgeMap_IteratorOut(const GR& G,
359                             const IN& in,
360                             RET out)
361  {
362    KruskalSequenceOutput<RET> _out(out);
363    return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
364  }
365
366  /// @}
367
368} //namespace lemon
369
370#endif //LEMON_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.