Changeset 194:74cd0c58b348 in lemon-1.2
- Timestamp:
- 07/08/08 22:56:02 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/kruskal.h
r167 r194 33 33 ///\ingroup spantree 34 34 ///\file 35 ///\brief Kruskal's algorithm to compute a minimum cost tree35 ///\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 … … 252 252 /// \ingroup spantree 253 253 /// 254 /// \brief Kruskal's algorithm to find a minimum cost tree of a graph. 255 /// 256 /// This function runs Kruskal's algorithm to find a minimum cost tree. 254 /// \brief Kruskal algorithm to find a minimum cost spanning tree of 255 /// a graph. 256 /// 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 /// … … 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 one266 /// 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> or269 /// <tt>std::pair<GR:: Arc,X></tt> as its <tt>value_type</tt>, where270 /// \c X is the type of the costs. The pairs indicates the arcs 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 Arc map. The values of the map indicate the arc costs. 274 /// 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 275 /// - Any readable arc/edge map. The values of the map indicate the 276 /// arc/edge costs. 277 /// 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:: Edge</tt> or <tt>GR::Arc</tt> as its285 /// <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 … … 291 294 /// Or if we don't know in advance the size of the tree, we can 292 295 /// write this. 293 ///\code std::vector<Arc> tree; 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.298 /// 299 /// \warning If kruskal runs on an be consistent of using the same301 /// \return The total cost of the found spanning tree. 302 /// 303 /// \warning If Kruskal runs on an be consistent of using the same 300 304 /// Arc type for input and output. 301 305 ///
Note: See TracChangeset
for help on using the changeset viewer.