Changeset 246:dc95ca4ebc7b in lemon-0.x for src/work/johanna

Timestamp:

03/26/04 14:59:59 (21 years ago)

Author:

beckerjc

Branch:

default

Phase:

public

Convert:

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

Message:

koztes valtozat

Location:

src/work/johanna

Files:

• kruskal.h (modified) (3 diffs)
• kruskal_test.cc (modified) (2 diffs)

src/work/johanna/kruskal.h

@@ -8 +8 @@
 namespace hugo {
 
-
-  template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
+  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
+  typename EdgeCostMap::ValueType
+  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
+           RetEdgeBoolMap &ret_bool_map);
+
+  template <typename Graph, typename EdgeCostMap, typename RetIterator>
+  typename EdgeCostMap::ValueType
+  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
+           RetIterator ret_iterator);
+
+  // FIXME: ret_iterator nem lehet referencia!!!
+
+  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
+  typename EdgeCostPairVec::value_type::second_type
+  kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
+           RetEdgeBoolMap &ret_bool_map);
+
+  template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
+  typename EdgeCostPairVec::value_type::second_type
+  kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
+           RetIterator &ret_iterator);
+
+  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
+  int
+  kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
+           RetEdgeBoolMap &ret_bool_map);
+
+  template <typename Graph, typename EdgePairVec, typename RetIterator>
+  int
+  kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
+           RetIterator &ret_iterator);
+
+
+  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
+            typename RetIterator>
+  typename EdgeCostMap::ValueType
+  kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
+           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
+
+  template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
+            typename RetIterator>
+  typename EdgeCostPairVec::value_type::second_type
+  kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
+           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
+
+  template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
+            typename RetIterator>
+  int
+  kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
+           RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
+
+
+
+
+  template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
   class MinCostTreeKruskal
   {
@@ -17 +70 @@
 
   public:
-    typedef typename EdgeCostMap::ValueType EdgeCost;
-    typedef std::pair<Edge, EdgeCost> EdgeCostPair;
-    typedef std::vector<EdgeCostPair> EdgeCostVector;
+    typedef typename InputEdgeOrder::ValueType EdgeCost;
     
   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:
-
-
-    MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap, 
-                       EdgeBoolMap& _treemap) : G(_G), costmap(_costmap), 
-                                                treemap(_treemap) {}
+    InputEdgeOrder const &edges;
+    OutputObserver &out_obs;
+
+  public:
+
+
+    MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, 
+                       OutputObserver& _out_obs) : 
+      G(_G), edges(_edges), out_obs(_out_obs) {}
   
 
-    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);
-    
-    }
-
-    EdgeCost run(EdgeCostVector const &rank)
+    EdgeCost run()
     {
       typedef typename Graph::NodeMap<int> NodeIntMap;
@@ -63 +93 @@
       
       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;
+      for (typename InputEdgeOrder::const_iterator p = edges.begin(); 
+           p!=edges.end(); ++p ) {
+        if ( uf.joinComponents(G.head(edges.first(p)),
+                               G.tail(edges.first(p))) ) {
+          out_obs.setTrue(edges.first(p));
+          tot_cost += edges.second(p);
         }
         else {
-          treemap.set(p->first, false);
+          out_obs.setFalse(edges.first(p));
         }
       }
       return tot_cost;
-
-    }
-
-  };
+    }
+
+  };
+
+  
+  /* ** ** Output-objektumok (Observerek (?)) ** ** */
+  
+  template <typename BoolMap>
+  class BoolMapOutput {
+    BoolMap &bm;
+    typedef typename BoolMap::KeyType KeyType;
+
+  public:
+    BoolMapOutput(BoolMap &_bm) : bm(_bm) {}
+
+    void setTrue(KeyType const& k) { bm.set(k, true); }
+    void setFalse(KeyType const& k) { bm.set(k, false); }
+  };
+
+  template <typename Iterator>
+  class SequenceOutput {
+    Iterator &it;
+
+  public:
+    SequenceOutput(Iterator &_it) : it(_it) {}
+
+    template<typename KeyType>
+    void setTrue(KeyType const& k) { *it=k; ++it; }
+    template<typename KeyType>
+    void setFalse(KeyType const& k) {}
+  };
+
+  template <typename BoolMap, typename Iterator>
+  class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
+    typedef BoolMapOutput<BoolMap> BMO;
+    typedef SequenceOutput<Iterator> SO;
+  public:
+    CombinedOutput(BoolMap &_bm, Iterator &_it) :
+      BMO(_bm), SO(_it) {}
+
+    template<typename KeyType>
+    void setTrue(KeyType const& k) {
+      BMO::setTrue(k); 
+      SO::setTrue(k);
+    }
+    template<typename KeyType>
+    void setFalse(KeyType const& k) {
+      BMO::setFalse(k); 
+      SO::setFalse(k);      
+    }
+  };
+
+
+  /* ** ** InputSource -ok ** ** */
+
+  template<typename Key, typename Val>
+  class PairVec : public std::vector< std::pair<Key,Val> > {
+
+  public:
+    typedef std::vector< std::pair<Key,Val> > Parent;
+    typedef Key KeyType;
+    typedef Val ValueType;
+    typedef std::pair<Key,Val> PairType;
+
+    typedef typename Parent::iterator iterator;
+    typedef typename Parent::const_iterator const_iterator;
+
+
+  private:
+
+    class comparePair {
+    public:
+      bool operator()(PairType const& a, PairType const& b) {
+        return a.second < b.second;
+      }
+    };
+
+  public:
+
+    // FIXME: kell ez?
+    // PairVec(Parent const& p) : Parent(p) {}
+    
+    void sort() {
+      std::sort(begin(), end(), comparePair());
+    }
+
+    // FIXME: nem nagyon illik ez ide...
+    template<typename Graph, typename Map>
+    void readGraphEdgeMap(Graph const& G, Map const& m) {
+      typedef typename Graph::EdgeIt EdgeIt;
+
+      clear();
+      for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
+        push_back(make_pair(e, m[e]));
+      }
+
+      sort();
+    }
+
+    int alma() { return 5; /* FIXME */ }
+
+    Key const& first(const_iterator i) const { return i->first; }
+    Key& first(iterator i) { return i->first; }
+
+    Val const& second(const_iterator i) const { return i->second; }
+    Val& second(iterator i) { return i->second; }
+  };
+
+  /* ** ** Wrapper fuggvenyek ** ** */
+
+  template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
+  typename EdgeCostMap::ValueType
+  kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
+           RetEdgeBoolMap &ret_bool_map) {
+    typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
+    OutObs out(ret_bool_map);
+
+    typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
+      InputVec;
+    InputVec iv;
+    iv.readGraphEdgeMap(G, edge_costs);
+
+    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
+    return mctk.run();
+  }
+
+  template <typename Graph, typename EdgeCostMap, typename RetIterator>
+  typename EdgeCostMap::ValueType
+  kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
+           RetIterator ret_iterator) {
+    typedef SequenceOutput<RetIterator> OutObs;
+    OutObs out(ret_iterator);
+
+    typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
+      InputVec;
+    InputVec iv;
+    iv.readGraphEdgeMap(G, edge_costs);
+
+    MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
+    return mctk.run();    
+  }
 
 

