Changeset 1449:ac7e995e47e2 in lemon-0.x for lemon/kruskal.h

Timestamp:

06/07/05 18:13:21 (20 years ago)

Author:

Alpar Juttner

Branch:

default

Phase:

public

Convert:

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

Message:

Modify kruskal to work correctly with UndirGraphs?.

File:

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

lemon/kruskal.h

@@ -20 +20 @@
 #include <algorithm>
 #include <lemon/unionfind.h>
+#include<lemon/utility.h>
 
 /**
@@ -67 +68 @@
   ///
   /// \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>
@@ -167 +174 @@
     };
 
+    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:
 
@@ -174 +198 @@
 
     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();
     }