MapSelector has become a standalone class.
2 * lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
17 #ifndef LEMON_KRUSKAL_H
18 #define LEMON_KRUSKAL_H
21 #include <lemon/unionfind.h>
22 #include<lemon/utility.h>
25 @defgroup spantree Minimum Cost Spanning Tree Algorithms
27 \brief This group containes the algorithms for finding a minimum cost spanning
30 This group containes the algorithms for finding a minimum cost spanning
36 ///\brief Kruskal's algorithm to compute a minimum cost tree
38 ///Kruskal's algorithm to compute a minimum cost tree.
40 ///\todo The file still needs some clean-up.
44 /// \addtogroup spantree
47 /// Kruskal's algorithm to find a minimum cost tree of a graph.
49 /// This function runs Kruskal's algorithm to find a minimum cost tree.
50 /// Due to hard C++ hacking, it accepts various input and output types.
52 /// \param g The graph the algorithm runs on.
53 /// It can be either \ref concept::StaticGraph "directed" or
54 /// \ref concept::UndirGraph "undirected".
55 /// If the graph is directed, the algorithm consider it to be
56 /// undirected by disregarding the direction of the edges.
58 /// \param in This object is used to describe the edge costs. It can be one
59 /// of the following choices.
60 /// - An STL compatible 'Forward Container'
61 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
62 /// where \c X is the type of the costs. The pairs indicates the edges along
63 /// with the assigned cost. <em>They must be in a
64 /// cost-ascending order.</em>
65 /// - Any readable Edge map. The values of the map indicate the edge costs.
67 /// \retval out Here we also have a choise.
68 /// - Is can be a writable \c bool edge map.
69 /// After running the algorithm
70 /// this will contain the found minimum cost spanning tree: the value of an
71 /// edge will be set to \c true if it belongs to the tree, otherwise it will
72 /// be set to \c false. The value of each edge will be set exactly once.
73 /// - It can also be an iteraror of an STL Container with
74 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
75 /// The algorithm copies the elements of the found tree into this sequence.
76 /// For example, if we know that the spanning tree of the graph \c g has
77 /// say 53 edges, then
78 /// we can put its edges into a STL vector \c tree with a code like this.
80 /// std::vector<Edge> tree(53);
81 /// kruskal(g,cost,tree.begin());
83 /// Or if we don't know in advance the size of the tree, we can write this.
85 /// std::vector<Edge> tree;
86 /// kruskal(g,cost,std::back_inserter(tree));
89 /// \return The cost of the found tree.
91 /// \warning If kruskal is run on an
92 /// \ref lemon::concept::UndirGraph "undirected graph", be sure that the
93 /// map storing the tree is also undirected
94 /// (e.g. UndirListGraph::UndirEdgeMap<bool>, otherwise the values of the
95 /// half of the edges will not be set.
97 /// \todo Discuss the case of undirected graphs: In this case the algorithm
98 /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some
99 /// people would expect. So, one should be careful not to add both of the
100 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
101 /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.)
104 template <class GR, class IN, class OUT>
105 typename IN::value_type::second_type
106 kruskal(GR const& g, IN const& in,
109 template <class GR, class IN, class OUT>
110 typename IN::value_type::second_type
111 kruskal(GR const& g, IN const& in,
113 // typename IN::value_type::first_type = typename GR::Edge()
114 // ,typename OUT::Key = OUT::Key()
115 // //,typename OUT::Key = typename GR::Edge()
116 const typename IN::value_type::first_type * =
117 (const typename IN::value_type::first_type *)(0),
118 const typename OUT::Key * = (const typename OUT::Key *)(0)
122 typedef typename IN::value_type::second_type EdgeCost;
123 typedef typename GR::template NodeMap<int> NodeIntMap;
124 typedef typename GR::Node Node;
126 NodeIntMap comp(g, -1);
127 UnionFind<Node,NodeIntMap> uf(comp);
129 EdgeCost tot_cost = 0;
130 for (typename IN::const_iterator p = in.begin();
132 if ( uf.join(g.target((*p).first),
133 g.source((*p).first)) ) {
134 out.set((*p).first, true);
135 tot_cost += (*p).second;
138 out.set((*p).first, false);
148 /* A work-around for running Kruskal with const-reference bool maps... */
150 /// Helper class for calling kruskal with "constant" output map.
152 /// Helper class for calling kruskal with output maps constructed
155 /// A typical examle is the following call:
156 /// <tt>kruskal(g, some_input, makeSequenceOutput(iterator))</tt>.
157 /// Here, the third argument is a temporary object (which wraps around an
158 /// iterator with a writable bool map interface), and thus by rules of C++
159 /// is a \c const object. To enable call like this exist this class and
160 /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
163 class NonConstMapWr {
166 typedef typename Map::Key Key;
167 typedef typename Map::Value Value;
169 NonConstMapWr(const Map &_m) : m(_m) {}
172 void set(Key const& k, Value const &v) const { m.set(k,v); }
175 template <class GR, class IN, class OUT>
177 typename IN::value_type::second_type
178 kruskal(GR const& g, IN const& edges, OUT const& out_map,
179 // typename IN::value_type::first_type = typename GR::Edge(),
180 // typename OUT::Key = GR::Edge()
181 const typename IN::value_type::first_type * =
182 (const typename IN::value_type::first_type *)(0),
183 const typename OUT::Key * = (const typename OUT::Key *)(0)
186 NonConstMapWr<OUT> map_wr(out_map);
187 return kruskal(g, edges, map_wr);
190 /* ** ** Input-objects ** ** */
192 /// Kruskal's input source.
194 /// Kruskal's input source.
196 /// In most cases you possibly want to use the \ref kruskal() instead.
198 /// \sa makeKruskalMapInput()
200 ///\param GR The type of the graph the algorithm runs on.
201 ///\param Map An edge map containing the cost of the edges.
203 ///The cost type can be any type satisfying
204 ///the STL 'LessThan comparable'
205 ///concept if it also has an operator+() implemented. (It is necessary for
206 ///computing the total cost of the tree).
208 template<class GR, class Map>
209 class KruskalMapInput
210 : public std::vector< std::pair<typename GR::Edge,
211 typename Map::Value> > {
214 typedef std::vector< std::pair<typename GR::Edge,
215 typename Map::Value> > Parent;
216 typedef typename Parent::value_type value_type;
221 bool operator()(const value_type& a,
222 const value_type& b) {
223 return a.second < b.second;
228 typename enable_if<typename _GR::UndirTag,void>::type
229 fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0)
231 for(typename GR::UndirEdgeIt e(g);e!=INVALID;++e)
232 push_back(value_type(g.direct(e, true), m[e]));
236 typename disable_if<typename _GR::UndirTag,void>::type
237 fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1)
239 for(typename GR::EdgeIt e(g);e!=INVALID;++e)
240 push_back(value_type(e, m[e]));
247 std::sort(this->begin(), this->end(), comparePair());
250 KruskalMapInput(GR const& g, Map const& m) {
256 /// Creates a KruskalMapInput object for \ref kruskal()
258 /// It makes easier to use
259 /// \ref KruskalMapInput by making it unnecessary
260 /// to explicitly give the type of the parameters.
262 /// In most cases you possibly
263 /// want to use \ref kruskal() instead.
265 ///\param g The type of the graph the algorithm runs on.
266 ///\param m An edge map containing the cost of the edges.
268 ///The cost type can be any type satisfying the
269 ///STL 'LessThan Comparable'
270 ///concept if it also has an operator+() implemented. (It is necessary for
271 ///computing the total cost of the tree).
273 ///\return An appropriate input source for \ref kruskal().
275 template<class GR, class Map>
277 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &g,const Map &m)
279 return KruskalMapInput<GR,Map>(g,m);
284 /* ** ** Output-objects: simple writable bool maps ** ** */
288 /// A writable bool-map that makes a sequence of "true" keys
290 /// A writable bool-map that creates a sequence out of keys that receives
291 /// the value "true".
293 /// \sa makeKruskalSequenceOutput()
295 /// Very often, when looking for a min cost spanning tree, we want as
296 /// output a container containing the edges of the found tree. For this
297 /// purpose exist this class that wraps around an STL iterator with a
298 /// writable bool map interface. When a key gets value "true" this key
299 /// is added to sequence pointed by the iterator.
303 /// std::vector<Graph::Edge> v;
304 /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
307 /// For the most common case, when the input is given by a simple edge
308 /// map and the output is a sequence of the tree edges, a special
309 /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
311 /// \warning Not a regular property map, as it doesn't know its Key
313 template<class Iterator>
314 class KruskalSequenceOutput {
318 typedef typename Iterator::value_type Key;
321 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
323 template<typename Key>
324 void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
327 template<class Iterator>
329 KruskalSequenceOutput<Iterator>
330 makeKruskalSequenceOutput(Iterator it) {
331 return KruskalSequenceOutput<Iterator>(it);
336 /* ** ** Wrapper funtions ** ** */
338 // \brief Wrapper function to kruskal().
339 // Input is from an edge map, output is a plain bool map.
341 // Wrapper function to kruskal().
342 // Input is from an edge map, output is a plain bool map.
344 // \param g The type of the graph the algorithm runs on.
345 // \param in An edge map containing the cost of the edges.
347 // The cost type can be any type satisfying the
348 // STL 'LessThan Comparable'
349 // concept if it also has an operator+() implemented. (It is necessary for
350 // computing the total cost of the tree).
352 // \retval out This must be a writable \c bool edge map.
353 // After running the algorithm
354 // this will contain the found minimum cost spanning tree: the value of an
355 // edge will be set to \c true if it belongs to the tree, otherwise it will
356 // be set to \c false. The value of each edge will be set exactly once.
358 // \return The cost of the found tree.
360 template <class GR, class IN, class RET>
366 // typename IN::Key = typename GR::Edge(),
367 //typename IN::Key = typename IN::Key (),
368 // typename RET::Key = typename GR::Edge()
369 const typename IN::Key * = (const typename IN::Key *)(0),
370 const typename RET::Key * = (const typename RET::Key *)(0)
374 KruskalMapInput<GR,IN>(g,in),
378 // \brief Wrapper function to kruskal().
379 // Input is from an edge map, output is an STL Sequence.
381 // Wrapper function to kruskal().
382 // Input is from an edge map, output is an STL Sequence.
384 // \param g The type of the graph the algorithm runs on.
385 // \param in An edge map containing the cost of the edges.
387 // The cost type can be any type satisfying the
388 // STL 'LessThan Comparable'
389 // concept if it also has an operator+() implemented. (It is necessary for
390 // computing the total cost of the tree).
392 // \retval out This must be an iteraror of an STL Container with
393 // <tt>GR::Edge</tt> as its <tt>value_type</tt>.
394 // The algorithm copies the elements of the found tree into this sequence.
395 // For example, if we know that the spanning tree of the graph \c g has
396 // say 53 edges, then
397 // we can put its edges into a STL vector \c tree with a code like this.
399 // std::vector<Edge> tree(53);
400 // kruskal(g,cost,tree.begin());
402 // Or if we don't know in advance the size of the tree, we can write this.
404 // std::vector<Edge> tree;
405 // kruskal(g,cost,std::back_inserter(tree));
408 // \return The cost of the found tree.
410 // \bug its name does not follow the coding style.
412 template <class GR, class IN, class RET>
418 //,typename RET::value_type = typename GR::Edge()
419 //,typename RET::value_type = typename RET::value_type()
420 const typename RET::value_type * =
421 (const typename RET::value_type *)(0)
424 KruskalSequenceOutput<RET> _out(out);
425 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
432 #endif //LEMON_KRUSKAL_H