Changeset 1557:3e8d928e283d in lemon-0.x for lemon/kruskal.h

Timestamp:

07/14/05 14:23:15 (19 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2053

Message:

Each version of Kruskal is called the same ( kruskal(g,in,out) ) independently
from the input source and the output type.

File:

• lemon/kruskal.h (modified) (11 diffs)

lemon/kruskal.h

@@ -37 +37 @@
 ///
 ///Kruskal's algorithm to compute a minimum cost tree.
+///
+///\todo The file still needs some clean-up.
 
 namespace lemon {
@@ -46 +48 @@
 
   /// 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 
@@ -52 +56 @@
   /// undirected by disregarding the direction of the edges.
   ///
-  /// \param in This object is used to describe the edge costs. It must
-  /// be an STL compatible 'Forward Container'
+  /// \param in This object is used to describe the edge costs. It can be one
+  /// 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
-  /// cost-ascending order.
-  ///\par
-  /// For the sake of simplicity, there is a helper class KruskalMapInput,
-  /// which converts a
-  /// simple edge map to an input of this form. Alternatively, you can use
-  /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
-  /// the edge costs are given by an edge map.
-  ///
-  /// \retval out This must be a writable \c bool edge map.
+  /// where \c X is the type of the costs. The pairs indicates the edges along
+  /// with the assigned cost. <em>They must be in a
+  /// cost-ascending order.</em>
+  /// - Any readable Edge map. The values of the map indicate the edge costs.
+  ///
+  /// \retval out Here we also have a choise.
+  /// - Is can 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.
@@ -78 +95 @@
   /// (\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;
@@ -105 +136 @@
   }
 
+ 
+  /// @}
+
+  
   /* A work-around for running Kruskal with const-reference bool maps... */
 
@@ -123 +158 @@
     const Map &m;
   public:
+    typedef typename Map::Key Key;
     typedef typename Map::Value Value;
 
@@ -134 +170 @@
   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);
@@ -143 +185 @@
 
   /// Kruskal's input source.
-
+ 
   /// Kruskal's input source.
   ///
@@ -268 +310 @@
 
   public:
+    typedef typename Iterator::value_type Key;
     typedef bool Value;
 
@@ -287 +330 @@
   /* ** ** Wrapper funtions ** ** */
 
-
-
-  /// \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.
-  ///
-  ///\param g The type of the graph the algorithm runs on.
-  ///\param in An edge map containing the cost of the edges.
-  ///\par
-  ///The cost type can be any type satisfying the
-  ///STL 'LessThan Comparable'
-  ///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
-  /// 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.
-  ///
-  /// \return The cost of the found tree.
+//   \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.
+//  
+//   \param g The type of the graph the algorithm runs on.
+//   \param in An edge map containing the cost of the edges.
+//   \par
+//   The cost type can be any type satisfying the
+//   STL 'LessThan Comparable'
+//   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
+//   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.
+//  
+//   \return The cost of the found tree.
 
   template <class GR, class IN, class RET>
   inline
   typename IN::Value
-  kruskalEdgeMap(GR const& g,
-                 IN const& in,
-                 RET &out) {
+  kruskal(GR const& g,
+          IN const& in,
+          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),
@@ -322 +370 @@
   }
 
-  /// \brief Wrapper function to kruskal().
-  /// Input is from an edge map, output is an STL Sequence.
-  ///
-  /// Wrapper function to kruskal().
-  /// Input is from an edge map, output is an STL Sequence.
-  ///
-  ///\param g The type of the graph the algorithm runs on.
-  ///\param in An edge map containing the cost of the edges.
-  ///\par
-  ///The cost type can be any type satisfying the
-  ///STL 'LessThan Comparable'
-  ///concept if it also has an operator+() implemented. (It is necessary for
-  ///computing the total cost of the tree).
-  ///
-  /// \retval out This must 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);
-  /// kruskalEdgeMap_IteratorOut(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;
-  /// kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
-  /// \endcode
-  ///
-  /// \return The cost of the found tree.
-  ///
-  /// \bug its name does not follow the coding style.
+//   \brief Wrapper function to kruskal().
+//   Input is from an edge map, output is an STL Sequence.
+//  
+//   Wrapper function to kruskal().
+//   Input is from an edge map, output is an STL Sequence.
+//  
+//   \param g The type of the graph the algorithm runs on.
+//   \param in An edge map containing the cost of the edges.
+//   \par
+//   The cost type can be any type satisfying the
+//   STL 'LessThan Comparable'
+//   concept if it also has an operator+() implemented. (It is necessary for
+//   computing the total cost of the tree).
+//  
+//   \retval out This must 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);
+//   kruskalEdgeMap_IteratorOut(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;
+//   kruskalEdgeMap_IteratorOut(g,cost,std::back_inserter(tree));
+//   \endcode
+//  
+//   \return The cost of the found tree.
+//  
+//   \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,
-                             const IN& in,
-                             RET out)
+  kruskal(const GR& g,
+          const IN& in,
+          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);
   }
-
+ 
   /// @}