... | ... |
@@ -29,15 +29,15 @@ |
29 | 29 |
|
30 | 30 |
#include <lemon/bits/utility.h> |
31 | 31 |
#include <lemon/bits/traits.h> |
32 | 32 |
|
33 | 33 |
///\ingroup spantree |
34 | 34 |
///\file |
35 |
///\brief Kruskal's algorithm to compute a minimum cost tree |
|
35 |
///\brief Kruskal's algorithm to compute a minimum cost spanning tree |
|
36 | 36 |
/// |
37 |
///Kruskal's algorithm to compute a minimum cost tree. |
|
37 |
///Kruskal's algorithm to compute a minimum cost spanning tree. |
|
38 | 38 |
/// |
39 | 39 |
|
40 | 40 |
namespace lemon { |
41 | 41 |
|
42 | 42 |
namespace _kruskal_bits { |
43 | 43 |
|
... | ... |
@@ -248,58 +248,62 @@ |
248 | 248 |
}; |
249 | 249 |
|
250 | 250 |
} |
251 | 251 |
|
252 | 252 |
/// \ingroup spantree |
253 | 253 |
/// |
254 |
/// \brief Kruskal |
|
254 |
/// \brief Kruskal algorithm to find a minimum cost spanning tree of |
|
255 |
/// a graph. |
|
255 | 256 |
/// |
256 |
/// This function runs Kruskal's algorithm to find a minimum cost |
|
257 |
/// This function runs Kruskal's algorithm to find a minimum cost |
|
258 |
/// spanning tree. |
|
257 | 259 |
/// Due to some C++ hacking, it accepts various input and output types. |
258 | 260 |
/// |
259 | 261 |
/// \param g The graph the algorithm runs on. |
260 | 262 |
/// It can be either \ref concepts::Digraph "directed" or |
261 | 263 |
/// \ref concepts::Graph "undirected". |
262 | 264 |
/// If the graph is directed, the algorithm consider it to be |
263 | 265 |
/// undirected by disregarding the direction of the arcs. |
264 | 266 |
/// |
265 |
/// \param in This object is used to describe the arc costs. It can be one |
|
266 |
/// of the following choices. |
|
267 |
/// \param in This object is used to describe the arc/edge costs. |
|
268 |
/// It can be one of the following choices. |
|
267 | 269 |
/// - An STL compatible 'Forward Container' with |
268 |
/// <tt>std::pair<GR::Edge,X></tt> or |
|
269 |
/// <tt>std::pair<GR::Arc,X></tt> as its <tt>value_type</tt>, where |
|
270 |
/// |
|
270 |
/// <tt>std::pair<GR::Arc,X></tt> or |
|
271 |
/// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where |
|
272 |
/// \c X is the type of the costs. The pairs indicates the arcs/edges |
|
271 | 273 |
/// along with the assigned cost. <em>They must be in a |
272 | 274 |
/// cost-ascending order.</em> |
273 |
/// - Any readable |
|
275 |
/// - Any readable arc/edge map. The values of the map indicate the |
|
276 |
/// arc/edge costs. |
|
274 | 277 |
/// |
275 |
/// \retval out Here we also have a choise. |
|
276 |
/// - It can be a writable \c bool arc map. After running the |
|
277 |
/// algorithm this will contain the found minimum cost spanning |
|
278 |
/// tree: the value of an arc will be set to \c true if it belongs |
|
278 |
/// \retval out Here we also have a choice. |
|
279 |
/// - It can be a writable \c bool arc/edge map. After running the |
|
280 |
/// algorithm it will contain the found minimum cost spanning |
|
281 |
/// tree: the value of an arc/edge will be set to \c true if it belongs |
|
279 | 282 |
/// to the tree, otherwise it will be set to \c false. The value of |
280 |
/// each arc will be set exactly once. |
|
283 |
/// each arc/edge will be set exactly once. |
|
281 | 284 |
/// - It can also be an iteraror of an STL Container with |
282 |
/// <tt>GR:: |
|
285 |
/// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its |
|
283 | 286 |
/// <tt>value_type</tt>. The algorithm copies the elements of the |
284 | 287 |
/// found tree into this sequence. For example, if we know that the |
285 | 288 |
/// spanning tree of the graph \c g has say 53 arcs, then we can |
286 | 289 |
/// put its arcs into an STL vector \c tree with a code like this. |
287 | 290 |
///\code |
288 | 291 |
/// std::vector<Arc> tree(53); |
289 | 292 |
/// kruskal(g,cost,tree.begin()); |
290 | 293 |
///\endcode |
291 | 294 |
/// Or if we don't know in advance the size of the tree, we can |
292 | 295 |
/// write this. |
293 |
///\code |
|
296 |
///\code |
|
297 |
/// std::vector<Arc> tree; |
|
294 | 298 |
/// kruskal(g,cost,std::back_inserter(tree)); |
295 | 299 |
///\endcode |
296 | 300 |
/// |
297 |
/// \return The total cost of the found tree. |
|
301 |
/// \return The total cost of the found spanning tree. |
|
298 | 302 |
/// |
299 |
/// \warning If |
|
303 |
/// \warning If Kruskal runs on an be consistent of using the same |
|
300 | 304 |
/// Arc type for input and output. |
301 | 305 |
/// |
302 | 306 |
|
303 | 307 |
#ifdef DOXYGEN |
304 | 308 |
template <class Graph, class In, class Out> |
305 | 309 |
Value kruskal(GR const& g, const In& in, Out& out) |
0 comments (0 inline)