src/work/johanna/kruskal_test.cc

@@ -2 +2 @@
 #include <iostream>
 #include <map>
+#include <vector>
 
 #include <kruskal.h>
@@ -69 +70 @@
   EBoolMap tree_map(G);
   
-  typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
 
-  MCTK mctk(G, edge_cost_map, tree_map);
-  double k0lts = mctk.run();
+  cout << "Uniform 2-es koltseggel: " 
+       << kruskal1(G, edge_cost_map, tree_map)
+       << endl;
 
-  cout << "Uniform 2-es koltseggel: " << k0lts << endl;
 
-  // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
-  typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
-  MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
-  MCTK2::EdgeCostVector ecv;
-  ecv.push_back(make_pair(e1, 10));
-  ecv.push_back(make_pair(e2, 9));
-  ecv.push_back(make_pair(e3, 8));
-  ecv.push_back(make_pair(e4, 7));
-  ecv.push_back(make_pair(e5, 6));
-  ecv.push_back(make_pair(e6, 5));
-  ecv.push_back(make_pair(e7, 4));
-  ecv.push_back(make_pair(e8, 3));
-  ecv.push_back(make_pair(e9, 2));
-  ecv.push_back(make_pair(e10, 1));
+  edge_cost_map.set(e1, -10);
+  edge_cost_map.set(e2, -9);
+  edge_cost_map.set(e3, -8);
+  edge_cost_map.set(e4, -7);
+  edge_cost_map.set(e5, -6);
+  edge_cost_map.set(e6, -5);
+  edge_cost_map.set(e7, -4);
+  edge_cost_map.set(e8, -3);
+  edge_cost_map.set(e9, -2);
+  edge_cost_map.set(e10, -1);
 
-  k0lts = mctk2.run(ecv);
-  cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
-       << k0lts << endl;
+  vector<Edge> tree_edge_vec;
+
+  cout << "Nemkonst koltseggel (-31): "
+       << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec))
+       << endl;
+
+  int i = 1;
+  for(vector<Edge>::iterator e = tree_edge_vec.begin();
+      e != tree_edge_vec.end(); ++e, ++i) {
+    cout << i << ". el: " << *e << endl;
+  }
+
+
+//   typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
+
+//   MCTK mctk(G, edge_cost_map, tree_map);
+//   double k0lts = mctk.run();
+
+//   cout << "Uniform 2-es koltseggel: " << k0lts << endl;
+
+//   // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
+//   typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
+//   MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
+//   MCTK2::EdgeCostVector ecv;
+//   ecv.push_back(make_pair(e1, 10));
+//   ecv.push_back(make_pair(e2, 9));
+//   ecv.push_back(make_pair(e3, 8));
+//   ecv.push_back(make_pair(e4, 7));
+//   ecv.push_back(make_pair(e5, 6));
+//   ecv.push_back(make_pair(e6, 5));
+//   ecv.push_back(make_pair(e7, 4));
+//   ecv.push_back(make_pair(e8, 3));
+//   ecv.push_back(make_pair(e9, 2));
+//   ecv.push_back(make_pair(e10, 1));
+
+//   k0lts = mctk2.run(ecv);
+//   cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
+//        << k0lts << endl;