lemon/kruskal.h
changeset 655 c706534d4740
parent 440 88ed40ad0d4f
child 921 140c953ad5d1
equal deleted inserted replaced
7:611c3db385da 8:d4ceaee6eae3
   246 
   246 
   247   }
   247   }
   248 
   248 
   249   /// \ingroup spantree
   249   /// \ingroup spantree
   250   ///
   250   ///
   251   /// \brief Kruskal algorithm to find a minimum cost spanning tree of
   251   /// \brief Kruskal's algorithm for finding a minimum cost spanning tree of
   252   /// a graph.
   252   /// a graph.
   253   ///
   253   ///
   254   /// This function runs Kruskal's algorithm to find a minimum cost
   254   /// This function runs Kruskal's algorithm to find a minimum cost
   255   /// spanning tree.
   255   /// spanning tree of a graph.
   256   /// Due to some C++ hacking, it accepts various input and output types.
   256   /// Due to some C++ hacking, it accepts various input and output types.
   257   ///
   257   ///
   258   /// \param g The graph the algorithm runs on.
   258   /// \param g The graph the algorithm runs on.
   259   /// It can be either \ref concepts::Digraph "directed" or
   259   /// It can be either \ref concepts::Digraph "directed" or
   260   /// \ref concepts::Graph "undirected".
   260   /// \ref concepts::Graph "undirected".
   262   /// undirected by disregarding the direction of the arcs.
   262   /// undirected by disregarding the direction of the arcs.
   263   ///
   263   ///
   264   /// \param in This object is used to describe the arc/edge costs.
   264   /// \param in This object is used to describe the arc/edge costs.
   265   /// It can be one of the following choices.
   265   /// It can be one of the following choices.
   266   /// - An STL compatible 'Forward Container' with
   266   /// - An STL compatible 'Forward Container' with
   267   /// <tt>std::pair<GR::Arc,X></tt> or
   267   /// <tt>std::pair<GR::Arc,C></tt> or
   268   /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where
   268   /// <tt>std::pair<GR::Edge,C></tt> as its <tt>value_type</tt>, where
   269   /// \c X is the type of the costs. The pairs indicates the arcs/edges
   269   /// \c C is the type of the costs. The pairs indicates the arcs/edges
   270   /// along with the assigned cost. <em>They must be in a
   270   /// along with the assigned cost. <em>They must be in a
   271   /// cost-ascending order.</em>
   271   /// cost-ascending order.</em>
   272   /// - Any readable arc/edge map. The values of the map indicate the
   272   /// - Any readable arc/edge map. The values of the map indicate the
   273   /// arc/edge costs.
   273   /// arc/edge costs.
   274   ///
   274   ///
   275   /// \retval out Here we also have a choice.
   275   /// \retval out Here we also have a choice.
   276   /// - It can be a writable \c bool arc/edge map. After running the
   276   /// - It can be a writable arc/edge map with \c bool value type. After
   277   /// algorithm it will contain the found minimum cost spanning
   277   /// running the algorithm it will contain the found minimum cost spanning
   278   /// tree: the value of an arc/edge will be set to \c true if it belongs
   278   /// 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
   279   /// to the tree, otherwise it will be set to \c false. The value of
   280   /// each arc/edge will be set exactly once.
   280   /// each arc/edge will be set exactly once.
   281   /// - It can also be an iteraror of an STL Container with
   281   /// - It can also be an iteraror of an STL Container with
   282   /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its
   282   /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its
   299   ///
   299   ///
   300   /// \note If the input graph is not (weakly) connected, a spanning
   300   /// \note If the input graph is not (weakly) connected, a spanning
   301   /// forest is calculated instead of a spanning tree.
   301   /// forest is calculated instead of a spanning tree.
   302 
   302 
   303 #ifdef DOXYGEN
   303 #ifdef DOXYGEN
   304   template <class Graph, class In, class Out>
   304   template <typename Graph, typename In, typename Out>
   305   Value kruskal(GR const& g, const In& in, Out& out)
   305   Value kruskal(const Graph& g, const In& in, Out& out)
   306 #else
   306 #else
   307   template <class Graph, class In, class Out>
   307   template <class Graph, class In, class Out>
   308   inline typename _kruskal_bits::KruskalValueSelector<In>::Value
   308   inline typename _kruskal_bits::KruskalValueSelector<In>::Value
   309   kruskal(const Graph& graph, const In& in, Out& out)
   309   kruskal(const Graph& graph, const In& in, Out& out)
   310 #endif
   310 #endif
   312     return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
   312     return _kruskal_bits::KruskalInputSelector<Graph, In, Out>::
   313       kruskal(graph, in, out);
   313       kruskal(graph, in, out);
   314   }
   314   }
   315 
   315 
   316 
   316 
   317 
       
   318 
       
   319   template <class Graph, class In, class Out>
   317   template <class Graph, class In, class Out>
   320   inline typename _kruskal_bits::KruskalValueSelector<In>::Value
   318   inline typename _kruskal_bits::KruskalValueSelector<In>::Value
   321   kruskal(const Graph& graph, const In& in, const Out& out)
   319   kruskal(const Graph& graph, const In& in, const Out& out)
   322   {
   320   {
   323     return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::
   321     return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>::