Turn off 32 bit only tests, cont'd.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_KRUSKAL_H
20 #define LEMON_KRUSKAL_H
24 #include <lemon/unionfind.h>
25 #include <lemon/bits/utility.h>
26 #include <lemon/bits/traits.h>
30 ///\brief Kruskal's algorithm to compute a minimum cost tree
32 ///Kruskal's algorithm to compute a minimum cost tree.
34 ///\todo The file still needs some clean-up.
38 /// \addtogroup spantree
41 /// Kruskal's algorithm to find a minimum cost tree of a graph.
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.
46 /// \param g The graph the algorithm runs on.
47 /// It can be either \ref concepts::Graph "directed" or
48 /// \ref concepts::UGraph "undirected".
49 /// If the graph is directed, the algorithm consider it to be
50 /// undirected by disregarding the direction of the edges.
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.
61 /// \retval out Here we also have a choise.
62 /// - It 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 an STL vector \c tree with a code like this.
74 /// std::vector<Edge> tree(53);
75 /// kruskal(g,cost,tree.begin());
77 /// Or if we don't know in advance the size of the tree, we can write this.
79 /// std::vector<Edge> tree;
80 /// kruskal(g,cost,std::back_inserter(tree));
83 /// \return The cost of the found tree.
85 /// \warning If kruskal runs on an
86 /// \ref lemon::concepts::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.
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.)
98 template <class GR, class IN, class OUT>
99 typename IN::value_type::second_type
100 kruskal(GR const& g, IN const& in,
103 template <class GR, class IN, class OUT>
104 typename IN::value_type::second_type
105 kruskal(GR const& g, IN const& in,
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)
116 typedef typename IN::value_type::second_type EdgeCost;
117 typedef typename GR::template NodeMap<int> NodeIntMap;
118 typedef typename GR::Node Node;
121 UnionFind<Node,NodeIntMap> uf(comp);
122 for (typename GR::NodeIt it(g); it != INVALID; ++it) {
126 EdgeCost tot_cost = 0;
127 for (typename IN::const_iterator p = in.begin();
129 if ( uf.join(g.target((*p).first),
130 g.source((*p).first)) ) {
131 out.set((*p).first, true);
132 tot_cost += (*p).second;
135 out.set((*p).first, false);
145 /* A work-around for running Kruskal with const-reference bool maps... */
147 /// Helper class for calling kruskal with "constant" output map.
149 /// Helper class for calling kruskal with output maps constructed
152 /// A typical examle is the following call:
153 /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.
154 /// Here, the third argument is a temporary object (which wraps around an
155 /// iterator with a writable bool map interface), and thus by rules of C++
156 /// is a \c const object. To enable call like this exist this class and
157 /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
160 class NonConstMapWr {
163 typedef typename Map::Key Key;
164 typedef typename Map::Value Value;
166 NonConstMapWr(const Map &_m) : m(_m) {}
169 void set(Key const& k, Value const &v) const { m.set(k,v); }
172 template <class GR, class IN, class OUT>
174 typename IN::value_type::second_type
175 kruskal(GR const& g, IN const& edges, OUT const& out_map,
176 // typename IN::value_type::first_type = typename GR::Edge(),
177 // typename OUT::Key = GR::Edge()
178 const typename IN::value_type::first_type * =
179 (const typename IN::value_type::first_type *)(0),
180 const typename OUT::Key * = (const typename OUT::Key *)(0)
183 NonConstMapWr<OUT> map_wr(out_map);
184 return kruskal(g, edges, map_wr);
187 /* ** ** Input-objects ** ** */
189 /// Kruskal's input source.
191 /// Kruskal's input source.
193 /// In most cases you possibly want to use the \ref kruskal() instead.
195 /// \sa makeKruskalMapInput()
197 ///\param GR The type of the graph the algorithm runs on.
198 ///\param Map An edge map containing the cost of the edges.
200 ///The cost type can be any type satisfying
201 ///the STL 'LessThan comparable'
202 ///concept if it also has an operator+() implemented. (It is necessary for
203 ///computing the total cost of the tree).
205 template<class GR, class Map>
206 class KruskalMapInput
207 : public std::vector< std::pair<typename GR::Edge,
208 typename Map::Value> > {
211 typedef std::vector< std::pair<typename GR::Edge,
212 typename Map::Value> > Parent;
213 typedef typename Parent::value_type value_type;
218 bool operator()(const value_type& a,
219 const value_type& b) {
220 return a.second < b.second;
225 typename enable_if<UndirectedTagIndicator<_GR>,void>::type
226 fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0)
228 for(typename GR::UEdgeIt e(g);e!=INVALID;++e)
229 push_back(value_type(g.direct(e, true), m[e]));
233 typename disable_if<UndirectedTagIndicator<_GR>,void>::type
234 fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1)
236 for(typename GR::EdgeIt e(g);e!=INVALID;++e)
237 push_back(value_type(e, m[e]));
244 std::sort(this->begin(), this->end(), comparePair());
247 KruskalMapInput(GR const& g, Map const& m) {
253 /// Creates a KruskalMapInput object for \ref kruskal()
255 /// It makes easier to use
256 /// \ref KruskalMapInput by making it unnecessary
257 /// to explicitly give the type of the parameters.
259 /// In most cases you possibly
260 /// want to use \ref kruskal() instead.
262 ///\param g The type of the graph the algorithm runs on.
263 ///\param m An edge map containing the cost of the edges.
265 ///The cost type can be any type satisfying the
266 ///STL 'LessThan Comparable'
267 ///concept if it also has an operator+() implemented. (It is necessary for
268 ///computing the total cost of the tree).
270 ///\return An appropriate input source for \ref kruskal().
272 template<class GR, class Map>
274 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
276 return KruskalMapInput<GR,Map>(g,m);
281 /* ** ** Output-objects: simple writable bool maps ** ** */
285 /// A writable bool-map that makes a sequence of "true" keys
287 /// A writable bool-map that creates a sequence out of keys that receives
288 /// the value "true".
290 /// \sa makeKruskalSequenceOutput()
292 /// Very often, when looking for a min cost spanning tree, we want as
293 /// output a container containing the edges of the found tree. For this
294 /// purpose exist this class that wraps around an STL iterator with a
295 /// writable bool map interface. When a key gets value "true" this key
296 /// is added to sequence pointed by the iterator.
300 /// std::vector<Graph::Edge> v;
301 /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
304 /// For the most common case, when the input is given by a simple edge
305 /// map and the output is a sequence of the tree edges, a special
306 /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
308 /// \warning Not a regular property map, as it doesn't know its Key
310 template<class Iterator>
311 class KruskalSequenceOutput {
315 typedef typename std::iterator_traits<Iterator>::value_type Key;
318 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
320 template<typename Key>
321 void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
324 template<class Iterator>
326 KruskalSequenceOutput<Iterator>
327 makeKruskalSequenceOutput(Iterator it) {
328 return KruskalSequenceOutput<Iterator>(it);
333 /* ** ** Wrapper funtions ** ** */
335 // \brief Wrapper function to kruskal().
336 // Input is from an edge map, output is a plain bool map.
338 // Wrapper function to kruskal().
339 // Input is from an edge map, output is a plain bool map.
341 // \param g The type of the graph the algorithm runs on.
342 // \param in An edge map containing the cost of the edges.
344 // The cost type can be any type satisfying the
345 // STL 'LessThan Comparable'
346 // concept if it also has an operator+() implemented. (It is necessary for
347 // computing the total cost of the tree).
349 // \retval out This must be a writable \c bool edge map.
350 // After running the algorithm
351 // this will contain the found minimum cost spanning tree: the value of an
352 // edge will be set to \c true if it belongs to the tree, otherwise it will
353 // be set to \c false. The value of each edge will be set exactly once.
355 // \return The cost of the found tree.
357 template <class GR, class IN, class RET>
363 // typename IN::Key = typename GR::Edge(),
364 //typename IN::Key = typename IN::Key (),
365 // typename RET::Key = typename GR::Edge()
366 const typename IN::Key * = (const typename IN::Key *)(0),
367 const typename RET::Key * = (const typename RET::Key *)(0)
371 KruskalMapInput<GR,IN>(g,in),
375 // \brief Wrapper function to kruskal().
376 // Input is from an edge map, output is an STL Sequence.
378 // Wrapper function to kruskal().
379 // Input is from an edge map, output is an STL Sequence.
381 // \param g The type of the graph the algorithm runs on.
382 // \param in An edge map containing the cost of the edges.
384 // The cost type can be any type satisfying the
385 // STL 'LessThan Comparable'
386 // concept if it also has an operator+() implemented. (It is necessary for
387 // computing the total cost of the tree).
389 // \retval out This must be an iteraror of an STL Container with
390 // <tt>GR::Edge</tt> as its <tt>value_type</tt>.
391 // The algorithm copies the elements of the found tree into this sequence.
392 // For example, if we know that the spanning tree of the graph \c g has
393 // say 53 edges, then
394 // we can put its edges into an STL vector \c tree with a code like this.
396 // std::vector<Edge> tree(53);
397 // kruskal(g,cost,tree.begin());
399 // Or if we don't know in advance the size of the tree, we can write this.
401 // std::vector<Edge> tree;
402 // kruskal(g,cost,std::back_inserter(tree));
405 // \return The cost of the found tree.
407 // \bug its name does not follow the coding style.
409 template <class GR, class IN, class RET>
415 const typename RET::value_type * =
416 (const typename RET::value_type *)(0)
419 KruskalSequenceOutput<RET> _out(out);
420 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
423 template <class GR, class IN, class RET>
431 KruskalSequenceOutput<RET*> _out(out);
432 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
439 #endif //LEMON_KRUSKAL_H