r194:74cd0c58b348
Tue, 08 Jul 2008 22:56:02
[Not Reviewed]
0 comments (0 inline)
0
1
0
23
19
| ... | ... |
@@ -23,27 +23,27 @@ |
| 23 | 23 |
#include <vector> |
| 24 | 24 |
#include <lemon/unionfind.h> |
| 25 | 25 |
// #include <lemon/graph_utils.h> |
| 26 | 26 |
#include <lemon/maps.h> |
| 27 | 27 |
|
| 28 | 28 |
// #include <lemon/radix_sort.h> |
| 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 |
|
| 44 | 44 |
// Kruskal for directed graphs. |
| 45 | 45 |
|
| 46 | 46 |
template <typename Digraph, typename In, typename Out> |
| 47 | 47 |
typename disable_if<lemon::UndirectedTagIndicator<Digraph>, |
| 48 | 48 |
typename In::value_type::second_type >::type |
| 49 | 49 |
kruskal(const Digraph& digraph, const In& in, Out& out,dummy<0> = 0) {
|
| ... | ... |
@@ -242,70 +242,74 @@ |
| 242 | 242 |
{
|
| 243 | 243 |
typedef typename In::value_type::second_type Value; |
| 244 | 244 |
|
| 245 | 245 |
static Value kruskal(const Graph& graph, const In& in, Out& out) {
|
| 246 | 246 |
return _kruskal_bits::kruskal(graph, in, out); |
| 247 | 247 |
} |
| 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) |
| 306 | 310 |
#else |
| 307 | 311 |
template <class Graph, class In, class Out> |
| 308 | 312 |
inline typename _kruskal_bits::KruskalValueSelector<In>::Value |
| 309 | 313 |
kruskal(const Graph& graph, const In& in, Out& out) |
| 310 | 314 |
#endif |
| 311 | 315 |
{
|
0 comments (0 inline)