The default constructors are removed from the maps.
The ArrayMap is the map structure of the graphs.
6 #include <hugo/unionfind.h>
9 @defgroup spantree Minimum Cost Spanning Tree Algorithms
11 \brief This group containes the algorithms for finding a minimum cost spanning
14 This group containes the algorithms for finding a minimum cost spanning
20 ///\brief Kruskal's algorithm to compute a minimum cost tree
22 ///Kruskal's algorithm to compute a minimum cost tree.
26 /// \addtogroup spantree
29 /// Kruskal's algorithm to find a minimum cost tree of a graph.
31 /// This function runs Kruskal's algorithm to find a minimum cost tree.
32 /// \param G The graph the algorithm runs on. The algorithm considers the
33 /// graph to be undirected, the direction of the edges are not used.
35 /// \param in This object is used to describe the edge costs. It must
36 /// be an STL compatible 'Forward Container'
37 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
38 /// where X is the type of the costs. It must contain every edge in
39 /// cost-ascending order.
41 /// For the sake of simplicity, there is a helper class KruskalMapInput,
43 /// simple edge map to an input of this form. Alternatively, you can use
44 /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
45 /// the edge costs are given by an edge map.
47 /// \retval out This must be a writable \c bool edge map.
48 /// After running the algorithm
49 /// this will contain the found minimum cost spanning tree: the value of an
50 /// edge will be set to \c true if it belongs to the tree, otherwise it will
51 /// be set to \c false. The value of each edge will be set exactly once.
53 /// \return The cost of the found tree.
55 template <class GR, class IN, class OUT>
56 typename IN::value_type::second_type
57 kruskal(GR const& G, IN const& in,
60 typedef typename IN::value_type::second_type EdgeCost;
61 typedef typename GR::template NodeMap<int> NodeIntMap;
62 typedef typename GR::Node Node;
64 NodeIntMap comp(G, -1);
65 UnionFind<Node,NodeIntMap> uf(comp);
67 EdgeCost tot_cost = 0;
68 for (typename IN::const_iterator p = in.begin();
70 if ( uf.join(G.head((*p).first),
71 G.tail((*p).first)) ) {
72 out.set((*p).first, true);
73 tot_cost += (*p).second;
76 out.set((*p).first, false);
82 /* A work-around for running Kruskal with const-reference bool maps... */
84 /// Helper class for calling kruskal with "constant" output map.
86 /// Helper class for calling kruskal with output maps constructed
89 /// A typical examle is the following call:
90 /// <tt>kruskal(G, some_input, makeSequenceOutput(iterator))</tt>.
91 /// Here, the third argument is a temporary object (which wraps around an
92 /// iterator with a writable bool map interface), and thus by rules of C++
93 /// is a \c const object. To enable call like this exist this class and
94 /// the prototype of the \ref kruskal() function with <tt>const& OUT</tt>
100 typedef typename Map::ValueType ValueType;
102 NonConstMapWr(const Map &_m) : m(_m) {}
104 template<class KeyType>
105 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
108 template <class GR, class IN, class OUT>
110 typename IN::value_type::second_type
111 kruskal(GR const& G, IN const& edges, OUT const& out_map)
113 NonConstMapWr<OUT> map_wr(out_map);
114 return kruskal(G, edges, map_wr);
117 /* ** ** Input-objects ** ** */
119 /// Kruskal input source.
121 /// Kruskal input source.
123 /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
125 /// \sa makeKruskalMapInput()
127 ///\param GR The type of the graph the algorithm runs on.
128 ///\param Map An edge map containing the cost of the edges.
130 ///The cost type can be any type satisfying
131 ///the STL 'LessThan comparable'
132 ///concept if it also has an operator+() implemented. (It is necessary for
133 ///computing the total cost of the tree).
135 template<class GR, class Map>
136 class KruskalMapInput
137 : public std::vector< std::pair<typename GR::Edge,
138 typename Map::ValueType> > {
141 typedef std::vector< std::pair<typename GR::Edge,
142 typename Map::ValueType> > Parent;
143 typedef typename Parent::value_type value_type;
148 bool operator()(const value_type& a,
149 const value_type& b) {
150 return a.second < b.second;
157 std::sort(this->begin(), this->end(), comparePair());
160 KruskalMapInput(GR const& G, Map const& m) {
161 typedef typename GR::EdgeIt EdgeIt;
163 for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
168 /// Creates a KruskalMapInput object for \ref kruskal()
170 /// It makes is easier to use
171 /// \ref KruskalMapInput by making it unnecessary
172 /// to explicitly give the type of the parameters.
174 /// In most cases you possibly
175 /// want to use the function kruskalEdgeMap() instead.
177 ///\param G The type of the graph the algorithm runs on.
178 ///\param m An edge map containing the cost of the edges.
180 ///The cost type can be any type satisfying the
181 ///STL 'LessThan Comparable'
182 ///concept if it also has an operator+() implemented. (It is necessary for
183 ///computing the total cost of the tree).
185 ///\return An appropriate input source for \ref kruskal().
187 template<class GR, class Map>
189 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
191 return KruskalMapInput<GR,Map>(G,m);
196 /* ** ** Output-objects: simple writable bool maps ** ** */
200 /// A writable bool-map that makes a sequence of "true" keys
202 /// A writable bool-map that creates a sequence out of keys that receives
203 /// the value "true".
205 /// \sa makeKruskalSequenceOutput()
207 /// Very often, when looking for a min cost spanning tree, we want as
208 /// output a container containing the edges of the found tree. For this
209 /// purpose exist this class that wraps around an STL iterator with a
210 /// writable bool map interface. When a key gets value "true" this key
211 /// is added to sequence pointed by the iterator.
215 /// std::vector<Graph::Edge> v;
216 /// kruskal(g, input, makeKruskalSequenceOutput(back_inserter(v)));
219 /// For the most common case, when the input is given by a simple edge
220 /// map and the output is a sequence of the tree edges, a special
221 /// wrapper function exists: \ref kruskalEdgeMap_IteratorOut().
223 /// \warning Not a regular property map, as it doesn't know its KeyType
225 template<class Iterator>
226 class KruskalSequenceOutput {
230 typedef bool ValueType;
232 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
234 template<typename KeyType>
235 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
238 template<class Iterator>
240 KruskalSequenceOutput<Iterator>
241 makeKruskalSequenceOutput(Iterator it) {
242 return KruskalSequenceOutput<Iterator>(it);
247 /* ** ** Wrapper funtions ** ** */
251 /// \brief Wrapper function to kruskal().
252 /// Input is from an edge map, output is a plain bool map.
254 /// Wrapper function to kruskal().
255 /// Input is from an edge map, output is a plain bool map.
257 ///\param G The type of the graph the algorithm runs on.
258 ///\param in An edge map containing the cost of the edges.
260 ///The cost type can be any type satisfying the
261 ///STL 'LessThan Comparable'
262 ///concept if it also has an operator+() implemented. (It is necessary for
263 ///computing the total cost of the tree).
265 /// \retval out This must be a writable \c bool edge map.
266 /// After running the algorithm
267 /// this will contain the found minimum cost spanning tree: the value of an
268 /// edge will be set to \c true if it belongs to the tree, otherwise it will
269 /// be set to \c false. The value of each edge will be set exactly once.
271 /// \return The cost of the found tree.
273 template <class GR, class IN, class RET>
275 typename IN::ValueType
276 kruskalEdgeMap(GR const& G,
280 KruskalMapInput<GR,IN>(G,in),
284 /// \brief Wrapper function to kruskal().
285 /// Input is from an edge map, output is an STL Sequence.
287 /// Wrapper function to kruskal().
288 /// Input is from an edge map, output is an STL Sequence.
290 ///\param G The type of the graph the algorithm runs on.
291 ///\param in An edge map containing the cost of the edges.
293 ///The cost type can be any type satisfying the
294 ///STL 'LessThan Comparable'
295 ///concept if it also has an operator+() implemented. (It is necessary for
296 ///computing the total cost of the tree).
298 /// \retval out This must be an iteraror of an STL Container with
299 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
300 /// The algorithm copies the elements of the found tree into this sequence.
301 /// For example, if we know that the spanning tree of the graph \c G has
302 /// say 53 edges then
303 /// we can put its edges into a STL vector \c tree with a code like this.
305 /// std::vector<Edge> tree(53);
306 /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
308 /// Or if we don't know in advance the size of the tree, we can write this.
310 /// std::vector<Edge> tree;
311 /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
314 /// \return The cost of the found tree.
316 /// \bug its name does not follow the coding style.
318 template <class GR, class IN, class RET>
320 typename IN::ValueType
321 kruskalEdgeMap_IteratorOut(const GR& G,
325 KruskalSequenceOutput<RET> _out(out);
326 return kruskal(G, KruskalMapInput<GR,IN>(G, in), _out);
333 #endif //HUGO_KRUSKAL_H