lemon-0.x: comparison lemon/kruskal.h

equal deleted inserted replaced

-:f042b1451d48
+:a9f53d822283
 ///\ingroup spantree
 ///\file
 ///\brief Kruskal's algorithm to compute a minimum cost tree
 ///
 ///Kruskal's algorithm to compute a minimum cost tree.
+///
+///\todo The file still needs some clean-up.
 namespace lemon {
 /// \addtogroup spantree
 /// @{
 /// Kruskal's algorithm to find a minimum cost tree of a graph.
 /// This function runs Kruskal's algorithm to find a minimum cost tree.
+/// Due to hard C++ hacking, it accepts various input and output types.
+///
 /// \param g The graph the algorithm runs on.
 /// It can be either \ref concept::StaticGraph "directed" or
 /// \ref concept::UndirStaticGraph "undirected".
 /// If the graph is directed, the algorithm consider it to be
 /// undirected by disregarding the direction of the edges.
 ///
-/// \param in This object is used to describe the edge costs. It must
+/// \param in This object is used to describe the edge costs. It can be one
-/// be an STL compatible 'Forward Container'
+/// of the following choices.
+/// - An STL compatible 'Forward Container'
 /// with <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>,
-/// where X is the type of the costs. It must contain every edge in
+/// where \c X is the type of the costs. The pairs indicates the edges along
-/// cost-ascending order.
+/// with the assigned cost. <em>They must be in a
-///\par
+/// cost-ascending order.</em>
-/// For the sake of simplicity, there is a helper class KruskalMapInput,
+/// - Any readable Edge map. The values of the map indicate the edge costs.
-/// which converts a
+///
-/// simple edge map to an input of this form. Alternatively, you can use
+/// \retval out Here we also have a choise.
-/// the function \ref kruskalEdgeMap to compute the minimum cost tree if
+/// - Is can be a writable \c bool edge map.
-/// the edge costs are given by an edge map.
-///
-/// \retval out This must be a writable \c bool edge map.
 /// After running the algorithm
 /// this will contain the found minimum cost spanning tree: the value of an
 /// edge will be set to \c true if it belongs to the tree, otherwise it will
 /// be set to \c false. The value of each edge will be set exactly once.
+/// - It can also be an iteraror of an STL Container with
+/// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
+/// The algorithm copies the elements of the found tree into this sequence.
+/// For example, if we know that the spanning tree of the graph \c g has
+/// say 53 edges then
+/// we can put its edges into a STL vector \c tree with a code like this.
+/// \code
+/// std::vector<Edge> tree(53);
+/// kruskal(g,cost,tree.begin());
+/// \endcode
+/// Or if we don't know in advance the size of the tree, we can write this.
+/// \code
+/// std::vector<Edge> tree;
+/// kruskal(g,cost,std::back_inserter(tree));
+/// \endcode
 ///
 /// \return The cost of the found tree.
 ///
 /// \todo Discuss the case of undirected graphs: In this case the algorithm
 /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some
 /// people would expect. So, one should be careful not to add both of the
 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
 /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
+#ifdef DOXYGEN
 template <class GR, class IN, class OUT>
 typename IN::value_type::second_type
 kruskal(GR const& g, IN const& in,
-		 OUT& out)
+	  OUT& out)
+#else
+template <class GR, class IN, class OUT>
+typename IN::value_type::second_type
+kruskal(GR const& g, IN const& in,
+	  OUT& out,
+// 	  typename IN::value_type::first_type = typename GR::Edge()
+// 	  ,typename OUT::Key = OUT::Key()
+// 	  //,typename OUT::Key = typename GR::Edge()
+	  const typename IN::value_type::first_type * =
+	  (const typename IN::value_type::first_type *)(0),
+	  const typename OUT::Key * = (const typename OUT::Key *)(0)
+	  )
+#endif
 {
 typedef typename IN::value_type::second_type EdgeCost;
 typedef typename GR::template NodeMap<int> NodeIntMap;
 typedef typename GR::Node Node;
 }
 }
 return tot_cost;
 }
