Document the file itself.
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.
24 ///\weakgroup spantree
27 /// \addtogroup spantree
30 /// Kruskal's algorithm to find a minimum cost tree of a graph.
32 /// This function runs Kruskal's algorithm to find a minimum cost tree.
33 /// \param G The graph the algorithm runs on. The algorithm considers the
34 /// graph to be undirected, the direction of the edges are not used.
36 /// \param in This object is used to describe the edge costs. It must
37 /// be an STL compatible 'Forward Container'
38 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
39 /// where X is the type of the costs. It must contain every edge in
40 /// cost-ascending order.
42 /// For the sake of simplicity, there is a helper class KruskalMapInput,
44 /// simple edge map to an input of this form. Alternatively, you can use
45 /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
46 /// the edge costs are given by an edge map.
48 /// \retval out This must be a writable \c bool edge map.
49 /// After running the algorithm
50 /// this will contain the found minimum cost spanning tree: the value of an
51 /// edge will be set to \c true if it belongs to the tree, otherwise it will
52 /// be set to \c false. The value of each edge will be set exactly once.
54 /// \return The cost of the found tree.
56 template <class GR, class IN, class OUT>
57 typename IN::value_type::second_type
58 kruskal(GR const& G, IN const& in,
61 typedef typename IN::value_type::second_type EdgeCost;
62 typedef typename GR::template NodeMap<int> NodeIntMap;
63 typedef typename GR::Node Node;
65 NodeIntMap comp(G, -1);
66 UnionFind<Node,NodeIntMap> uf(comp);
68 EdgeCost tot_cost = 0;
69 for (typename IN::const_iterator p = in.begin();
71 if ( uf.join(G.head((*p).first),
72 G.tail((*p).first)) ) {
73 out.set((*p).first, true);
74 tot_cost += (*p).second;
77 out.set((*p).first, false);
83 /* A work-around for running Kruskal with const-reference bool maps... */
85 ///\bug What is this? Or why doesn't it work?
91 typedef typename Map::ValueType ValueType;
93 NonConstMapWr(const Map &_m) : m(_m) {}
95 template<class KeyType>
96 void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
99 template <class GR, class IN, class OUT>
101 typename IN::ValueType
102 kruskal(GR const& G, IN const& edges,
105 NonConstMapWr<OUT> map_wr(out_map);
106 return kruskal(G, edges, map_wr);
109 /* ** ** Input-objects ** ** */
111 /// Kruskal input source.
113 /// Kruskal input source.
115 /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
117 /// \sa makeKruskalMapInput()
119 ///\param GR The type of the graph the algorithm runs on.
120 ///\param Map An edge map containing the cost of the edges.
122 ///The cost type can be any type satisfying
123 ///the STL 'LessThan comparable'
124 ///concept if it also has an operator+() implemented. (It is necessary for
125 ///computing the total cost of the tree).
127 template<class GR, class Map>
128 class KruskalMapInput
129 : public std::vector< std::pair<typename GR::Edge,
130 typename Map::ValueType> > {
133 typedef std::vector< std::pair<typename GR::Edge,
134 typename Map::ValueType> > Parent;
135 typedef typename Parent::value_type value_type;
140 bool operator()(const value_type& a,
141 const value_type& b) {
142 return a.second < b.second;
149 std::sort(this->begin(), this->end(), comparePair());
152 KruskalMapInput(GR const& G, Map const& m) {
153 typedef typename GR::EdgeIt EdgeIt;
156 for(EdgeIt e(G);e!=INVALID;++e) push_back(make_pair(e, m[e]));
161 /// Creates a KruskalMapInput object for \ref kruskal()
163 /// It makes is easier to use
164 /// \ref KruskalMapInput by making it unnecessary
165 /// to explicitly give the type of the parameters.
167 /// In most cases you possibly
168 /// want to use the function kruskalEdgeMap() instead.
170 ///\param G The type of the graph the algorithm runs on.
171 ///\param m An edge map containing the cost of the edges.
173 ///The cost type can be any type satisfying the
174 ///STL 'LessThan Comparable'
175 ///concept if it also has an operator+() implemented. (It is necessary for
176 ///computing the total cost of the tree).
178 ///\return An appropriate input source for \ref kruskal().
180 template<class GR, class Map>
182 KruskalMapInput<GR,Map> makeKruskalMapInput(const GR &G,const Map &m)
184 return KruskalMapInput<GR,Map>(G,m);
188 /* ** ** Output-objects: simple writable bool maps** ** */
190 /// A writable bool-map that makes a sequence of "true" keys
192 /// A writable bool-map that creates a sequence out of keys that receives
193 /// the value "true".
194 /// \warning Not a regular property map, as it doesn't know its KeyType
195 /// \bug Missing documentation.
196 /// \todo This class may be of wider usage, therefore it could move to
198 template<class Iterator>
199 class SequenceOutput {
203 typedef bool ValueType;
205 SequenceOutput(Iterator const &_it) : it(_it) {}
207 template<typename KeyType>
208 void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
211 template<class Iterator>
213 SequenceOutput<Iterator>
214 makeSequenceOutput(Iterator it) {
215 return SequenceOutput<Iterator>(it);
218 /* ** ** Wrapper funtions ** ** */
221 /// \brief Wrapper function to kruskal().
222 /// Input is from an edge map, output is a plain bool map.
224 /// Wrapper function to kruskal().
225 /// Input is from an edge map, output is a plain bool map.
227 ///\param G The type of the graph the algorithm runs on.
228 ///\param in An edge map containing the cost of the edges.
230 ///The cost type can be any type satisfying the
231 ///STL 'LessThan Comparable'
232 ///concept if it also has an operator+() implemented. (It is necessary for
233 ///computing the total cost of the tree).
235 /// \retval out This must be a writable \c bool edge map.
236 /// After running the algorithm
237 /// this will contain the found minimum cost spanning tree: the value of an
238 /// edge will be set to \c true if it belongs to the tree, otherwise it will
239 /// be set to \c false. The value of each edge will be set exactly once.
241 /// \return The cost of the found tree.
244 template <class GR, class IN, class RET>
246 typename IN::ValueType
247 kruskalEdgeMap(GR const& G,
251 KruskalMapInput<GR,IN>(G,in),
255 /// \brief Wrapper function to kruskal().
256 /// Input is from an edge map, output is an STL Sequence.
258 /// Wrapper function to kruskal().
259 /// Input is from an edge map, output is an STL Sequence.
261 ///\param G The type of the graph the algorithm runs on.
262 ///\param in An edge map containing the cost of the edges.
264 ///The cost type can be any type satisfying the
265 ///STL 'LessThan Comparable'
266 ///concept if it also has an operator+() implemented. (It is necessary for
267 ///computing the total cost of the tree).
269 /// \retval out This must be an iteraror of an STL Container with
270 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
271 /// The algorithm copies the elements of the found tree into this sequence.
272 /// For example, if we know that the spanning tree of the graph \c G has
273 /// say 53 edges then
274 /// we can put its edges into a STL vector \c tree with a code like this.
276 /// std::vector<Edge> tree(53);
277 /// kruskalEdgeMap_IteratorOut(G,cost,tree.begin());
279 /// Or if we don't know in advance the size of the tree, we can write this.
281 /// std::vector<Edge> tree;
282 /// kruskalEdgeMap_IteratorOut(G,cost,std::back_inserter(tree));
285 /// \return The cost of the found tree.
287 /// \bug its name does not follow the coding style.
288 template <class GR, class IN, class RET>
290 typename IN::ValueType
291 kruskalEdgeMap_IteratorOut(const GR& G,
295 SequenceOutput<RET> _out(out);
297 KruskalMapInput<GR,IN>(G, in),
305 #endif //HUGO_KRUSKAL_H