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