Changeset 218:5964f1c64ca1 in lemon-0.x for src/work/johanna/kruskal.h

Timestamp:

03/20/04 18:01:45 (20 years ago)

Author:

beckerjc

Branch:

default

Phase:

public

Convert:

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

Message:

unionfind: componentSize tagfv

kruskal: osztalyositva; lehet beadni sajat elorendezett el-koltseg vektort

nem tul elegans megoldas...

File:

• src/work/johanna/kruskal.h (modified) (1 diff)

src/work/johanna/kruskal.h

@@ -8 +8 @@
 namespace hugo {
 
-  template <typename EdgeCostPair> static
-  bool comparePair(EdgeCostPair const& a, EdgeCostPair const& b) {
-    return a.second < b.second;
-  }
+
+  template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
+  class MinCostTreeKruskal
+  {
+
+    typedef typename Graph::EdgeIt EdgeIt;
+    typedef typename Graph::Edge Edge;
+
+  public:
+    typedef typename EdgeCostMap::ValueType EdgeCost;
+    typedef std::pair<Edge, EdgeCost> EdgeCostPair;
+    typedef std::vector<EdgeCostPair> EdgeCostVector;
+    
+  private:
+    Graph const &G;
+    EdgeCostMap const &costmap;
+    EdgeBoolMap& treemap;
+    
+    //template <typename EdgeCostPair>
+    class comparePair {
+    public:
+      bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) {
+        return a.second < b.second;
+      }
+    };
+
+  public:
 
 
-  template <typename Graph, typename EdgeDoubleMap, typename EdgeBoolMap>
+    MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap, 
+                       EdgeBoolMap& _treemap) : G(_G), costmap(_costmap), 
+                                                treemap(_treemap) {}
+  
 
-  typename EdgeDoubleMap::ValueType 
-  MinCostTreeKruskal(Graph const& G, EdgeDoubleMap const& costmap, 
-                     EdgeBoolMap& treemap) 
-  {
+    EdgeCost run() 
+    {
+     EdgeCostVector rank;
+     for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
+        rank.push_back(make_pair(e, costmap.get(e)));
+      }
+      
+      std::sort(rank.begin(), rank.end(), comparePair());
+
+      return run(rank);
     
-    typedef typename EdgeDoubleMap::ValueType EDouble;
-    typedef typename Graph::EachEdgeIt EachEdgeIt;
-    typedef std::pair<EachEdgeIt, EDouble> EdgeCostPair;
-
-
-    typedef std::vector<EdgeCostPair> EdgeCostVector;
-    EdgeCostVector rank;
-
-    for (EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
-      rank.push_back(make_pair(e, costmap.get(e)));
     }
 
-    
-    std::sort(rank.begin(), rank.end(), comparePair<EdgeCostPair>);
+    EdgeCost run(EdgeCostVector const &rank)
+    {
+      typedef typename Graph::NodeMap<int> NodeIntMap;
+      typedef typename Graph::Node Node;
+      NodeIntMap comp_map(G, -1);
+      UnionFind<Node,NodeIntMap> uf(comp_map); 
+      
+      EdgeCost tot_cost = 0;
+      for (typename EdgeCostVector::const_iterator p = rank.begin(); 
+           p!=rank.end(); ++p ) {
+        if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
+          treemap.set(p->first, true);
+          tot_cost += p->second;
+        }
+        else {
+          treemap.set(p->first, false);
+        }
+      }
+      return tot_cost;
 
-    typedef typename Graph::NodeMap<int> NodeIntMap;
-    typedef typename Graph::NodeIt NodeIt;
-    NodeIntMap comp_map(G, -1);
-    UnionFind<NodeIt,NodeIntMap> uf(comp_map); 
+    }
 
-    EDouble tot_cost = 0;
-    for (typename EdgeCostVector::iterator p = rank.begin(); 
-         p!=rank.end(); ++p ) {
-      if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
-        treemap.set(p->first, true);
-        tot_cost += p->second;
-      }
-      else {
-        treemap.set(p->first, false);
-      }
-    }
-    return tot_cost;
-  }
+  };