NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 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