1.1 --- a/lemon/kruskal.h	Tue Jun 07 16:12:14 2005 +0000
     1.2 +++ b/lemon/kruskal.h	Tue Jun 07 16:13:21 2005 +0000
     1.3 @@ -19,6 +19,7 @@
     1.4  
     1.5  #include <algorithm>
     1.6  #include <lemon/unionfind.h>
     1.7 +#include<lemon/utility.h>
     1.8  
     1.9  /**
    1.10  @defgroup spantree Minimum Cost Spanning Tree Algorithms
    1.11 @@ -66,6 +67,12 @@
    1.12    /// be set to \c false. The value of each edge will be set exactly once.
    1.13    ///
    1.14    /// \return The cost of the found tree.
    1.15 +  ///
    1.16 +  /// \todo Discuss the case of undirected graphs: In this case the algorithm
    1.17 +  /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some
    1.18 +  /// people would expect. So, one should be careful not to add both of the
    1.19 +  /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>.
    1.20 +  /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.)
    1.21  
    1.22    template <class GR, class IN, class OUT>
    1.23    typename IN::value_type::second_type
    1.24 @@ -166,6 +173,23 @@
    1.25        }
    1.26      };
    1.27  
    1.28 +    template<class _GR>
    1.29 +    typename enable_if<typename _GR::UndirTag,void>::type
    1.30 +    fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0) 
    1.31 +    {
    1.32 +      for(typename GR::UndirEdgeIt e(G);e!=INVALID;++e) 
    1.33 +	push_back(value_type(typename GR::Edge(e,true), m[e]));
    1.34 +    }
    1.35 +
    1.36 +    template<class _GR>
    1.37 +    typename disable_if<typename _GR::UndirTag,void>::type
    1.38 +    fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1) 
    1.39 +    {
    1.40 +      for(typename GR::EdgeIt e(G);e!=INVALID;++e) 
    1.41 +	push_back(value_type(e, m[e]));
    1.42 +    }
    1.43 +    
    1.44 +    
    1.45    public:
    1.46  
    1.47      void sort() {
    1.48 @@ -173,9 +197,7 @@
    1.49      }
    1.50  
    1.51      KruskalMapInput(GR const& G, Map const& m) {
    1.52 -      typedef typename GR::EdgeIt EdgeIt;
    1.53 -      
    1.54 -      for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
    1.55 +      fillWithEdges(G,m); 
    1.56        sort();
    1.57      }
    1.58    };