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