lemon/kruskal.h
changeset 196 420013ff029b
parent 167 d57ae6f0a335
child 209 765619b7cbb2
equal deleted inserted replaced
2:5f236d30879d 3:6dee89ef8800
    30 #include <lemon/bits/utility.h>
    30 #include <lemon/bits/utility.h>
    31 #include <lemon/bits/traits.h>
    31 #include <lemon/bits/traits.h>
    32 
    32 
    33 ///\ingroup spantree
    33 ///\ingroup spantree
    34 ///\file
    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 namespace lemon {
    40 namespace lemon {
    41 
    41 
    42   namespace _kruskal_bits {
    42   namespace _kruskal_bits {
   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>