# HG changeset patch
# User alpar
# Date 1118160801 0
# Node ID ac7e995e47e27f9f3d23faf66f694dece3b0971c
# Parent  0274acee0e35638115be3f95f3176437c5d6ddaa
Modify kruskal to work correctly with UndirGraphs.

diff -r 0274acee0e35 -r ac7e995e47e2 lemon/kruskal.h
--- a/lemon/kruskal.h	Tue Jun 07 16:12:14 2005 +0000
+++ b/lemon/kruskal.h	Tue Jun 07 16:13:21 2005 +0000
@@ -19,6 +19,7 @@
 
 #include <algorithm>
 #include <lemon/unionfind.h>
+#include<lemon/utility.h>
 
 /**
 @defgroup spantree Minimum Cost Spanning Tree Algorithms
@@ -66,6 +67,12 @@
   /// be set to \c false. The value of each edge will be set exactly once.
   ///
   /// \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.)
 
   template <class GR, class IN, class OUT>
   typename IN::value_type::second_type
@@ -166,6 +173,23 @@
       }
     };
 
+    template<class _GR>
+    typename enable_if<typename _GR::UndirTag,void>::type
+    fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0) 
+    {
+      for(typename GR::UndirEdgeIt e(G);e!=INVALID;++e) 
+	push_back(value_type(typename GR::Edge(e,true), m[e]));
+    }
+
+    template<class _GR>
+    typename disable_if<typename _GR::UndirTag,void>::type
+    fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1) 
+    {
+      for(typename GR::EdgeIt e(G);e!=INVALID;++e) 
+	push_back(value_type(e, m[e]));
+    }
+    
+    
   public:
 
     void sort() {
@@ -173,9 +197,7 @@
     }
 
     KruskalMapInput(GR const& G, Map const& m) {
-      typedef typename GR::EdgeIt EdgeIt;
-      
-      for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e]));
+      fillWithEdges(G,m); 
       sort();
     }
   };