Index: lemon/kruskal.h
===================================================================
--- lemon/kruskal.h	(revision 1555)
+++ lemon/kruskal.h	(revision 1557)
@@ -37,4 +37,6 @@
 ///
 ///Kruskal's algorithm to compute a minimum cost tree.
+///
+///\todo The file still needs some clean-up.
 
 namespace lemon {
@@ -46,4 +48,6 @@
 
   /// 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,21 +56,34 @@
   /// 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,8 +95,22 @@
   /// (\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,4 +136,8 @@
   }
 
+ 
+  /// @}
+
+  
   /* A work-around for running Kruskal with const-reference bool maps... */
 
@@ -123,4 +158,5 @@
     const Map &m;
   public:
+    typedef typename Map::Key Key;
     typedef typename Map::Value Value;
 
@@ -134,5 +170,11 @@
   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,5 +185,5 @@
 
   /// Kruskal's input source.
-
+ 
   /// Kruskal's input source.
   ///
@@ -268,4 +310,5 @@
 
   public:
+    typedef typename Iterator::value_type Key;
     typedef bool Value;
 
@@ -287,34 +330,39 @@
   /* ** ** 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,49 +370,54 @@
   }
 
-  /// \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);
   }
-
+ 
   /// @}
 
