- '.lgf' could be the standard 'lemon graph format' extension.
- heap_test is fixed in order that 'make discheck' work.
- heap_test now checks whether the input file exists.
2 * src/lemon/kruskal.h - Part of LEMON, a generic C++ optimization library
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
5 * (Egervary Combinatorial Optimization Research Group, 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>
24 @defgroup spantree Minimum Cost Spanning Tree Algorithms
26 \brief This group containes the algorithms for finding a minimum cost spanning
29 This group containes the algorithms for finding a minimum cost spanning
35 ///\brief Kruskal's algorithm to compute a minimum cost tree
37 ///Kruskal's algorithm to compute a minimum cost tree.
41 /// \addtogroup spantree
44 /// Kruskal's algorithm to find a minimum cost tree of a graph.
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.
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.
56 /// For the sake of simplicity, there is a helper class KruskalMapInput,
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.
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.
68 /// \return The cost of the found tree.
70 template <class GR, class IN, class OUT>
71 typename IN::value_type::second_type
72 kruskal(GR const& G, IN const& in,
75 typedef typename IN::value_type::second_type EdgeCost;
76 typedef typename GR::template NodeMap<int> NodeIntMap;
77 typedef typename GR::Node Node;
79 NodeIntMap comp(G, -1);
80 UnionFind<Node,NodeIntMap> uf(comp);
82 EdgeCost tot_cost = 0;
83 for (typename IN::const_iterator p = in.begin();
85 if ( uf.join(G.target((*p).first),
86 G.source((*p).first)) ) {
87 out.set((*p).first, true);
88 tot_cost += (*p).second;
91 out.set((*p).first, false);
97 /* A work-around for running Kruskal with const-reference bool maps... */
99 /// Helper class for calling kruskal with "constant" output map.
101 /// Helper class for calling kruskal with output maps constructed
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>
112 class NonConstMapWr {
115 typedef typename Map::Value Value;
117 NonConstMapWr(const Map &_m) : m(_m) {}
120 void set(Key const& k, Value const &v) const { m.set(k,v); }
123 template <class GR, class IN, class OUT>
125 typename IN::value_type::second_type
126 kruskal(GR const& G, IN const& edges, OUT const& out_map)
128 NonConstMapWr<OUT> map_wr(out_map);
129 return kruskal(G, edges, map_wr);
132 /* ** ** Input-objects ** ** */
134 /// Kruskal input source.
136 /// Kruskal input source.
138 /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
140 /// \sa makeKruskalMapInput()
142 ///\param GR The type of the graph the algorithm runs on.
143 ///\param Map An edge map containing the cost of the edges.
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).
150 template<class GR, class Map>
151 class KruskalMapInput
152 : public std::vector< std::pair<typename GR::Edge,
153 typename Map::Value> > {
156 typedef std::vector< std::pair<typename GR::Edge,
157 typename Map::Value> > Parent;
158 typedef typename Parent::value_type value_type;
163 bool operator()(const value_type& a,
164 const value_type& b) {
165 return a.second < b.second;
172 std::sort(this->begin(), this->end(), comparePair());
175 KruskalMapInput(GR const& G, Map const& m) {
176 typedef typename GR::EdgeIt EdgeIt;
178 for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
183 /// Creates a KruskalMapInput object for \ref kruskal()
185 /// It makes is easier to use
186 /// \ref KruskalMapInput by making it unnecessary
187 /// to explicitly give the type of the parameters.
189 /// In most cases you possibly
190 /// want to use the function kruskalEdgeMap() instead.
192 ///\param G The type of the graph the algorithm runs on.
193 ///\param m An edge map containing the cost of the edges.
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).
200 ///\return An appropriate input source for \ref kruskal().
202 template<class GR, class Map>
204 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
206 return KruskalMapInput<GR,Map>(G,m);
211 /* ** ** Output-objects: simple writable bool maps ** ** */
215 /// A writable bool-map that makes a sequence of "true" keys
217 /// A writable bool-map that creates a sequence out of keys that receives
218 /// the value "true".
220 /// \sa makeKruskalSequenceOutput()
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.
230 /// std::vector<Graph::Edge> v;
231 /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
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().
238 /// \warning Not a regular property map, as it doesn't know its Key
240 template<class Iterator>
241 class KruskalSequenceOutput {
247 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
249 template<typename Key>
250 void set(Key const& k, bool v) const { if(v) {*it=k; ++it;} }
253 template<class Iterator>
255 KruskalSequenceOutput<Iterator>
256 makeKruskalSequenceOutput(Iterator it) {
257 return KruskalSequenceOutput<Iterator>(it);
262 /* ** ** Wrapper funtions ** ** */
266 /// \brief Wrapper function to kruskal().
267 /// Input is from an edge map, output is a plain bool map.
269 /// Wrapper function to kruskal().
270 /// Input is from an edge map, output is a plain bool map.
272 ///\param G The type of the graph the algorithm runs on.
273 ///\param in An edge map containing the cost of the edges.
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).
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.
286 /// \return The cost of the found tree.
288 template <class GR, class IN, class RET>
291 kruskalEdgeMap(GR const& G,
295 KruskalMapInput<GR,IN>(G,in),
299 /// \brief Wrapper function to kruskal().
300 /// Input is from an edge map, output is an STL Sequence.
302 /// Wrapper function to kruskal().
303 /// Input is from an edge map, output is an STL Sequence.
305 ///\param G The type of the graph the algorithm runs on.
306 ///\param in An edge map containing the cost of the edges.
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).
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.
320 /// std::vector<Edge> tree(53);
321 /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
323 /// Or if we don't know in advance the size of the tree, we can write this.
325 /// std::vector<Edge> tree;
326 /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
329 /// \return The cost of the found tree.
331 /// \bug its name does not follow the coding style.
333 template <class GR, class IN, class RET>
336 kruskalEdgeMap_IteratorOut(const GR& G,
340 KruskalSequenceOutput<RET> _out(out);
341 return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
348 #endif //LEMON_KRUSKAL_H