Kruskal lenyegeben kesz.
Kell meg dokumentalni, meg meg egy par jol hasznalhato wrapper fv.
Es valamit meg kene csinalni azzal, hogy nem const ref. a kimeno boolmap,
viszont sokszor "on-the-fly" akarjuk megkonstrualni (es ilyenkor persze a
const-os mapet is lehet set-elni...)
1.1 --- a/src/work/johanna/kruskal.h Sat Apr 17 13:15:53 2004 +0000
1.2 +++ b/src/work/johanna/kruskal.h Sat Apr 17 19:19:57 2004 +0000
1.3 @@ -2,165 +2,75 @@
1.4 #ifndef HUGO_KRUSKAL_H
1.5 #define HUGO_KRUSKAL_H
1.6
1.7 -#include "unionfind.h"
1.8 #include <algorithm>
1.9 +#include <unionfind.h>
1.10 +#include <for_each_macros.h>
1.11
1.12 namespace hugo {
1.13
1.14 - template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
1.15 - typename EdgeCostMap::ValueType
1.16 - kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
1.17 - RetEdgeBoolMap &ret_bool_map);
1.18 + /// Kruskal's algorithm to compute a minimum cost tree
1.19
1.20 - template <typename Graph, typename EdgeCostMap, typename RetIterator>
1.21 - typename EdgeCostMap::ValueType
1.22 - kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
1.23 - RetIterator ret_iterator);
1.24 + template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.25 + typename InputEdgeOrder::ValueType
1.26 + Kruskal(Graph const& G, InputEdgeOrder const& edges,
1.27 + OutBoolMap& out_map)
1.28 + {
1.29 + typedef typename InputEdgeOrder::ValueType EdgeCost;
1.30 + typedef typename Graph::NodeMap<int> NodeIntMap;
1.31 + typedef typename Graph::Node Node;
1.32
1.33 - // FIXME: ret_iterator nem lehet referencia!!!
1.34 + NodeIntMap comp_map(G, -1);
1.35 + UnionFind<Node,NodeIntMap> uf(comp_map);
1.36 +
1.37 + EdgeCost tot_cost = 0;
1.38 + for (typename InputEdgeOrder::const_iterator p = edges.begin();
1.39 + p!=edges.end(); ++p ) {
1.40 + if ( uf.joinComponents(G.head(edges.first(p)),
1.41 + G.tail(edges.first(p))) ) {
1.42 + out_map.set(edges.first(p), true);
1.43 + tot_cost += edges.second(p);
1.44 + }
1.45 + else {
1.46 + out_map.set(edges.first(p), false);
1.47 + }
1.48 + }
1.49 + return tot_cost;
1.50 + }
1.51
1.52 - template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap>
1.53 - typename EdgeCostPairVec::value_type::second_type
1.54 - kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
1.55 - RetEdgeBoolMap &ret_bool_map);
1.56
1.57 - template <typename Graph, typename EdgeCostPairVec, typename RetIterator>
1.58 - typename EdgeCostPairVec::value_type::second_type
1.59 - kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
1.60 - RetIterator &ret_iterator);
1.61 +
1.62 + /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
1.63 +
1.64 + /// A writable bool-map that makes a sequence of "true" keys
1.65
1.66 - template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap>
1.67 - int
1.68 - kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec,
1.69 - RetEdgeBoolMap &ret_bool_map);
1.70 + /// A writable bool-map that creates a sequence out of keys that receive
1.71 + /// the value "true".
1.72 + /// \warning Not a regular property map, as it doesn't know its KeyType
1.73
1.74 - template <typename Graph, typename EdgePairVec, typename RetIterator>
1.75 - int
1.76 - kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec,
1.77 - RetIterator &ret_iterator);
1.78 -
1.79 -
1.80 - template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap,
1.81 - typename RetIterator>
1.82 - typename EdgeCostMap::ValueType
1.83 - kruskal7(Graph const& G, EdgeCostMap const& edge_costs,
1.84 - RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
1.85 -
1.86 - template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap,
1.87 - typename RetIterator>
1.88 - typename EdgeCostPairVec::value_type::second_type
1.89 - kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec,
1.90 - RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
1.91 -
1.92 - template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap,
1.93 - typename RetIterator>
1.94 - int
1.95 - kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec,
1.96 - RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator);
1.97 -
1.98 -
1.99 -
1.100 -
1.101 - template <typename Graph, typename InputEdgeOrder, typename OutputObserver>
1.102 - class MinCostTreeKruskal
1.103 - {
1.104 -
1.105 - typedef typename Graph::EdgeIt EdgeIt;
1.106 - typedef typename Graph::Edge Edge;
1.107 + template<typename Iterator>
1.108 + class SequenceOutput {
1.109 + Iterator it;
1.110
1.111 public:
1.112 - typedef typename InputEdgeOrder::ValueType EdgeCost;
1.113 -
1.114 - private:
1.115 - Graph const &G;
1.116 - InputEdgeOrder const &edges;
1.117 - OutputObserver &out_obs;
1.118 + typedef bool ValueType;
1.119
1.120 - public:
1.121 + SequenceOutput(Iterator const &_it) : it(_it) {}
1.122
1.123 -
1.124 - MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges,
1.125 - OutputObserver& _out_obs) :
1.126 - G(_G), edges(_edges), out_obs(_out_obs) {}
1.127 -
1.128 -
1.129 - EdgeCost run()
1.130 - {
1.131 - typedef typename Graph::NodeMap<int> NodeIntMap;
1.132 - typedef typename Graph::Node Node;
1.133 - NodeIntMap comp_map(G, -1);
1.134 - UnionFind<Node,NodeIntMap> uf(comp_map);
1.135 -
1.136 - EdgeCost tot_cost = 0;
1.137 - for (typename InputEdgeOrder::const_iterator p = edges.begin();
1.138 - p!=edges.end(); ++p ) {
1.139 - if ( uf.joinComponents(G.head(edges.first(p)),
1.140 - G.tail(edges.first(p))) ) {
1.141 - out_obs.setTrue(edges.first(p));
1.142 - tot_cost += edges.second(p);
1.143 - }
1.144 - else {
1.145 - out_obs.setFalse(edges.first(p));
1.146 - }
1.147 - }
1.148 - return tot_cost;
1.149 - }
1.150 -
1.151 + template<typename KeyType>
1.152 + void set(KeyType const& k, bool v) { if(v) {*it=k; ++it;} }
1.153 };
1.154
1.155 -
1.156 - /* ** ** Output-objektumok (Observerek (?)) ** ** */
1.157 -
1.158 - template <typename BoolMap>
1.159 - class BoolMapOutput {
1.160 - BoolMap &bm;
1.161 - typedef typename BoolMap::KeyType KeyType;
1.162 -
1.163 - public:
1.164 - BoolMapOutput(BoolMap &_bm) : bm(_bm) {}
1.165 -
1.166 - void setTrue(KeyType const& k) { bm.set(k, true); }
1.167 - void setFalse(KeyType const& k) { bm.set(k, false); }
1.168 - };
1.169 -
1.170 - template <typename Iterator>
1.171 - class SequenceOutput {
1.172 - Iterator ⁢
1.173 -
1.174 - public:
1.175 - SequenceOutput(Iterator &_it) : it(_it) {}
1.176 -
1.177 - template<typename KeyType>
1.178 - void setTrue(KeyType const& k) { *it=k; ++it; }
1.179 - template<typename KeyType>
1.180 - void setFalse(KeyType const& k) {}
1.181 - };
1.182 -
1.183 - template <typename BoolMap, typename Iterator>
1.184 - class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> {
1.185 - typedef BoolMapOutput<BoolMap> BMO;
1.186 - typedef SequenceOutput<Iterator> SO;
1.187 - public:
1.188 - CombinedOutput(BoolMap &_bm, Iterator &_it) :
1.189 - BMO(_bm), SO(_it) {}
1.190 -
1.191 - template<typename KeyType>
1.192 - void setTrue(KeyType const& k) {
1.193 - BMO::setTrue(k);
1.194 - SO::setTrue(k);
1.195 - }
1.196 - template<typename KeyType>
1.197 - void setFalse(KeyType const& k) {
1.198 - BMO::setFalse(k);
1.199 - SO::setFalse(k);
1.200 - }
1.201 - };
1.202 -
1.203 + template<typename Iterator>
1.204 + inline
1.205 + SequenceOutput<Iterator>
1.206 + makeSequenceOutput(Iterator it) {
1.207 + return SequenceOutput<Iterator>(it);
1.208 + }
1.209
1.210 /* ** ** InputSource -ok ** ** */
1.211
1.212 template<typename Key, typename Val>
1.213 - class PairVec : public std::vector< std::pair<Key,Val> > {
1.214 + class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
1.215
1.216 public:
1.217 typedef std::vector< std::pair<Key,Val> > Parent;
1.218 @@ -171,9 +81,7 @@
1.219 typedef typename Parent::iterator iterator;
1.220 typedef typename Parent::const_iterator const_iterator;
1.221
1.222 -
1.223 private:
1.224 -
1.225 class comparePair {
1.226 public:
1.227 bool operator()(PairType const& a, PairType const& b) {
1.228 @@ -184,7 +92,7 @@
1.229 public:
1.230
1.231 // FIXME: kell ez?
1.232 - // PairVec(Parent const& p) : Parent(p) {}
1.233 + // KruskalPairVec(Parent const& p) : Parent(p) {}
1.234
1.235 void sort() {
1.236 std::sort(begin(), end(), comparePair());
1.237 @@ -192,19 +100,17 @@
1.238
1.239 // FIXME: nem nagyon illik ez ide...
1.240 template<typename Graph, typename Map>
1.241 - void readGraphEdgeMap(Graph const& G, Map const& m) {
1.242 + KruskalPairVec(Graph const& G, Map const& m) {
1.243 typedef typename Graph::EdgeIt EdgeIt;
1.244
1.245 clear();
1.246 - for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.247 + FOR_EACH_LOC(EdgeIt, e, G) {
1.248 + // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.249 push_back(make_pair(e, m[e]));
1.250 }
1.251 -
1.252 sort();
1.253 }
1.254
1.255 - int alma() { return 5; /* FIXME */ }
1.256 -
1.257 Key const& first(const_iterator i) const { return i->first; }
1.258 Key& first(iterator i) { return i->first; }
1.259
1.260 @@ -212,38 +118,93 @@
1.261 Val& second(iterator i) { return i->second; }
1.262 };
1.263
1.264 +
1.265 + template <typename Map>
1.266 + class KruskalMapVec : public std::vector<typename Map::KeyType> {
1.267 + public:
1.268 +
1.269 + typedef typename Map::KeyType KeyType;
1.270 + typedef typename Map::ValueType ValueType;
1.271 +
1.272 + typedef typename std::vector<KeyType> Parent;
1.273 + typedef typename Parent::iterator iterator;
1.274 + typedef typename Parent::const_iterator const_iterator;
1.275 +
1.276 + private:
1.277 +
1.278 + const Map &m;
1.279 +
1.280 + class compareKeys {
1.281 + const Map &m;
1.282 + public:
1.283 + compareKeys(Map const &_m) : m(_m) {}
1.284 + bool operator()(KeyType const& a, KeyType const& b) {
1.285 + return m[a] < m[b];
1.286 + }
1.287 + };
1.288 +
1.289 + public:
1.290 +
1.291 + KruskalMapVec(Map const& _m) : m(_m) {}
1.292 +
1.293 + void sort() {
1.294 + std::sort(begin(), end(), compareKeys(m));
1.295 + }
1.296 +
1.297 + // FIXME: nem nagyon illik ez ide...
1.298 + template<typename Graph>
1.299 + KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
1.300 + typedef typename Graph::EdgeIt EdgeIt;
1.301 +
1.302 + clear();
1.303 + FOR_EACH_LOC(EdgeIt, e, G) {
1.304 + // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.305 + push_back(e);
1.306 + }
1.307 + sort();
1.308 + }
1.309 +
1.310 + KeyType const& first(const_iterator i) const { return *i; }
1.311 + KeyType& first(iterator i) { return *i; }
1.312 +
1.313 + ValueType const& second(const_iterator i) const { return m[*i]; }
1.314 + ValueType& second(iterator i) { return m[*i]; }
1.315 + };
1.316 +
1.317 /* ** ** Wrapper fuggvenyek ** ** */
1.318
1.319 +
1.320 + /// \brief Wrapper to Kruskal().
1.321 + /// Input is from an EdgeMap, output is a plain boolmap.
1.322 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
1.323 typename EdgeCostMap::ValueType
1.324 - kruskal1(Graph const& G, EdgeCostMap const& edge_costs,
1.325 - RetEdgeBoolMap &ret_bool_map) {
1.326 - typedef BoolMapOutput<RetEdgeBoolMap> OutObs;
1.327 - OutObs out(ret_bool_map);
1.328 + Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
1.329 + EdgeCostMap const& edge_costs,
1.330 + RetEdgeBoolMap &ret_bool_map) {
1.331
1.332 - typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
1.333 + typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
1.334 InputVec;
1.335 - InputVec iv;
1.336 - iv.readGraphEdgeMap(G, edge_costs);
1.337 + InputVec iv(G, edge_costs);
1.338
1.339 - MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
1.340 - return mctk.run();
1.341 + return Kruskal(G, iv, ret_bool_map);
1.342 }
1.343
1.344 +
1.345 + /// \brief Wrapper to Kruskal().
1.346 + /// Input is from an EdgeMap, output is to a sequence.
1.347 template <typename Graph, typename EdgeCostMap, typename RetIterator>
1.348 typename EdgeCostMap::ValueType
1.349 - kruskal2(Graph const& G, EdgeCostMap const& edge_costs,
1.350 - RetIterator ret_iterator) {
1.351 - typedef SequenceOutput<RetIterator> OutObs;
1.352 - OutObs out(ret_iterator);
1.353 + Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
1.354 + EdgeCostMap const& edge_costs,
1.355 + RetIterator ret_iterator) {
1.356 + typedef SequenceOutput<RetIterator> OutMap;
1.357 + OutMap out(ret_iterator);
1.358
1.359 - typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
1.360 + typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
1.361 InputVec;
1.362 - InputVec iv;
1.363 - iv.readGraphEdgeMap(G, edge_costs);
1.364 + InputVec iv(G, edge_costs);
1.365
1.366 - MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out);
1.367 - return mctk.run();
1.368 + return Kruskal(G, iv, out);
1.369 }
1.370
1.371
2.1 --- a/src/work/johanna/kruskal_test.cc Sat Apr 17 13:15:53 2004 +0000
2.2 +++ b/src/work/johanna/kruskal_test.cc Sat Apr 17 19:19:57 2004 +0000
2.3 @@ -71,7 +71,7 @@
2.4
2.5
2.6 cout << "Uniform 2-es koltseggel: "
2.7 - << kruskal1(G, edge_cost_map, tree_map)
2.8 + << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map)
2.9 << endl;
2.10
2.11
2.12 @@ -89,7 +89,8 @@
2.13 vector<Edge> tree_edge_vec;
2.14
2.15 cout << "Nemkonst koltseggel (-31): "
2.16 - << kruskal2(G, edge_cost_map, back_inserter(tree_edge_vec))
2.17 + << Kruskal_EdgeCostMapIn_IteratorOut(G, edge_cost_map,
2.18 + back_inserter(tree_edge_vec))
2.19 << endl;
2.20
2.21 int i = 1;
2.22 @@ -98,6 +99,21 @@
2.23 cout << i << ". el: " << *e << endl;
2.24 }
2.25
2.26 + tree_edge_vec.clear();
2.27 + SequenceOutput< back_insert_iterator< vector<Edge> > >
2.28 + vec_filler(back_inserter(tree_edge_vec));
2.29 + cout << "Nemkonst koltseggel tarhatekonyabban: "
2.30 + << Kruskal(G,
2.31 + KruskalMapVec<ECostMap>(G, edge_cost_map),
2.32 + vec_filler)
2.33 + << endl;
2.34 +
2.35 + i = 1;
2.36 + for(vector<Edge>::iterator e = tree_edge_vec.begin();
2.37 + e != tree_edge_vec.end(); ++e, ++i) {
2.38 + cout << i << ". el: " << *e << endl;
2.39 + }
2.40 +
2.41
2.42 // typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
2.43
3.1 --- a/src/work/johanna/unionfind.h Sat Apr 17 13:15:53 2004 +0000
3.2 +++ b/src/work/johanna/unionfind.h Sat Apr 17 19:19:57 2004 +0000
3.3 @@ -24,7 +24,7 @@
3.4
3.5 int whichComponent(T a)
3.6 {
3.7 - int comp0 = map.get(a);
3.8 + int comp0 = map[a];
3.9 if (comp0 < 0) {
3.10 return insertNewElement(a);
3.11 }