Changeset 246:dc95ca4ebc7b in lemon0.x for src/work/johanna
 Timestamp:
 03/26/04 14:59:59 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@346
 Location:
 src/work/johanna
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

src/work/johanna/kruskal.h
r218 r246 8 8 namespace hugo { 9 9 10 11 template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap> 10 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> 11 typename EdgeCostMap::ValueType 12 kruskal1(Graph const& G, EdgeCostMap const& edge_costs, 13 RetEdgeBoolMap &ret_bool_map); 14 15 template <typename Graph, typename EdgeCostMap, typename RetIterator> 16 typename EdgeCostMap::ValueType 17 kruskal2(Graph const& G, EdgeCostMap const& edge_costs, 18 RetIterator ret_iterator); 19 20 // FIXME: ret_iterator nem lehet referencia!!! 21 22 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap> 23 typename EdgeCostPairVec::value_type::second_type 24 kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, 25 RetEdgeBoolMap &ret_bool_map); 26 27 template <typename Graph, typename EdgeCostPairVec, typename RetIterator> 28 typename EdgeCostPairVec::value_type::second_type 29 kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, 30 RetIterator &ret_iterator); 31 32 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap> 33 int 34 kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec, 35 RetEdgeBoolMap &ret_bool_map); 36 37 template <typename Graph, typename EdgePairVec, typename RetIterator> 38 int 39 kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec, 40 RetIterator &ret_iterator); 41 42 43 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap, 44 typename RetIterator> 45 typename EdgeCostMap::ValueType 46 kruskal7(Graph const& G, EdgeCostMap const& edge_costs, 47 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); 48 49 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap, 50 typename RetIterator> 51 typename EdgeCostPairVec::value_type::second_type 52 kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, 53 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); 54 55 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap, 56 typename RetIterator> 57 int 58 kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec, 59 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); 60 61 62 63 64 template <typename Graph, typename InputEdgeOrder, typename OutputObserver> 12 65 class MinCostTreeKruskal 13 66 { … … 17 70 18 71 public: 19 typedef typename EdgeCostMap::ValueType EdgeCost; 20 typedef std::pair<Edge, EdgeCost> EdgeCostPair; 21 typedef std::vector<EdgeCostPair> EdgeCostVector; 72 typedef typename InputEdgeOrder::ValueType EdgeCost; 22 73 23 74 private: 24 75 Graph const &G; 25 EdgeCostMap const &costmap; 26 EdgeBoolMap& treemap; 27 28 //template <typename EdgeCostPair> 29 class comparePair { 30 public: 31 bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) { 32 return a.second < b.second; 33 } 34 }; 35 36 public: 37 38 39 MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap, 40 EdgeBoolMap& _treemap) : G(_G), costmap(_costmap), 41 treemap(_treemap) {} 76 InputEdgeOrder const &edges; 77 OutputObserver &out_obs; 78 79 public: 80 81 82 MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, 83 OutputObserver& _out_obs) : 84 G(_G), edges(_edges), out_obs(_out_obs) {} 42 85 43 86 44 EdgeCost run() 45 { 46 EdgeCostVector rank; 47 for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { 48 rank.push_back(make_pair(e, costmap.get(e))); 49 } 50 51 std::sort(rank.begin(), rank.end(), comparePair()); 52 53 return run(rank); 54 55 } 56 57 EdgeCost run(EdgeCostVector const &rank) 87 EdgeCost run() 58 88 { 59 89 typedef typename Graph::NodeMap<int> NodeIntMap; … … 63 93 64 94 EdgeCost tot_cost = 0; 65 for (typename EdgeCostVector::const_iterator p = rank.begin(); 66 p!=rank.end(); ++p ) { 67 if ( uf.joinComponents(G.head(p>first), G.tail(p>first)) ) { 68 treemap.set(p>first, true); 69 tot_cost += p>second; 95 for (typename InputEdgeOrder::const_iterator p = edges.begin(); 96 p!=edges.end(); ++p ) { 97 if ( uf.joinComponents(G.head(edges.first(p)), 98 G.tail(edges.first(p))) ) { 99 out_obs.setTrue(edges.first(p)); 100 tot_cost += edges.second(p); 70 101 } 71 102 else { 72 treemap.set(p>first, false);103 out_obs.setFalse(edges.first(p)); 73 104 } 74 105 } 75 106 return tot_cost; 76 77 } 78 79 }; 107 } 108 109 }; 110 111 112 /* ** ** Outputobjektumok (Observerek (?)) ** ** */ 113 114 template <typename BoolMap> 115 class BoolMapOutput { 116 BoolMap &bm; 117 typedef typename BoolMap::KeyType KeyType; 118 119 public: 120 BoolMapOutput(BoolMap &_bm) : bm(_bm) {} 121 122 void setTrue(KeyType const& k) { bm.set(k, true); } 123 void setFalse(KeyType const& k) { bm.set(k, false); } 124 }; 125 126 template <typename Iterator> 127 class SequenceOutput { 128 Iterator ⁢ 129 130 public: 131 SequenceOutput(Iterator &_it) : it(_it) {} 132 133 template<typename KeyType> 134 void setTrue(KeyType const& k) { *it=k; ++it; } 135 template<typename KeyType> 136 void setFalse(KeyType const& k) {} 137 }; 138 139 template <typename BoolMap, typename Iterator> 140 class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> { 141 typedef BoolMapOutput<BoolMap> BMO; 142 typedef SequenceOutput<Iterator> SO; 143 public: 144 CombinedOutput(BoolMap &_bm, Iterator &_it) : 145 BMO(_bm), SO(_it) {} 146 147 template<typename KeyType> 148 void setTrue(KeyType const& k) { 149 BMO::setTrue(k); 150 SO::setTrue(k); 151 } 152 template<typename KeyType> 153 void setFalse(KeyType const& k) { 154 BMO::setFalse(k); 155 SO::setFalse(k); 156 } 157 }; 158 159 160 /* ** ** InputSource ok ** ** */ 161 162 template<typename Key, typename Val> 163 class PairVec : public std::vector< std::pair<Key,Val> > { 164 165 public: 166 typedef std::vector< std::pair<Key,Val> > Parent; 167 typedef Key KeyType; 168 typedef Val ValueType; 169 typedef std::pair<Key,Val> PairType; 170 171 typedef typename Parent::iterator iterator; 172 typedef typename Parent::const_iterator const_iterator; 173 174 175 private: 176 177 class comparePair { 178 public: 179 bool operator()(PairType const& a, PairType const& b) { 180 return a.second < b.second; 181 } 182 }; 183 184 public: 185 186 // FIXME: kell ez? 187 // PairVec(Parent const& p) : Parent(p) {} 188 189 void sort() { 190 std::sort(begin(), end(), comparePair()); 191 } 192 193 // FIXME: nem nagyon illik ez ide... 194 template<typename Graph, typename Map> 195 void readGraphEdgeMap(Graph const& G, Map const& m) { 196 typedef typename Graph::EdgeIt EdgeIt; 197 198 clear(); 199 for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { 200 push_back(make_pair(e, m[e])); 201 } 202 203 sort(); 204 } 205 206 int alma() { return 5; /* FIXME */ } 207 208 Key const& first(const_iterator i) const { return i>first; } 209 Key& first(iterator i) { return i>first; } 210 211 Val const& second(const_iterator i) const { return i>second; } 212 Val& second(iterator i) { return i>second; } 213 }; 214 215 /* ** ** Wrapper fuggvenyek ** ** */ 216 217 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> 218 typename EdgeCostMap::ValueType 219 kruskal1(Graph const& G, EdgeCostMap const& edge_costs, 220 RetEdgeBoolMap &ret_bool_map) { 221 typedef BoolMapOutput<RetEdgeBoolMap> OutObs; 222 OutObs out(ret_bool_map); 223 224 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> 225 InputVec; 226 InputVec iv; 227 iv.readGraphEdgeMap(G, edge_costs); 228 229 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out); 230 return mctk.run(); 231 } 232 233 template <typename Graph, typename EdgeCostMap, typename RetIterator> 234 typename EdgeCostMap::ValueType 235 kruskal2(Graph const& G, EdgeCostMap const& edge_costs, 236 RetIterator ret_iterator) { 237 typedef SequenceOutput<RetIterator> OutObs; 238 OutObs out(ret_iterator); 239 240 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> 241 InputVec; 242 InputVec iv; 243 iv.readGraphEdgeMap(G, edge_costs); 244 245 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out); 246 return mctk.run(); 247 } 80 248 81 249 
src/work/johanna/kruskal_test.cc
r218 r246 2 2 #include <iostream> 3 3 #include <map> 4 #include <vector> 4 5 5 6 #include <kruskal.h> … … 69 70 EBoolMap tree_map(G); 70 71 71 typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;72 72 73 MCTK mctk(G, edge_cost_map, tree_map); 74 double k0lts = mctk.run(); 73 cout << "Uniform 2es koltseggel: " 74 << kruskal1(G, edge_cost_map, tree_map) 75 << endl; 75 76 76 cout << "Uniform 2es koltseggel: " << k0lts << endl;77 77 78 // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol: 79 typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2; 80 MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map); 81 MCTK2::EdgeCostVector ecv; 82 ecv.push_back(make_pair(e1, 10)); 83 ecv.push_back(make_pair(e2, 9)); 84 ecv.push_back(make_pair(e3, 8)); 85 ecv.push_back(make_pair(e4, 7)); 86 ecv.push_back(make_pair(e5, 6)); 87 ecv.push_back(make_pair(e6, 5)); 88 ecv.push_back(make_pair(e7, 4)); 89 ecv.push_back(make_pair(e8, 3)); 90 ecv.push_back(make_pair(e9, 2)); 91 ecv.push_back(make_pair(e10, 1)); 78 edge_cost_map.set(e1, 10); 79 edge_cost_map.set(e2, 9); 80 edge_cost_map.set(e3, 8); 81 edge_cost_map.set(e4, 7); 82 edge_cost_map.set(e5, 6); 83 edge_cost_map.set(e6, 5); 84 edge_cost_map.set(e7, 4); 85 edge_cost_map.set(e8, 3); 86 edge_cost_map.set(e9, 2); 87 edge_cost_map.set(e10, 1); 92 88 93 k0lts = mctk2.run(ecv); 94 cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = " 95 << k0lts << endl; 89 vector<Edge> tree_edge_vec; 90 91 cout << "Nemkonst koltseggel (31): " 92 << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec)) 93 << endl; 94 95 int i = 1; 96 for(vector<Edge>::iterator e = tree_edge_vec.begin(); 97 e != tree_edge_vec.end(); ++e, ++i) { 98 cout << i << ". el: " << *e << endl; 99 } 100 101 102 // typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK; 103 104 // MCTK mctk(G, edge_cost_map, tree_map); 105 // double k0lts = mctk.run(); 106 107 // cout << "Uniform 2es koltseggel: " << k0lts << endl; 108 109 // // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol: 110 // typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2; 111 // MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map); 112 // MCTK2::EdgeCostVector ecv; 113 // ecv.push_back(make_pair(e1, 10)); 114 // ecv.push_back(make_pair(e2, 9)); 115 // ecv.push_back(make_pair(e3, 8)); 116 // ecv.push_back(make_pair(e4, 7)); 117 // ecv.push_back(make_pair(e5, 6)); 118 // ecv.push_back(make_pair(e6, 5)); 119 // ecv.push_back(make_pair(e7, 4)); 120 // ecv.push_back(make_pair(e8, 3)); 121 // ecv.push_back(make_pair(e9, 2)); 122 // ecv.push_back(make_pair(e10, 1)); 123 124 // k0lts = mctk2.run(ecv); 125 // cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = " 126 // << k0lts << endl; 96 127 97 128
Note: See TracChangeset
for help on using the changeset viewer.