+/// @}
 /* A work-around for running Kruskal with const-reference bool maps... */
 /// Helper class for calling kruskal with "constant" output map.
 /// Helper class for calling kruskal with output maps constructed
 /// third argument.
 template<class Map>
 class NonConstMapWr {
 const Map &m;
 public:
+typedef typename Map::Key Key;
 typedef typename Map::Value Value;
 NonConstMapWr(const Map &_m) : m(_m) {}
 template<class Key>
 };
 template <class GR, class IN, class OUT>
 inline
 typename IN::value_type::second_type
-kruskal(GR const& g, IN const& edges, OUT const& out_map)
+kruskal(GR const& g, IN const& edges, OUT const& out_map,
+// 	  typename IN::value_type::first_type = typename GR::Edge(),
+// 	  typename OUT::Key = GR::Edge()
+	  const typename IN::value_type::first_type * =
+	  (const typename IN::value_type::first_type *)(0),
+	  const typename OUT::Key * = (const typename OUT::Key *)(0)
+	  )
 {
 NonConstMapWr<OUT> map_wr(out_map);
 return kruskal(g, edges, map_wr);
 }
 /* ** ** Input-objects ** ** */
 /// Kruskal's input source.
 /// Kruskal's input source.
 ///
 /// In most cases you possibly want to use the \ref kruskalEdgeMap() instead.
 ///
 /// \sa makeKruskalMapInput()
 template<class Iterator>
 class KruskalSequenceOutput {
 mutable Iterator it;
 public:
+typedef typename Iterator::value_type Key;
 typedef bool Value;
 KruskalSequenceOutput(Iterator const &_it) : it(_it) {}
 template<typename Key>
 /* ** ** Wrapper funtions ** ** */
+//   \brief Wrapper function to kruskal().
+//   Input is from an edge map, output is a plain bool map.
-/// \brief Wrapper function to kruskal().
+//
-/// Input is from an edge map, output is a plain bool map.
+//   Wrapper function to kruskal().
-///
+//   Input is from an edge map, output is a plain bool map.
-/// Wrapper function to kruskal().
+//
-/// Input is from an edge map, output is a plain bool map.
+//   \param g The type of the graph the algorithm runs on.
-///
+//   \param in An edge map containing the cost of the edges.
-///\param g The type of the graph the algorithm runs on.
+//   \par
-///\param in An edge map containing the cost of the edges.
+//   The cost type can be any type satisfying the
-///\par
+//   STL 'LessThan Comparable'
-///The cost type can be any type satisfying the
+//   concept if it also has an operator+() implemented. (It is necessary for
-///STL 'LessThan Comparable'
+//   computing the total cost of the tree).
-///concept if it also has an operator+() implemented. (It is necessary for
+//
-///computing the total cost of the tree).
+//   \retval out This must be a writable \c bool edge map.
-///
+//   After running the algorithm
-/// \retval out This must be a writable \c bool edge map.
+//   this will contain the found minimum cost spanning tree: the value of an
-/// After running the algorithm
+//   edge will be set to \c true if it belongs to the tree, otherwise it will
-/// this will contain the found minimum cost spanning tree: the value of an
+//   be set to \c false. The value of each edge will be set exactly once.
-/// edge will be set to \c true if it belongs to the tree, otherwise it will
+//
-/// be set to \c false. The value of each edge will be set exactly once.
+//   \return The cost of the found tree.
-///
-/// \return The cost of the found tree.
 template <class GR, class IN, class RET>
 inline
 typename IN::Value
-kruskalEdgeMap(GR const& g,
+kruskal(GR const& g,
-		 IN const& in,
+	  IN const& in,
-		 RET &out) {
+	  RET &out,
+	  //	  typename IN::Key = typename GR::Edge(),
+	  //typename IN::Key = typename IN::Key (),
+	  //	  typename RET::Key = typename GR::Edge()
+	  const typename IN::Key *  = (const typename IN::Key *)(0),
+	  const typename RET::Key * = (const typename RET::Key *)(0)
+	  )
+{
 return kruskal(g,
 		   KruskalMapInput<GR,IN>(g,in),
 		   out);
 }
-/// \brief Wrapper function to kruskal().
+//   \brief Wrapper function to kruskal().
-/// Input is from an edge map, output is an STL Sequence.
+//   Input is from an edge map, output is an STL Sequence.
-///
+//
-/// Wrapper function to kruskal().
+//   Wrapper function to kruskal().
-/// Input is from an edge map, output is an STL Sequence.
+//   Input is from an edge map, output is an STL Sequence.
-///
+//
-///\param g The type of the graph the algorithm runs on.
+//   \param g The type of the graph the algorithm runs on.
-///\param in An edge map containing the cost of the edges.
+//   \param in An edge map containing the cost of the edges.
-///\par
+//   \par
-///The cost type can be any type satisfying the
+//   The cost type can be any type satisfying the
-///STL 'LessThan Comparable'
+//   STL 'LessThan Comparable'
-///concept if it also has an operator+() implemented. (It is necessary for
+//   concept if it also has an operator+() implemented. (It is necessary for
-///computing the total cost of the tree).
+//   computing the total cost of the tree).
-///
+//
-/// \retval out This must be an iteraror of an STL Container with
+//   \retval out This must be an iteraror of an STL Container with
-/// <tt>GR::Edge</tt> as its <tt>value_type</tt>.
+//   <tt>GR::Edge</tt> as its <tt>value_type</tt>.
-/// The algorithm copies the elements of the found tree into this sequence.
+//   The algorithm copies the elements of the found tree into this sequence.
-/// For example, if we know that the spanning tree of the graph \c g has
+//   For example, if we know that the spanning tree of the graph \c g has
-/// say 53 edges then
+//   say 53 edges then
-/// we can put its edges into a STL vector \c tree with a code like this.
+//   we can put its edges into a STL vector \c tree with a code like this.
-/// \code
+//   \code
-/// std::vector<Edge> tree(53);
+//   std::vector<Edge> tree(53);
-/// kruskalEdgeMap_IteratorOut(g,cost,tree.begin());
+//   kruskalEdgeMap_IteratorOut(g,cost,tree.begin());
-/// \endcode
+//   \endcode
-/// Or if we don't know in advance the size of the tree, we can write this.
+//   Or if we don't know in advance the size of the tree, we can write this.
-/// \code
+//   \code
-/// std::vector<Edge> tree;
+//   std::vector<Edge> tree;
-/// kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
+//   kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
-/// \endcode
+//   \endcode
-///
+//
-/// \return The cost of the found tree.
+//   \return The cost of the found tree.
-///
+//
-/// \bug its name does not follow the coding style.
+//   \bug its name does not follow the coding style.
 template <class GR, class IN, class RET>
 inline
 typename IN::Value
-kruskalEdgeMap_IteratorOut(const GR& g,
+kruskal(const GR& g,
-			     const IN& in,
+	  const IN& in,
-			     RET out)
+	  RET out,
+	  //,typename RET::value_type = typename GR::Edge()
+	  //,typename RET::value_type = typename RET::value_type()
+	  const typename RET::value_type * =
+	  (const typename RET::value_type *)(0)
+	  )
 {
 KruskalSequenceOutput<RET> _out(out);
 return kruskal(g, KruskalMapInput<GR,IN>(g, in), _out);
 }
 /// @}
 } //namespace lemon
 #endif //LEMON_KRUSKAL_H

changeset 1563	0853ed07a677
parent 1555	48769ac7ec32
child 1570	da93692e6537