Several changes in Kruskal alg.
- Input object interface was changed to an STL compatible one.
- template parameters of class KruskalPairVec has been simplified.
- (the most of) the names meet the naming conventions.
- a lot of (but still not enough) documentation has been added.
- class KruskalMapVec has been commented out.
1.1 --- a/src/work/johanna/kruskal.h Fri Jul 23 16:58:02 2004 +0000
1.2 +++ b/src/work/johanna/kruskal.h Fri Jul 23 17:13:23 2004 +0000
1.3 @@ -3,38 +3,55 @@
1.4 #define HUGO_KRUSKAL_H
1.5
1.6 #include <algorithm>
1.7 -#include <unionfind.h>
1.8 -#include <for_each_macros.h>
1.9 +#include <hugo/unionfind.h>
1.10
1.11 ///\file
1.12 ///\brief Kruskal's algorithm to compute a minimum cost tree
1.13
1.14 namespace hugo {
1.15
1.16 - /// Kruskal's algorithm to compute a minimum cost tree
1.17 + /// Kruskal's algorithm to find a minimum cost tree of a graph.
1.18 +
1.19 + /// This function runs Kruskal's algorithm to find a minimum cost tree.
1.20 + /// \param G The graph the algorithm runs on.
1.21 + /// \param in This object is used to describe the edge costs. It must
1.22 + /// be an STL 'forward container'
1.23 + /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
1.24 + /// where X is the type of the costs. It must contain every edge in
1.25 + /// cost-ascending order.
1.26 + /// \retval out This must be a writeable EdgeMap. After running the algorithm
1.27 + /// this will contain the found minimum cost spanning tree: the value of an
1.28 + /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.29 + /// be set to \c false. The value of each edge will be set exactly once.\n
1.30 + /// For the sake of simplicity, there is a helper class KruskalPairVec,
1.31 + /// which converts a
1.32 + /// simple EdgeMap to an input of this form. Alternatively, you can use
1.33 + /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
1.34 + /// the edge costs are given by an EdgeMap.
1.35 + /// \return The cost of the found tree.
1.36
1.37 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.38 - typename InputEdgeOrder::ValueType
1.39 - Kruskal(Graph const& G, InputEdgeOrder const& edges,
1.40 - OutBoolMap& out_map)
1.41 + typename InputEdgeOrder::value_type::second_type
1.42 + kruskal(Graph const& G, InputEdgeOrder const& in,
1.43 + OutBoolMap& out)
1.44 {
1.45 - typedef typename InputEdgeOrder::ValueType EdgeCost;
1.46 - typedef typename Graph::NodeMap<int> NodeIntMap;
1.47 + typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
1.48 + typedef typename Graph::template NodeMap<int> NodeIntMap;
1.49 typedef typename Graph::Node Node;
1.50
1.51 - NodeIntMap comp_map(G, -1);
1.52 - UnionFind<Node,NodeIntMap> uf(comp_map);
1.53 + NodeIntMap comp(G, -1);
1.54 + UnionFind<Node,NodeIntMap> uf(comp);
1.55
1.56 EdgeCost tot_cost = 0;
1.57 - for (typename InputEdgeOrder::const_iterator p = edges.begin();
1.58 - p!=edges.end(); ++p ) {
1.59 - if ( uf.join(G.head(edges.first(p)),
1.60 - G.tail(edges.first(p))) ) {
1.61 - out_map.set(edges.first(p), true);
1.62 - tot_cost += edges.second(p);
1.63 + for (typename InputEdgeOrder::const_iterator p = in.begin();
1.64 + p!=in.end(); ++p ) {
1.65 + if ( uf.join(G.head((*p).first),
1.66 + G.tail((*p).first)) ) {
1.67 + out.set((*p).first, true);
1.68 + tot_cost += (*p).second;
1.69 }
1.70 else {
1.71 - out_map.set(edges.first(p), false);
1.72 + out.set((*p).first, false);
1.73 }
1.74 }
1.75 return tot_cost;
1.76 @@ -57,11 +74,11 @@
1.77 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.78 inline
1.79 typename InputEdgeOrder::ValueType
1.80 - Kruskal(Graph const& G, InputEdgeOrder const& edges,
1.81 + kruskal(Graph const& G, InputEdgeOrder const& edges,
1.82 OutBoolMap const& out_map)
1.83 {
1.84 NonConstMapWr<OutBoolMap> map_wr(out_map);
1.85 - return Kruskal(G, edges, map_wr);
1.86 + return kruskal(G, edges, map_wr);
1.87 }
1.88
1.89
1.90 @@ -69,7 +86,7 @@
1.91
1.92 /// A writable bool-map that makes a sequence of "true" keys
1.93
1.94 - /// A writable bool-map that creates a sequence out of keys that receive
1.95 + /// A writable bool-map that creates a sequence out of keys that receives
1.96 /// the value "true".
1.97 /// \warning Not a regular property map, as it doesn't know its KeyType
1.98
1.99 @@ -95,22 +112,30 @@
1.100
1.101 /* ** ** InputSource -ok ** ** */
1.102
1.103 - template<typename Key, typename Val>
1.104 - class KruskalPairVec : public std::vector< std::pair<Key,Val> > {
1.105 + /// Kruskal input source.
1.106
1.107 + /// Kruskal input source.
1.108 + ///
1.109 + template<typename Graph, typename Map>
1.110 + class KruskalPairVec
1.111 + : public std::vector< std::pair<typename Graph::Edge,
1.112 + typename Map::ValueType> > {
1.113 +
1.114 public:
1.115 - typedef std::vector< std::pair<Key,Val> > Parent;
1.116 - typedef Key KeyType;
1.117 - typedef Val ValueType;
1.118 - typedef std::pair<Key,Val> PairType;
1.119 -
1.120 - typedef typename Parent::iterator iterator;
1.121 - typedef typename Parent::const_iterator const_iterator;
1.122 + typedef std::vector< std::pair<typename Graph::Edge,
1.123 + typename Map::ValueType> > Parent;
1.124 + typedef typename Parent::value_type value_type;
1.125 +// typedef Key KeyType;
1.126 +// typedef Val ValueType;
1.127 +// typedef std::pair<Key,Val> PairType;
1.128 +// typedef typename Parent::iterator iterator;
1.129 +// typedef typename Parent::const_iterator const_iterator;
1.130
1.131 private:
1.132 class comparePair {
1.133 public:
1.134 - bool operator()(PairType const& a, PairType const& b) {
1.135 + bool operator()(const value_type& a,
1.136 + const value_type& b) {
1.137 return a.second < b.second;
1.138 }
1.139 };
1.140 @@ -121,118 +146,125 @@
1.141 // KruskalPairVec(Parent const& p) : Parent(p) {}
1.142
1.143 void sort() {
1.144 - std::sort(begin(), end(), comparePair());
1.145 + std::sort(this->begin(), this->end(), comparePair());
1.146 }
1.147
1.148 // FIXME: nem nagyon illik ez ide...
1.149 - template<typename Graph, typename Map>
1.150 KruskalPairVec(Graph const& G, Map const& m) {
1.151 typedef typename Graph::EdgeIt EdgeIt;
1.152 -
1.153 - clear();
1.154 - FOR_EACH_LOC(EdgeIt, e, G) {
1.155 - // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.156 +
1.157 + this->clear();
1.158 + for(EdgeIt e(G);G.valid(e);G.next(e)) {
1.159 + // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.160 push_back(make_pair(e, m[e]));
1.161 }
1.162 sort();
1.163 }
1.164
1.165 - Key const& first(const_iterator i) const { return i->first; }
1.166 - Key& first(iterator i) { return i->first; }
1.167 +// Key const& first(const_iterator i) const { return i->first; }
1.168 +// Key& first(iterator i) { return i->first; }
1.169
1.170 - Val const& second(const_iterator i) const { return i->second; }
1.171 - Val& second(iterator i) { return i->second; }
1.172 +// Val const& second(const_iterator i) const { return i->second; }
1.173 +// Val& second(iterator i) { return i->second; }
1.174 };
1.175
1.176
1.177 - template <typename Map>
1.178 - class KruskalMapVec : public std::vector<typename Map::KeyType> {
1.179 - public:
1.180 +// template <typename Map>
1.181 +// class KruskalMapVec : public std::vector<typename Map::KeyType> {
1.182 +// public:
1.183 +
1.184 +// typedef typename Map::KeyType KeyType;
1.185 +// typedef typename Map::ValueType ValueType;
1.186
1.187 - typedef typename Map::KeyType KeyType;
1.188 - typedef typename Map::ValueType ValueType;
1.189 +// typedef typename std::vector<KeyType> Parent;
1.190 +// typedef typename Parent::iterator iterator;
1.191 +// typedef typename Parent::const_iterator const_iterator;
1.192
1.193 - typedef typename std::vector<KeyType> Parent;
1.194 - typedef typename Parent::iterator iterator;
1.195 - typedef typename Parent::const_iterator const_iterator;
1.196 +// private:
1.197
1.198 - private:
1.199 +// const Map &m;
1.200
1.201 - const Map &m;
1.202 +// class compareKeys {
1.203 +// const Map &m;
1.204 +// public:
1.205 +// compareKeys(Map const &_m) : m(_m) {}
1.206 +// bool operator()(KeyType const& a, KeyType const& b) {
1.207 +// return m[a] < m[b];
1.208 +// }
1.209 +// };
1.210
1.211 - class compareKeys {
1.212 - const Map &m;
1.213 - public:
1.214 - compareKeys(Map const &_m) : m(_m) {}
1.215 - bool operator()(KeyType const& a, KeyType const& b) {
1.216 - return m[a] < m[b];
1.217 - }
1.218 - };
1.219 +// public:
1.220
1.221 - public:
1.222 +// KruskalMapVec(Map const& _m) : m(_m) {}
1.223
1.224 - KruskalMapVec(Map const& _m) : m(_m) {}
1.225 +// void sort() {
1.226 +// std::sort(begin(), end(), compareKeys(m));
1.227 +// }
1.228
1.229 - void sort() {
1.230 - std::sort(begin(), end(), compareKeys(m));
1.231 - }
1.232 +// // FIXME: nem nagyon illik ez ide...
1.233 +// template<typename Graph>
1.234 +// KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
1.235 +// typedef typename Graph::EdgeIt EdgeIt;
1.236
1.237 - // FIXME: nem nagyon illik ez ide...
1.238 - template<typename Graph>
1.239 - KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
1.240 - typedef typename Graph::EdgeIt EdgeIt;
1.241 +// clear();
1.242 +// for(EdgeIt e(G);G.valid(e);G.next(e)) {
1.243 +// // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e))
1.244 +// push_back(e);
1.245 +// }
1.246 +// sort();
1.247 +// }
1.248
1.249 - clear();
1.250 - FOR_EACH_LOC(EdgeIt, e, G) {
1.251 - // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.252 - push_back(e);
1.253 - }
1.254 - sort();
1.255 - }
1.256 +// KeyType const& first(const_iterator i) const { return *i; }
1.257 +// KeyType& first(iterator i) { return *i; }
1.258
1.259 - KeyType const& first(const_iterator i) const { return *i; }
1.260 - KeyType& first(iterator i) { return *i; }
1.261 -
1.262 - ValueType const& second(const_iterator i) const { return m[*i]; }
1.263 - ValueType& second(iterator i) { return m[*i]; }
1.264 - };
1.265 +// ValueType const& second(const_iterator i) const { return m[*i]; }
1.266 +// ValueType& second(iterator i) { return m[*i]; }
1.267 +// };
1.268
1.269 /* ** ** Wrapper fuggvenyek ** ** */
1.270
1.271
1.272 /// \brief Wrapper to Kruskal().
1.273 /// Input is from an EdgeMap, output is a plain boolmap.
1.274 +
1.275 + ///\todo some more words would be nice here.
1.276 + ///
1.277 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
1.278 inline
1.279 typename EdgeCostMap::ValueType
1.280 - Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G,
1.281 - EdgeCostMap const& edge_costs,
1.282 - RetEdgeBoolMap &ret_bool_map) {
1.283 -
1.284 - typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
1.285 - InputVec;
1.286 + kruskalEdgeMap(Graph const& G,
1.287 + EdgeCostMap const& edge_costs,
1.288 + RetEdgeBoolMap &ret_bool_map) {
1.289 +
1.290 + typedef KruskalPairVec<Graph,EdgeCostMap> InputVec;
1.291 +
1.292 InputVec iv(G, edge_costs);
1.293 -
1.294 - return Kruskal(G, iv, ret_bool_map);
1.295 + return kruskal(G, iv, ret_bool_map);
1.296 }
1.297
1.298
1.299 /// \brief Wrapper to Kruskal().
1.300 /// Input is from an EdgeMap, output is to a sequence.
1.301 +
1.302 + ///\todo it does not follow the naming convention.
1.303 + ///
1.304 template <typename Graph, typename EdgeCostMap, typename RetIterator>
1.305 inline
1.306 typename EdgeCostMap::ValueType
1.307 - Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G,
1.308 - EdgeCostMap const& edge_costs,
1.309 - RetIterator ret_iterator) {
1.310 + kruskalEdgeMap_IteratorOut(const Graph& G,
1.311 + const EdgeCostMap& edge_costs,
1.312 + RetIterator ret_iterator)
1.313 + {
1.314 + typedef typename EdgeCostMap::ValueType ValueType;
1.315 +
1.316 typedef SequenceOutput<RetIterator> OutMap;
1.317 OutMap out(ret_iterator);
1.318
1.319 - typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType>
1.320 - InputVec;
1.321 + typedef KruskalPairVec<Graph, EdgeCostMap> InputVec;
1.322 +
1.323 InputVec iv(G, edge_costs);
1.324
1.325 - return Kruskal(G, iv, out);
1.326 + return kruskal(G, iv, out);
1.327 }
1.328
1.329
2.1 --- a/src/work/johanna/kruskal_test.cc Fri Jul 23 16:58:02 2004 +0000
2.2 +++ b/src/work/johanna/kruskal_test.cc Fri Jul 23 17:13:23 2004 +0000
2.3 @@ -4,7 +4,7 @@
2.4 #include <vector>
2.5
2.6 #include <kruskal.h>
2.7 -#include <list_graph.h>
2.8 +#include <hugo/list_graph.h>
2.9
2.10
2.11 using namespace std;
2.12 @@ -71,7 +71,7 @@
2.13
2.14
2.15 cout << "Uniform 2-es koltseggel: "
2.16 - << Kruskal_EdgeCostMapIn_BoolMapOut(G, edge_cost_map, tree_map)
2.17 + << kruskalEdgeMap(G, edge_cost_map, tree_map)
2.18 << endl;
2.19
2.20
2.21 @@ -89,14 +89,14 @@
2.22 vector<Edge> tree_edge_vec;
2.23
2.24 cout << "Nemkonst koltseggel (-31): "
2.25 - << Kruskal_EdgeCostMapIn_IteratorOut(G, edge_cost_map,
2.26 - back_inserter(tree_edge_vec))
2.27 + << kruskalEdgeMap_IteratorOut(G, edge_cost_map,
2.28 + back_inserter(tree_edge_vec))
2.29 << endl;
2.30
2.31 int i = 1;
2.32 for(vector<Edge>::iterator e = tree_edge_vec.begin();
2.33 e != tree_edge_vec.end(); ++e, ++i) {
2.34 - cout << i << ". el: " << *e << endl;
2.35 + cout << i << ". el: " << G.id(*e) << endl;
2.36 }
2.37
2.38 tree_edge_vec.clear();
2.39 @@ -107,19 +107,21 @@
2.40 // KruskalMapVec<ECostMap>(G, edge_cost_map),
2.41 // vec_filler)
2.42 // << endl;
2.43 - cout << "Nemkonst koltseggel tarhatekonyabban: "
2.44 - << Kruskal(G,
2.45 - KruskalMapVec<ECostMap>(G, edge_cost_map),
2.46 - makeSequenceOutput(back_inserter(tree_edge_vec))
2.47 - )
2.48 - << endl;
2.49
2.50 - i = 1;
2.51 - for(vector<Edge>::iterator e = tree_edge_vec.begin();
2.52 - e != tree_edge_vec.end(); ++e, ++i) {
2.53 - cout << i << ". el: " << *e << endl;
2.54 - }
2.55 +// cout << "Nemkonst koltseggel tarhatekonyabban: "
2.56 +// << kruskal(G,
2.57 +// KruskalMapVec<ECostMap>(G, edge_cost_map),
2.58 +// makeSequenceOutput(back_inserter(tree_edge_vec))
2.59 +// )
2.60 +// << endl;
2.61
2.62 +// i = 1;
2.63 +// for(vector<Edge>::iterator e = tree_edge_vec.begin();
2.64 +// e != tree_edge_vec.end(); ++e, ++i) {
2.65 +// cout << i << ". el: " << *e << endl;
2.66 +// }
2.67 +
2.68 +// **********************************************************************
2.69
2.70 // typedef MinCostTreeKruskal<ListGraph, ECostMap, EBoolMap> MCTK;
2.71