Changeset 1557:3e8d928e283d in lemon0.x
 Timestamp:
 07/14/05 14:23:15 (16 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2053
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/kruskal.h
r1555 r1557 37 37 /// 38 38 ///Kruskal's algorithm to compute a minimum cost tree. 39 /// 40 ///\todo The file still needs some cleanup. 39 41 40 42 namespace lemon { … … 46 48 47 49 /// This function runs Kruskal's algorithm to find a minimum cost tree. 50 /// Due to hard C++ hacking, it accepts various input and output types. 51 /// 48 52 /// \param g The graph the algorithm runs on. 49 53 /// It can be either \ref concept::StaticGraph "directed" or … … 52 56 /// undirected by disregarding the direction of the edges. 53 57 /// 54 /// \param in This object is used to describe the edge costs. It must 55 /// be an STL compatible 'Forward Container' 58 /// \param in This object is used to describe the edge costs. It can be one 59 /// of the following choices. 60 ///  An STL compatible 'Forward Container' 56 61 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, 57 /// where X is the type of the costs. It must contain every edge in 58 /// costascending order. 59 ///\par 60 /// For the sake of simplicity, there is a helper class KruskalMapInput, 61 /// which converts a 62 /// simple edge map to an input of this form. Alternatively, you can use 63 /// the function \ref kruskalEdgeMap to compute the minimum cost tree if 64 /// the edge costs are given by an edge map. 65 /// 66 /// \retval out This must be a writable \c bool edge map. 62 /// where \c X is the type of the costs. The pairs indicates the edges along 63 /// with the assigned cost. <em>They must be in a 64 /// costascending order.</em> 65 ///  Any readable Edge map. The values of the map indicate the edge costs. 66 /// 67 /// \retval out Here we also have a choise. 68 ///  Is can be a writable \c bool edge map. 67 69 /// After running the algorithm 68 70 /// this will contain the found minimum cost spanning tree: the value of an 69 71 /// edge will be set to \c true if it belongs to the tree, otherwise it will 70 72 /// be set to \c false. The value of each edge will be set exactly once. 73 ///  It can also be an iteraror of an STL Container with 74 /// <tt>GR::Edge</tt> as its <tt>value_type</tt>. 75 /// The algorithm copies the elements of the found tree into this sequence. 76 /// For example, if we know that the spanning tree of the graph \c g has 77 /// say 53 edges then 78 /// we can put its edges into a STL vector \c tree with a code like this. 79 /// \code 80 /// std::vector<Edge> tree(53); 81 /// kruskal(g,cost,tree.begin()); 82 /// \endcode 83 /// Or if we don't know in advance the size of the tree, we can write this. 84 /// \code 85 /// std::vector<Edge> tree; 86 /// kruskal(g,cost,std::back_inserter(tree)); 87 /// \endcode 71 88 /// 72 89 /// \return The cost of the found tree. … … 78 95 /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.) 79 96 97 #ifdef DOXYGEN 80 98 template <class GR, class IN, class OUT> 81 99 typename IN::value_type::second_type 82 100 kruskal(GR const& g, IN const& in, 83 OUT& out) 101 OUT& out) 102 #else 103 template <class GR, class IN, class OUT> 104 typename IN::value_type::second_type 105 kruskal(GR const& g, IN const& in, 106 OUT& out, 107 // typename IN::value_type::first_type = typename GR::Edge() 108 // ,typename OUT::Key = OUT::Key() 109 // //,typename OUT::Key = typename GR::Edge() 110 const typename IN::value_type::first_type * = 111 (const typename IN::value_type::first_type *)(0), 112 const typename OUT::Key * = (const typename OUT::Key *)(0) 113 ) 114 #endif 84 115 { 85 116 typedef typename IN::value_type::second_type EdgeCost; … … 105 136 } 106 137 138 139 /// @} 140 141 107 142 /* A workaround for running Kruskal with constreference bool maps... */ 108 143 … … 123 158 const Map &m; 124 159 public: 160 typedef typename Map::Key Key; 125 161 typedef typename Map::Value Value; 126 162 … … 134 170 inline 135 171 typename IN::value_type::second_type 136 kruskal(GR const& g, IN const& edges, OUT const& out_map) 172 kruskal(GR const& g, IN const& edges, OUT const& out_map, 173 // typename IN::value_type::first_type = typename GR::Edge(), 174 // typename OUT::Key = GR::Edge() 175 const typename IN::value_type::first_type * = 176 (const typename IN::value_type::first_type *)(0), 177 const typename OUT::Key * = (const typename OUT::Key *)(0) 178 ) 137 179 { 138 180 NonConstMapWr<OUT> map_wr(out_map); … … 143 185 144 186 /// Kruskal's input source. 145 187 146 188 /// Kruskal's input source. 147 189 /// … … 268 310 269 311 public: 312 typedef typename Iterator::value_type Key; 270 313 typedef bool Value; 271 314 … … 287 330 /* ** ** Wrapper funtions ** ** */ 288 331 289 290 291 /// \brief Wrapper function to kruskal(). 292 /// Input is from an edge map, output is a plain bool map. 293 /// 294 /// Wrapper function to kruskal(). 295 /// Input is from an edge map, output is a plain bool map. 296 /// 297 ///\param g The type of the graph the algorithm runs on. 298 ///\param in An edge map containing the cost of the edges. 299 ///\par 300 ///The cost type can be any type satisfying the 301 ///STL 'LessThan Comparable' 302 ///concept if it also has an operator+() implemented. (It is necessary for 303 ///computing the total cost of the tree). 304 /// 305 /// \retval out This must be a writable \c bool edge map. 306 /// After running the algorithm 307 /// this will contain the found minimum cost spanning tree: the value of an 308 /// edge will be set to \c true if it belongs to the tree, otherwise it will 309 /// be set to \c false. The value of each edge will be set exactly once. 310 /// 311 /// \return The cost of the found tree. 332 // \brief Wrapper function to kruskal(). 333 // Input is from an edge map, output is a plain bool map. 334 // 335 // Wrapper function to kruskal(). 336 // Input is from an edge map, output is a plain bool map. 337 // 338 // \param g The type of the graph the algorithm runs on. 339 // \param in An edge map containing the cost of the edges. 340 // \par 341 // The cost type can be any type satisfying the 342 // STL 'LessThan Comparable' 343 // concept if it also has an operator+() implemented. (It is necessary for 344 // computing the total cost of the tree). 345 // 346 // \retval out This must be a writable \c bool edge map. 347 // After running the algorithm 348 // this will contain the found minimum cost spanning tree: the value of an 349 // edge will be set to \c true if it belongs to the tree, otherwise it will 350 // be set to \c false. The value of each edge will be set exactly once. 351 // 352 // \return The cost of the found tree. 312 353 313 354 template <class GR, class IN, class RET> 314 355 inline 315 356 typename IN::Value 316 kruskalEdgeMap(GR const& g, 317 IN const& in, 318 RET &out) { 357 kruskal(GR const& g, 358 IN const& in, 359 RET &out, 360 // typename IN::Key = typename GR::Edge(), 361 //typename IN::Key = typename IN::Key (), 362 // typename RET::Key = typename GR::Edge() 363 const typename IN::Key * = (const typename IN::Key *)(0), 364 const typename RET::Key * = (const typename RET::Key *)(0) 365 ) 366 { 319 367 return kruskal(g, 320 368 KruskalMapInput<GR,IN>(g,in), … … 322 370 } 323 371 324 ///\brief Wrapper function to kruskal().325 ///Input is from an edge map, output is an STL Sequence.326 /// 327 ///Wrapper function to kruskal().328 ///Input is from an edge map, output is an STL Sequence.329 /// 330 ///\param g The type of the graph the algorithm runs on.331 ///\param in An edge map containing the cost of the edges.332 ///\par333 ///The cost type can be any type satisfying the334 ///STL 'LessThan Comparable'335 ///concept if it also has an operator+() implemented. (It is necessary for336 ///computing the total cost of the tree).337 /// 338 ///\retval out This must be an iteraror of an STL Container with339 ///<tt>GR::Edge</tt> as its <tt>value_type</tt>.340 ///The algorithm copies the elements of the found tree into this sequence.341 ///For example, if we know that the spanning tree of the graph \c g has342 ///say 53 edges then343 ///we can put its edges into a STL vector \c tree with a code like this.344 ///\code345 ///std::vector<Edge> tree(53);346 ///kruskalEdgeMap_IteratorOut(g,cost,tree.begin());347 ///\endcode348 ///Or if we don't know in advance the size of the tree, we can write this.349 ///\code350 ///std::vector<Edge> tree;351 ///kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));352 ///\endcode353 /// 354 ///\return The cost of the found tree.355 /// 356 ///\bug its name does not follow the coding style.372 // \brief Wrapper function to kruskal(). 373 // Input is from an edge map, output is an STL Sequence. 374 // 375 // Wrapper function to kruskal(). 376 // Input is from an edge map, output is an STL Sequence. 377 // 378 // \param g The type of the graph the algorithm runs on. 379 // \param in An edge map containing the cost of the edges. 380 // \par 381 // The cost type can be any type satisfying the 382 // STL 'LessThan Comparable' 383 // concept if it also has an operator+() implemented. (It is necessary for 384 // computing the total cost of the tree). 385 // 386 // \retval out This must be an iteraror of an STL Container with 387 // <tt>GR::Edge</tt> as its <tt>value_type</tt>. 388 // The algorithm copies the elements of the found tree into this sequence. 389 // For example, if we know that the spanning tree of the graph \c g has 390 // say 53 edges then 391 // we can put its edges into a STL vector \c tree with a code like this. 392 // \code 393 // std::vector<Edge> tree(53); 394 // kruskalEdgeMap_IteratorOut(g,cost,tree.begin()); 395 // \endcode 396 // Or if we don't know in advance the size of the tree, we can write this. 397 // \code 398 // std::vector<Edge> tree; 399 // kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree)); 400 // \endcode 401 // 402 // \return The cost of the found tree. 403 // 404 // \bug its name does not follow the coding style. 357 405 358 406 template <class GR, class IN, class RET> 359 407 inline 360 408 typename IN::Value 361 kruskalEdgeMap_IteratorOut(const GR& g, 362 const IN& in, 363 RET out) 409 kruskal(const GR& g, 410 const IN& in, 411 RET out, 412 //,typename RET::value_type = typename GR::Edge() 413 //,typename RET::value_type = typename RET::value_type() 414 const typename RET::value_type * = 415 (const typename RET::value_type *)(0) 416 ) 364 417 { 365 418 KruskalSequenceOutput<RET> _out(out); 366 419 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out); 367 420 } 368 421 369 422 /// @} 370 423 
test/kruskal_test.cc
r1435 r1557 33 33 concept::WriteMap<concept::StaticGraph::Edge,bool> w; 34 34 35 kruskal EdgeMap(concept::StaticGraph(),36 37 35 kruskal(concept::StaticGraph(), 36 concept::ReadMap<concept::StaticGraph::Edge,int>(), 37 w); 38 38 } 39 39 … … 73 73 74 74 //Test with const map. 75 check(kruskal EdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,75 check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10, 76 76 "Total cost should be 10"); 77 77 //Test with a edge map (filled with uniform costs). 78 check(kruskal EdgeMap(G, edge_cost_map, tree_map)==10,78 check(kruskal(G, edge_cost_map, tree_map)==10, 79 79 "Total cost should be 10"); 80 80 … … 90 90 edge_cost_map.set(e10, 1); 91 91 92 vector<Edge> tree_edge_vec ;92 vector<Edge> tree_edge_vec(5); 93 93 94 94 //Test with a edge map and inserter. 95 check(kruskal EdgeMap_IteratorOut(G, edge_cost_map,96 back_inserter(tree_edge_vec))95 check(kruskal(G, edge_cost_map, 96 tree_edge_vec.begin()) 97 97 ==31, 98 98 "Total cost should be 31."); 99 99 100 100 tree_edge_vec.clear(); 101 101 102 check(kruskal(G, edge_cost_map, 103 back_inserter(tree_edge_vec)) 104 ==31, 105 "Total cost should be 31."); 106 107 tree_edge_vec.clear(); 108 102 109 //The above test could also be coded like this: 103 110 check(kruskal(G,
Note: See TracChangeset
for help on using the changeset viewer.