# source:lemon-0.x/src/hugo/kruskal.h@824:157115b5814a

Last change on this file since 824:157115b5814a was 824:157115b5814a, checked in by Alpar Juttner, 16 years ago

Shorter template parameter names to be more readable in Doxygen.

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