Some modifications in this and that.
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.
42 /// \addtogroup spantree
45 /// Kruskal's algorithm to find a minimum cost tree of a graph.
47 /// This function runs Kruskal's algorithm to find a minimum cost tree.
48 /// \param G The graph the algorithm runs on. The algorithm considers the
49 /// graph to be undirected, the direction of the edges are not used.
51 /// \param in This object is used to describe the edge costs. It must
52 /// be an STL compatible 'Forward Container'
53 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
54 /// where X is the type of the costs. It must contain every edge in
55 /// cost-ascending order.
57 /// For the sake of simplicity, there is a helper class KruskalMapInput,
59 /// simple edge map to an input of this form. Alternatively, you can use
60 /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
61 /// the edge costs are given by an edge map.
63 /// \retval out This must be a writable \c bool edge map.
64 /// After running the algorithm
65 /// this will contain the found minimum cost spanning tree: the value of an
66 /// edge will be set to \c true if it belongs to the tree, otherwise it will
67 /// be set to \c false. The value of each edge will be set exactly once.
69 /// \return The cost of the found tree.
71 /// \todo Discuss the case of undirected graphs: In this case the algorithm
72 /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some
73 /// people would expect. So, one should be careful not to add both of the
74 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
75 /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
77 template <class GR, class IN, class OUT>
78 typename IN::value_type::second_type
79 kruskal(GR const& G, IN const& in,
82 typedef typename IN::value_type::second_type EdgeCost;
83 typedef typename GR::template NodeMap<int> NodeIntMap;
84 typedef typename GR::Node Node;
86 NodeIntMap comp(G, -1);
87 UnionFind<Node,NodeIntMap> uf(comp);
89 EdgeCost tot_cost = 0;
90 for (typename IN::const_iterator p = in.begin();
92 if ( uf.join(G.target((*p).first),
93 G.source((*p).first)) ) {
94 out.set((*p).first, true);
95 tot_cost += (*p).second;
98 out.set((*p).first, false);
104 /* A work-around for running Kruskal with const-reference bool maps... */
106 /// Helper class for calling kruskal with "constant" output map.
108 /// Helper class for calling kruskal with output maps constructed
111 /// A typical examle is the following call:
112 /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
113 /// Here, the third argument is a temporary object (which wraps around an
114 /// iterator with a writable bool map interface), and thus by rules of C++
115 /// is a \c const object. To enable call like this exist this class and
116 /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
119 class NonConstMapWr {
122 typedef typename Map::Value Value;
124 NonConstMapWr(const Map &_m) : m(_m) {}
127 void set(Key const& k, Value const &v) const { m.set(k,v); }
130 template <class GR, class IN, class OUT>
132 typename IN::value_type::second_type
133 kruskal(GR const& G, IN const& edges, OUT const& out_map)
135 NonConstMapWr<OUT> map_wr(out_map);
136 return kruskal(G, edges, map_wr);
139 /* ** ** Input-objects ** ** */
141 /// Kruskal's input source.
143 /// Kruskal's input source.
145 /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
147 /// \sa makeKruskalMapInput()
149 ///\param GR The type of the graph the algorithm runs on.
150 ///\param Map An edge map containing the cost of the edges.
152 ///The cost type can be any type satisfying
153 ///the STL 'LessThan comparable'
154 ///concept if it also has an operator+() implemented. (It is necessary for
155 ///computing the total cost of the tree).
157 template<class GR, class Map>
158 class KruskalMapInput
159 : public std::vector< std::pair<typename GR::Edge,
160 typename Map::Value> > {
163 typedef std::vector< std::pair<typename GR::Edge,
164 typename Map::Value> > Parent;
165 typedef typename Parent::value_type value_type;
170 bool operator()(const value_type& a,
171 const value_type& b) {
172 return a.second < b.second;
177 typename enable_if<typename _GR::UndirTag,void>::type
178 fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0)
180 for(typename GR::UndirEdgeIt e(G);e!=INVALID;++e)
181 push_back(value_type(typename GR::Edge(e,true), m[e]));
185 typename disable_if<typename _GR::UndirTag,void>::type
186 fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1)
188 for(typename GR::EdgeIt e(G);e!=INVALID;++e)
189 push_back(value_type(e, m[e]));
196 std::sort(this->begin(), this->end(), comparePair());
199 KruskalMapInput(GR const& G, Map const& m) {
205 /// Creates a KruskalMapInput object for \ref kruskal()
207 /// It makes easier to use
208 /// \ref KruskalMapInput by making it unnecessary
209 /// to explicitly give the type of the parameters.
211 /// In most cases you possibly
212 /// want to use the function kruskalEdgeMap() instead.
214 ///\param G The type of the graph the algorithm runs on.
215 ///\param m An edge map containing the cost of the edges.
217 ///The cost type can be any type satisfying the
218 ///STL 'LessThan Comparable'
219 ///concept if it also has an operator+() implemented. (It is necessary for
220 ///computing the total cost of the tree).
222 ///\return An appropriate input source for \ref kruskal().
224 template<class GR, class Map>
226 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
228 return KruskalMapInput<GR,Map>(G,m);
233 /* ** ** Output-objects: simple writable bool maps ** ** */
237 /// A writable bool-map that makes a sequence of "true" keys
239 /// A writable bool-map that creates a sequence out of keys that receives
240 /// the value "true".
242 /// \sa makeKruskalSequenceOutput()
244 /// Very often, when looking for a min cost spanning tree, we want as
245 /// output a container containing the edges of the found tree. For this
246 /// purpose exist this class that wraps around an STL iterator with a
247 /// writable bool map interface. When a key gets value "true" this key
248 /// is added to sequence pointed by the iterator.
252 /// std::vector<Graph::Edge> v;
253 /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
256 /// For the most common case, when the input is given by a simple edge
257 /// map and the output is a sequence of the tree edges, a special
258 /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
260 /// \warning Not a regular property map, as it doesn't know its Key
262 template<class Iterator>
263 class KruskalSequenceOutput {
269 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
271 template<typename Key>
272 void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
275 template<class Iterator>
277 KruskalSequenceOutput<Iterator>
278 makeKruskalSequenceOutput(Iterator it) {
279 return KruskalSequenceOutput<Iterator>(it);
284 /* ** ** Wrapper funtions ** ** */
288 /// \brief Wrapper function to kruskal().
289 /// Input is from an edge map, output is a plain bool map.
291 /// Wrapper function to kruskal().
292 /// Input is from an edge map, output is a plain bool map.
294 ///\param G The type of the graph the algorithm runs on.
295 ///\param in An edge map containing the cost of the edges.
297 ///The cost type can be any type satisfying the
298 ///STL 'LessThan Comparable'
299 ///concept if it also has an operator+() implemented. (It is necessary for
300 ///computing the total cost of the tree).
302 /// \retval out This must be a writable \c bool edge map.
303 /// After running the algorithm
304 /// this will contain the found minimum cost spanning tree: the value of an
305 /// edge will be set to \c true if it belongs to the tree, otherwise it will
306 /// be set to \c false. The value of each edge will be set exactly once.
308 /// \return The cost of the found tree.
310 template <class GR, class IN, class RET>
313 kruskalEdgeMap(GR const& G,
317 KruskalMapInput<GR,IN>(G,in),
321 /// \brief Wrapper function to kruskal().
322 /// Input is from an edge map, output is an STL Sequence.
324 /// Wrapper function to kruskal().
325 /// Input is from an edge map, output is an STL Sequence.
327 ///\param G The type of the graph the algorithm runs on.
328 ///\param in An edge map containing the cost of the edges.
330 ///The cost type can be any type satisfying the
331 ///STL 'LessThan Comparable'
332 ///concept if it also has an operator+() implemented. (It is necessary for
333 ///computing the total cost of the tree).
335 /// \retval out This must be an iteraror of an STL Container with
336 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
337 /// The algorithm copies the elements of the found tree into this sequence.
338 /// For example, if we know that the spanning tree of the graph \c G has
339 /// say 53 edges then
340 /// we can put its edges into a STL vector \c tree with a code like this.
342 /// std::vector<Edge> tree(53);
343 /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
345 /// Or if we don't know in advance the size of the tree, we can write this.
347 /// std::vector<Edge> tree;
348 /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
351 /// \return The cost of the found tree.
353 /// \bug its name does not follow the coding style.
355 template <class GR, class IN, class RET>
358 kruskalEdgeMap_IteratorOut(const GR& G,
362 KruskalSequenceOutput<RET> _out(out);
363 return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
370 #endif //LEMON_KRUSKAL_H