1.1 --- a/src/work/johanna/kruskal.h Fri Mar 26 13:03:09 2004 +0000
1.2 +++ b/src/work/johanna/kruskal.h Fri Mar 26 13:59:59 2004 +0000
1.3 @@ -7,8 +7,61 @@
1.4
1.5 namespace hugo {
1.6
1.7 + template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
1.8 + typename EdgeCostMap::ValueType
1.9 + kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
1.10 + RetEdgeBoolMap &ret_bool_map);
1.11
1.12 - template <typename Graph, typename EdgeCostMap, typename EdgeBoolMap>
1.13 + template <typename Graph, typename EdgeCostMap, typename RetIterator>
1.14 + typename EdgeCostMap::ValueType
1.15 + kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
1.16 + RetIterator ret_iterator);
1.17 +
1.18 + // FIXME: ret_iterator nem lehet referencia!!!
1.19 +
1.20 + template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
1.21 + typename EdgeCostPairVec::value_type::second_type
1.22 + kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
1.23 + RetEdgeBoolMap &ret_bool_map);
1.24 +
1.25 + template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
1.26 + typename EdgeCostPairVec::value_type::second_type
1.27 + kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
1.28 + RetIterator &ret_iterator);
1.29 +
1.30 + template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
1.31 + int
1.32 + kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
1.33 + RetEdgeBoolMap &ret_bool_map);
1.34 +
1.35 + template <typename Graph, typename EdgePairVec, typename RetIterator>
1.36 + int
1.37 + kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
1.38 + RetIterator &ret_iterator);
1.39 +
1.40 +
1.41 + template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
1.42 + typename RetIterator>
1.43 + typename EdgeCostMap::ValueType
1.44 + kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
1.45 + RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
1.46 +
1.47 + template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
1.48 + typename RetIterator>
1.49 + typename EdgeCostPairVec::value_type::second_type
1.50 + kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
1.51 + RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
1.52 +
1.53 + template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
1.54 + typename RetIterator>
1.55 + int
1.56 + kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
1.57 + RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
1.58 +
1.59 +
1.60 +
1.61 +
1.62 + template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
1.63 class MinCostTreeKruskal
1.64 {
1.65
1.66 @@ -16,45 +69,22 @@
1.67 typedef typename Graph::Edge Edge;
1.68
1.69 public:
1.70 - typedef typename EdgeCostMap::ValueType EdgeCost;
1.71 - typedef std::pair<Edge, EdgeCost> EdgeCostPair;
1.72 - typedef std::vector<EdgeCostPair> EdgeCostVector;
1.73 + typedef typename InputEdgeOrder::ValueType EdgeCost;
1.74
1.75 private:
1.76 Graph const &G;
1.77 - EdgeCostMap const &costmap;
1.78 - EdgeBoolMap& treemap;
1.79 -
1.80 - //template <typename EdgeCostPair>
1.81 - class comparePair {
1.82 - public:
1.83 - bool operator()(EdgeCostPair const& a, EdgeCostPair const& b) {
1.84 - return a.second < b.second;
1.85 - }
1.86 - };
1.87 + InputEdgeOrder const &edges;
1.88 + OutputObserver &out_obs;
1.89
1.90 public:
1.91
1.92
1.93 - MinCostTreeKruskal(Graph const& _G, EdgeCostMap const& _costmap,
1.94 - EdgeBoolMap& _treemap) : G(_G), costmap(_costmap),
1.95 - treemap(_treemap) {}
1.96 + MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges,
1.97 + OutputObserver& _out_obs) :
1.98 + G(_G), edges(_edges), out_obs(_out_obs) {}
1.99
1.100
1.101 - EdgeCost run()
1.102 - {
1.103 - EdgeCostVector rank;
1.104 - for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.105 - rank.push_back(make_pair(e, costmap.get(e)));
1.106 - }
1.107 -
1.108 - std::sort(rank.begin(), rank.end(), comparePair());
1.109 -
1.110 - return run(rank);
1.111 -
1.112 - }
1.113 -
1.114 - EdgeCost run(EdgeCostVector const &rank)
1.115 + EdgeCost run()
1.116 {
1.117 typedef typename Graph::NodeMap<int> NodeIntMap;
1.118 typedef typename Graph::Node Node;
1.119 @@ -62,22 +92,160 @@
1.120 UnionFind<Node,NodeIntMap> uf(comp_map);
1.121
1.122 EdgeCost tot_cost = 0;
1.123 - for (typename EdgeCostVector::const_iterator p = rank.begin();
1.124 - p!=rank.end(); ++p ) {
1.125 - if ( uf.joinComponents(G.head(p->first), G.tail(p->first)) ) {
1.126 - treemap.set(p->first, true);
1.127 - tot_cost += p->second;
1.128 + for (typename InputEdgeOrder::const_iterator p = edges.begin();
1.129 + p!=edges.end(); ++p ) {
1.130 + if ( uf.joinComponents(G.head(edges.first(p)),
1.131 + G.tail(edges.first(p))) ) {
1.132 + out_obs.setTrue(edges.first(p));
1.133 + tot_cost += edges.second(p);
1.134 }
1.135 else {
1.136 - treemap.set(p->first, false);
1.137 + out_obs.setFalse(edges.first(p));
1.138 }
1.139 }
1.140 return tot_cost;
1.141 -
1.142 }
1.143
1.144 };
1.145
1.146 +
1.147 + /* ** ** Output-objektumok (Observerek (?)) ** ** */
1.148 +
1.149 + template <typename BoolMap>
1.150 + class BoolMapOutput {
1.151 + BoolMap &bm;
1.152 + typedef typename BoolMap::KeyType KeyType;
1.153 +
1.154 + public:
1.155 + BoolMapOutput(BoolMap &_bm) : bm(_bm) {}
1.156 +
1.157 + void setTrue(KeyType const& k) { bm.set(k, true); }
1.158 + void setFalse(KeyType const& k) { bm.set(k, false); }
1.159 + };
1.160 +
1.161 + template <typename Iterator>
1.162 + class SequenceOutput {
1.163 + Iterator ⁢
1.164 +
1.165 + public:
1.166 + SequenceOutput(Iterator &_it) : it(_it) {}
1.167 +
1.168 + template<typename KeyType>
1.169 + void setTrue(KeyType const& k) { *it=k; ++it; }
1.170 + template<typename KeyType>
1.171 + void setFalse(KeyType const& k) {}
1.172 + };
1.173 +
1.174 + template <typename BoolMap, typename Iterator>
1.175 + class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
1.176 + typedef BoolMapOutput<BoolMap> BMO;
1.177 + typedef SequenceOutput<Iterator> SO;
1.178 + public:
1.179 + CombinedOutput(BoolMap &_bm, Iterator &_it) :
1.180 + BMO(_bm), SO(_it) {}
1.181 +
1.182 + template<typename KeyType>
1.183 + void setTrue(KeyType const& k) {
1.184 + BMO::setTrue(k);
1.185 + SO::setTrue(k);
1.186 + }
1.187 + template<typename KeyType>
1.188 + void setFalse(KeyType const& k) {
1.189 + BMO::setFalse(k);
1.190 + SO::setFalse(k);
1.191 + }
1.192 + };
1.193 +
1.194 +
1.195 + /* ** ** InputSource -ok ** ** */
1.196 +
1.197 + template<typename Key, typename Val>
1.198 + class PairVec : public std::vector< std::pair<Key,Val> > {
1.199 +
1.200 + public:
1.201 + typedef std::vector< std::pair<Key,Val> > Parent;
1.202 + typedef Key KeyType;
1.203 + typedef Val ValueType;
1.204 + typedef std::pair<Key,Val> PairType;
1.205 +
1.206 + typedef typename Parent::iterator iterator;
1.207 + typedef typename Parent::const_iterator const_iterator;
1.208 +
1.209 +
1.210 + private:
1.211 +
1.212 + class comparePair {
1.213 + public:
1.214 + bool operator()(PairType const& a, PairType const& b) {
1.215 + return a.second < b.second;
1.216 + }
1.217 + };
1.218 +
1.219 + public:
1.220 +
1.221 + // FIXME: kell ez?
1.222 + // PairVec(Parent const& p) : Parent(p) {}
1.223 +
1.224 + void sort() {
1.225 + std::sort(begin(), end(), comparePair());
1.226 + }
1.227 +
1.228 + // FIXME: nem nagyon illik ez ide...
1.229 + template<typename Graph, typename Map>
1.230 + void readGraphEdgeMap(Graph const& G, Map const& m) {
1.231 + typedef typename Graph::EdgeIt EdgeIt;
1.232 +
1.233 + clear();
1.234 + for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.235 + push_back(make_pair(e, m[e]));
1.236 + }
1.237 +
1.238 + sort();
1.239 + }
1.240 +
1.241 + int alma() { return 5; /* FIXME */ }
1.242 +
1.243 + Key const& first(const_iterator i) const { return i->first; }
1.244 + Key& first(iterator i) { return i->first; }
1.245 +
1.246 + Val const& second(const_iterator i) const { return i->second; }
1.247 + Val& second(iterator i) { return i->second; }
1.248 + };
1.249 +
1.250 + /* ** ** Wrapper fuggvenyek ** ** */
1.251 +
1.252 + template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
1.253 + typename EdgeCostMap::ValueType
1.254 + kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
1.255 + RetEdgeBoolMap &ret_bool_map) {
1.256 + typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
1.257 + OutObs out(ret_bool_map);
1.258 +
1.259 + typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
1.260 + InputVec;
1.261 + InputVec iv;
1.262 + iv.readGraphEdgeMap(G, edge_costs);
1.263 +
1.264 + MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
1.265 + return mctk.run();
1.266 + }
1.267 +
1.268 + template <typename Graph, typename EdgeCostMap, typename RetIterator>
1.269 + typename EdgeCostMap::ValueType
1.270 + kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
1.271 + RetIterator ret_iterator) {
1.272 + typedef SequenceOutput<RetIterator> OutObs;
1.273 + OutObs out(ret_iterator);
1.274 +
1.275 + typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
1.276 + InputVec;
1.277 + InputVec iv;
1.278 + iv.readGraphEdgeMap(G, edge_costs);
1.279 +
1.280 + MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
1.281 + return mctk.run();
1.282 + }
1.283 +
1.284
1.285 } //namespace hugo
1.286
2.1 --- a/src/work/johanna/kruskal_test.cc Fri Mar 26 13:03:09 2004 +0000
2.2 +++ b/src/work/johanna/kruskal_test.cc Fri Mar 26 13:59:59 2004 +0000
2.3 @@ -1,6 +1,7 @@
2.4 #include <string>
2.5 #include <iostream>
2.6 #include <map>
2.7 +#include <vector>
2.8
2.9 #include <kruskal.h>
2.10 #include <list_graph.h>
2.11 @@ -68,31 +69,61 @@
2.12 ECostMap edge_cost_map(G, 2);
2.13 EBoolMap tree_map(G);
2.14
2.15 - typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
2.16
2.17 - MCTK mctk(G, edge_cost_map, tree_map);
2.18 - double k0lts = mctk.run();
2.19 + cout << "Uniform 2-es koltseggel: "
2.20 + << kruskal1(G, edge_cost_map, tree_map)
2.21 + << endl;
2.22
2.23 - cout << "Uniform 2-es koltseggel: " << k0lts << endl;
2.24
2.25 - // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
2.26 - typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
2.27 - MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
2.28 - MCTK2::EdgeCostVector ecv;
2.29 - ecv.push_back(make_pair(e1, 10));
2.30 - ecv.push_back(make_pair(e2, 9));
2.31 - ecv.push_back(make_pair(e3, 8));
2.32 - ecv.push_back(make_pair(e4, 7));
2.33 - ecv.push_back(make_pair(e5, 6));
2.34 - ecv.push_back(make_pair(e6, 5));
2.35 - ecv.push_back(make_pair(e7, 4));
2.36 - ecv.push_back(make_pair(e8, 3));
2.37 - ecv.push_back(make_pair(e9, 2));
2.38 - ecv.push_back(make_pair(e10, 1));
2.39 + edge_cost_map.set(e1, -10);
2.40 + edge_cost_map.set(e2, -9);
2.41 + edge_cost_map.set(e3, -8);
2.42 + edge_cost_map.set(e4, -7);
2.43 + edge_cost_map.set(e5, -6);
2.44 + edge_cost_map.set(e6, -5);
2.45 + edge_cost_map.set(e7, -4);
2.46 + edge_cost_map.set(e8, -3);
2.47 + edge_cost_map.set(e9, -2);
2.48 + edge_cost_map.set(e10, -1);
2.49
2.50 - k0lts = mctk2.run(ecv);
2.51 - cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
2.52 - << k0lts << endl;
2.53 + vector<Edge> tree_edge_vec;
2.54 +
2.55 + cout << "Nemkonst koltseggel (-31): "
2.56 + << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec))
2.57 + << endl;
2.58 +
2.59 + int i = 1;
2.60 + for(vector<Edge>::iterator e = tree_edge_vec.begin();
2.61 + e != tree_edge_vec.end(); ++e, ++i) {
2.62 + cout << i << ". el: " << *e << endl;
2.63 + }
2.64 +
2.65 +
2.66 +// typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
2.67 +
2.68 +// MCTK mctk(G, edge_cost_map, tree_map);
2.69 +// double k0lts = mctk.run();
2.70 +
2.71 +// cout << "Uniform 2-es koltseggel: " << k0lts << endl;
2.72 +
2.73 +// // Max koltsegu fa szamitasa elore megrendezett koltseg vektorbol:
2.74 +// typedef MinCostTreeKruskal<ListGraph, DummyMap<Edge,int>, EBoolMap> MCTK2;
2.75 +// MCTK2 mctk2(G, DummyMap<Edge,int>(), tree_map);
2.76 +// MCTK2::EdgeCostVector ecv;
2.77 +// ecv.push_back(make_pair(e1, 10));
2.78 +// ecv.push_back(make_pair(e2, 9));
2.79 +// ecv.push_back(make_pair(e3, 8));
2.80 +// ecv.push_back(make_pair(e4, 7));
2.81 +// ecv.push_back(make_pair(e5, 6));
2.82 +// ecv.push_back(make_pair(e6, 5));
2.83 +// ecv.push_back(make_pair(e7, 4));
2.84 +// ecv.push_back(make_pair(e8, 3));
2.85 +// ecv.push_back(make_pair(e9, 2));
2.86 +// ecv.push_back(make_pair(e10, 1));
2.87 +
2.88 +// k0lts = mctk2.run(ecv);
2.89 +// cout << "Max koltsegu fa elore megrendezett koltseg vektorbol: 31 = "
2.90 +// << k0lts << endl;
2.91
2.92
2.93 return 0;