COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/hugo/kruskal.h @ 883:4af619b64d98

Last change on this file since 883:4af619b64d98 was 881:a9f19f38970b, checked in by Alpar Juttner, 20 years ago

Right (but still too short) documentation of the namespaces.

File size: 8.9 KB
RevLine 
[810]1// -*- c++ -*- //
2#ifndef HUGO_KRUSKAL_H
3#define HUGO_KRUSKAL_H
4
5#include <algorithm>
6#include <hugo/unionfind.h>
7
8/**
9@defgroup spantree Minimum Cost Spanning Tree Algorithms
10@ingroup galgs
11\brief This group containes the algorithms for finding a minimum cost spanning
12tree in a graph
13
14This group containes the algorithms for finding a minimum cost spanning
15tree in a graph
16*/
17
18///\ingroup spantree
19///\file
20///\brief Kruskal's algorithm to compute a minimum cost tree
21///
22///Kruskal's algorithm to compute a minimum cost tree.
23
24namespace hugo {
25
26  /// \addtogroup spantree
27  /// @{
28
29  /// Kruskal's algorithm to find a minimum cost tree of a graph.
30
31  /// This function runs Kruskal's algorithm to find a minimum cost tree.
32  /// \param G The graph the algorithm runs on. The algorithm considers the
33  /// graph to be undirected, the direction of the edges are not used.
34  ///
35  /// \param in This object is used to describe the edge costs. It must
36  /// be an STL compatible 'Forward Container'
[824]37  /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
[810]38  /// where X is the type of the costs. It must contain every edge in
39  /// cost-ascending order.
40  ///\par
41  /// For the sake of simplicity, there is a helper class KruskalMapInput,
42  /// which converts a
43  /// simple edge map to an input of this form. Alternatively, you can use
44  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
45  /// the edge costs are given by an edge map.
46  ///
47  /// \retval out This must be a writable \c bool edge map.
48  /// After running the algorithm
49  /// this will contain the found minimum cost spanning tree: the value of an
50  /// edge will be set to \c true if it belongs to the tree, otherwise it will
51  /// be set to \c false. The value of each edge will be set exactly once.
52  ///
53  /// \return The cost of the found tree.
54
[824]55  template <class GR, class IN, class OUT>
56  typename IN::value_type::second_type
57  kruskal(GR const& G, IN const& in,
58                 OUT& out)
[810]59  {
[824]60    typedef typename IN::value_type::second_type EdgeCost;
61    typedef typename GR::template NodeMap<int> NodeIntMap;
62    typedef typename GR::Node Node;
[810]63
64    NodeIntMap comp(G, -1);
65    UnionFind<Node,NodeIntMap> uf(comp);
66     
67    EdgeCost tot_cost = 0;
[824]68    for (typename IN::const_iterator p = in.begin();
[810]69         p!=in.end(); ++p ) {
70      if ( uf.join(G.head((*p).first),
71                   G.tail((*p).first)) ) {
72        out.set((*p).first, true);
73        tot_cost += (*p).second;
74      }
75      else {
76        out.set((*p).first, false);
77      }
78    }
79    return tot_cost;
80  }
81
82  /* A work-around for running Kruskal with const-reference bool maps... */
83
[812]84  ///\bug What is this? Or why doesn't it work?
[810]85  ///
[824]86  template<class Map>
[810]87  class NonConstMapWr {
88    const Map &m;
89  public:
90    typedef typename Map::ValueType ValueType;
91
92    NonConstMapWr(const Map &_m) : m(_m) {}
93
[824]94    template<class KeyType>
[810]95    void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
96  };
97
[824]98  template <class GR, class IN, class OUT>
[810]99  inline
[824]100  typename IN::ValueType
101  kruskal(GR const& G, IN const& edges,
102          OUT const& out_map)
[810]103  {
[824]104    NonConstMapWr<OUT> map_wr(out_map);
[810]105    return kruskal(G, edges, map_wr);
106  } 
107
108  /* ** ** Input-objects ** ** */
109
110  /// Kruskal input source.
111
112  /// Kruskal input source.
113  ///
114  /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
115  ///
116  /// \sa makeKruskalMapInput()
117  ///
[824]118  ///\param GR The type of the graph the algorithm runs on.
[810]119  ///\param Map An edge map containing the cost of the edges.
120  ///\par
121  ///The cost type can be any type satisfying
122  ///the STL 'LessThan comparable'
123  ///concept if it also has an operator+() implemented. (It is necessary for
124  ///computing the total cost of the tree).
125  ///
[824]126  template<class GR, class Map>
[810]127  class KruskalMapInput
[824]128    : public std::vector< std::pair<typename GR::Edge,
[810]129                                    typename Map::ValueType> > {
130   
131  public:
[824]132    typedef std::vector< std::pair<typename GR::Edge,
[810]133                                   typename Map::ValueType> > Parent;
134    typedef typename Parent::value_type value_type;
135
136  private:
137    class comparePair {
138    public:
139      bool operator()(const value_type& a,
140                      const value_type& b) {
141        return a.second < b.second;
142      }
143    };
144
145  public:
146
147    void sort() {
148      std::sort(this->begin(), this->end(), comparePair());
149    }
150
[824]151    KruskalMapInput(GR const& G, Map const& m) {
152      typedef typename GR::EdgeIt EdgeIt;
[810]153     
154      this->clear();
155      for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
156      sort();
157    }
158  };
159
160  /// Creates a KruskalMapInput object for \ref kruskal()
161
162  /// It makes is easier to use
163  /// \ref KruskalMapInput by making it unnecessary
164  /// to explicitly give the type of the parameters.
165  ///
166  /// In most cases you possibly
167  /// want to use the function kruskalEdgeMap() instead.
168  ///
169  ///\param G The type of the graph the algorithm runs on.
170  ///\param m An edge map containing the cost of the edges.
171  ///\par
172  ///The cost type can be any type satisfying the
173  ///STL 'LessThan Comparable'
174  ///concept if it also has an operator+() implemented. (It is necessary for
175  ///computing the total cost of the tree).
176  ///
177  ///\return An appropriate input source for \ref kruskal().
178  ///
[824]179  template<class GR, class Map>
[810]180  inline
[824]181  KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
[810]182  {
[824]183    return KruskalMapInput<GR,Map>(G,m);
[810]184  }
185 
186 
187  /* ** ** Output-objects: simple writable bool maps** ** */
188 
189  /// A writable bool-map that makes a sequence of "true" keys
190
191  /// A writable bool-map that creates a sequence out of keys that receives
192  /// the value "true".
193  /// \warning Not a regular property map, as it doesn't know its KeyType
194  /// \bug Missing documentation.
195  /// \todo This class may be of wider usage, therefore it could move to
196  /// <tt>maps.h</tt>
[824]197  template<class Iterator>
[810]198  class SequenceOutput {
199    mutable Iterator it;
200
201  public:
202    typedef bool ValueType;
203
204    SequenceOutput(Iterator const &_it) : it(_it) {}
205
206    template<typename KeyType>
207    void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
208  };
209
[824]210  template<class Iterator>
[810]211  inline
212  SequenceOutput<Iterator>
213  makeSequenceOutput(Iterator it) {
214    return SequenceOutput<Iterator>(it);
215  }
216
217  /* ** ** Wrapper funtions ** ** */
218
219
220  /// \brief Wrapper function to kruskal().
221  /// Input is from an edge map, output is a plain bool map.
222  ///
223  /// Wrapper function to kruskal().
224  /// Input is from an edge map, output is a plain bool map.
225  ///
226  ///\param G The type of the graph the algorithm runs on.
227  ///\param in An edge map containing the cost of the edges.
228  ///\par
229  ///The cost type can be any type satisfying the
230  ///STL 'LessThan Comparable'
231  ///concept if it also has an operator+() implemented. (It is necessary for
232  ///computing the total cost of the tree).
233  ///
234  /// \retval out This must be a writable \c bool edge map.
235  /// After running the algorithm
236  /// this will contain the found minimum cost spanning tree: the value of an
237  /// edge will be set to \c true if it belongs to the tree, otherwise it will
238  /// be set to \c false. The value of each edge will be set exactly once.
239  ///
240  /// \return The cost of the found tree.
241
242
[824]243  template <class GR, class IN, class RET>
[810]244  inline
[824]245  typename IN::ValueType
246  kruskalEdgeMap(GR const& G,
247                 IN const& in,
248                 RET &out) {
[810]249    return kruskal(G,
[824]250                   KruskalMapInput<GR,IN>(G,in),
[810]251                   out);
252  }
253
254  /// \brief Wrapper function to kruskal().
255  /// Input is from an edge map, output is an STL Sequence.
256  ///
257  /// Wrapper function to kruskal().
258  /// Input is from an edge map, output is an STL Sequence.
259  ///
260  ///\param G The type of the graph the algorithm runs on.
261  ///\param in An edge map containing the cost of the edges.
262  ///\par
263  ///The cost type can be any type satisfying the
264  ///STL 'LessThan Comparable'
265  ///concept if it also has an operator+() implemented. (It is necessary for
266  ///computing the total cost of the tree).
267  ///
268  /// \retval out This must be an iteraror of an STL Container with
[824]269  /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
[810]270  /// The algorithm copies the elements of the found tree into this sequence.
271  /// For example, if we know that the spanning tree of the graph \c G has
272  /// say 53 edges then
[824]273  /// we can put its edges into a STL vector \c tree with a code like this.
[810]274  /// \code
275  /// std::vector<Edge> tree(53);
276  /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
277  /// \endcode
278  /// Or if we don't know in advance the size of the tree, we can write this.
279  /// \code
280  /// std::vector<Edge> tree;
281  /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
282  /// \endcode
283  ///
284  /// \return The cost of the found tree.
285  ///
286  /// \bug its name does not follow the coding style.
[824]287  template <class GR, class IN, class RET>
[810]288  inline
[824]289  typename IN::ValueType
290  kruskalEdgeMap_IteratorOut(const GR& G,
291                             const IN& in,
292                             RET out)
[810]293  {
[824]294    SequenceOutput<RET> _out(out);
[810]295    return kruskal(G,
[824]296                   KruskalMapInput<GR,IN>(G, in),
[810]297                   _out);
298  }
299
300  /// @}
301
302} //namespace hugo
303
304#endif //HUGO_KRUSKAL_H
Note: See TracBrowser for help on using the repository browser.