1.1 --- a/src/work/johanna/kruskal.h Mon Sep 06 13:47:54 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,311 +0,0 @@
1.4 -// -*- c++ -*- //
1.5 -#ifndef HUGO_KRUSKAL_H
1.6 -#define HUGO_KRUSKAL_H
1.7 -
1.8 -#include <algorithm>
1.9 -#include <hugo/unionfind.h>
1.10 -
1.11 -/**
1.12 -@defgroup spantree Minimum Cost Spanning Tree Algorithms
1.13 -\brief This group containes the algorithms for finding a minimum cost spanning
1.14 -tree in a graph
1.15 -@ingroup galgs
1.16 -*/
1.17 -
1.18 -///\ingroup spantree
1.19 -///\file
1.20 -///\brief Kruskal's algorithm to compute a minimum cost tree
1.21 -
1.22 -namespace hugo {
1.23 -
1.24 - /// \addtogroup spantree
1.25 - /// @{
1.26 -
1.27 - /// Kruskal's algorithm to find a minimum cost tree of a graph.
1.28 -
1.29 - /// This function runs Kruskal's algorithm to find a minimum cost tree.
1.30 - /// \param G The graph the algorithm runs on.
1.31 - /// \param in This object is used to describe the edge costs. It must
1.32 - /// be an STL 'forward container'
1.33 - /// with value_type <tt> std::pair<Graph::Edge,X> </tt>,
1.34 - /// where X is the type of the costs. It must contain every edge in
1.35 - /// cost-ascending order.
1.36 - /// \retval out This must be a writeable EdgeMap. After running the algorithm
1.37 - /// this will contain the found minimum cost spanning tree: the value of an
1.38 - /// edge will be set to \c true if it belongs to the tree, otherwise it will
1.39 - /// be set to \c false. The value of each edge will be set exactly once.\n
1.40 - /// For the sake of simplicity, there is a helper class KruskalPairVec,
1.41 - /// which converts a
1.42 - /// simple EdgeMap to an input of this form. Alternatively, you can use
1.43 - /// the function \ref kruskalEdgeMap to compute the minimum cost tree if
1.44 - /// the edge costs are given by an EdgeMap.
1.45 - /// \return The cost of the found tree.
1.46 -
1.47 - template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.48 - typename InputEdgeOrder::value_type::second_type
1.49 - kruskal(Graph const& G, InputEdgeOrder const& in,
1.50 - OutBoolMap& out)
1.51 - {
1.52 - typedef typename InputEdgeOrder::value_type::second_type EdgeCost;
1.53 - typedef typename Graph::template NodeMap<int> NodeIntMap;
1.54 - typedef typename Graph::Node Node;
1.55 -
1.56 - NodeIntMap comp(G, -1);
1.57 - UnionFind<Node,NodeIntMap> uf(comp);
1.58 -
1.59 - EdgeCost tot_cost = 0;
1.60 - for (typename InputEdgeOrder::const_iterator p = in.begin();
1.61 - p!=in.end(); ++p ) {
1.62 - if ( uf.join(G.head((*p).first),
1.63 - G.tail((*p).first)) ) {
1.64 - out.set((*p).first, true);
1.65 - tot_cost += (*p).second;
1.66 - }
1.67 - else {
1.68 - out.set((*p).first, false);
1.69 - }
1.70 - }
1.71 - return tot_cost;
1.72 - }
1.73 -
1.74 - /* A work-around for running Kruskal with const-reference bool maps... */
1.75 -
1.76 - template<typename Map>
1.77 - class NonConstMapWr {
1.78 - const Map &m;
1.79 - public:
1.80 - typedef typename Map::ValueType ValueType;
1.81 -
1.82 - NonConstMapWr(const Map &_m) : m(_m) {}
1.83 -
1.84 - template<typename KeyType>
1.85 - void set(KeyType const& k, ValueType const &v) const { m.set(k,v); }
1.86 - };
1.87 -
1.88 - template <typename Graph, typename InputEdgeOrder, typename OutBoolMap>
1.89 - inline
1.90 - typename InputEdgeOrder::ValueType
1.91 - kruskal(Graph const& G, InputEdgeOrder const& edges,
1.92 - OutBoolMap const& out_map)
1.93 - {
1.94 - NonConstMapWr<OutBoolMap> map_wr(out_map);
1.95 - return kruskal(G, edges, map_wr);
1.96 - }
1.97 -
1.98 -
1.99 - /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */
1.100 -
1.101 - /// A writable bool-map that makes a sequence of "true" keys
1.102 -
1.103 - /// A writable bool-map that creates a sequence out of keys that receives
1.104 - /// the value "true".
1.105 - /// \warning Not a regular property map, as it doesn't know its KeyType
1.106 -
1.107 - template<typename Iterator>
1.108 - class SequenceOutput {
1.109 - mutable Iterator it;
1.110 -
1.111 - public:
1.112 - typedef bool ValueType;
1.113 -
1.114 - SequenceOutput(Iterator const &_it) : it(_it) {}
1.115 -
1.116 - template<typename KeyType>
1.117 - void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} }
1.118 - };
1.119 -
1.120 - template<typename Iterator>
1.121 - inline
1.122 - SequenceOutput<Iterator>
1.123 - makeSequenceOutput(Iterator it) {
1.124 - return SequenceOutput<Iterator>(it);
1.125 - }
1.126 -
1.127 - /* ** ** InputSource -ok ** ** */
1.128 -
1.129 - /// Kruskal input source.
1.130 -
1.131 - /// Kruskal input source.
1.132 - ///
1.133 - template<typename Graph, typename Map>
1.134 - class KruskalMapInput
1.135 - : public std::vector< std::pair<typename Graph::Edge,
1.136 - typename Map::ValueType> > {
1.137 -
1.138 - public:
1.139 - typedef std::vector< std::pair<typename Graph::Edge,
1.140 - typename Map::ValueType> > Parent;
1.141 - typedef typename Parent::value_type value_type;
1.142 -// typedef Key KeyType;
1.143 -// typedef Val ValueType;
1.144 -// typedef std::pair<Key,Val> PairType;
1.145 -// typedef typename Parent::iterator iterator;
1.146 -// typedef typename Parent::const_iterator const_iterator;
1.147 -
1.148 - private:
1.149 - class comparePair {
1.150 - public:
1.151 - bool operator()(const value_type& a,
1.152 - const value_type& b) {
1.153 - return a.second < b.second;
1.154 - }
1.155 - };
1.156 -
1.157 - public:
1.158 -
1.159 - // FIXME: kell ez?
1.160 - // KruskalMapInput(Parent const& p) : Parent(p) {}
1.161 -
1.162 - void sort() {
1.163 - std::sort(this->begin(), this->end(), comparePair());
1.164 - }
1.165 -
1.166 - // FIXME: nem nagyon illik ez ide...
1.167 - KruskalMapInput(Graph const& G, Map const& m) {
1.168 - typedef typename Graph::EdgeIt EdgeIt;
1.169 -
1.170 - this->clear();
1.171 - for(EdgeIt e(G);G.valid(e);G.next(e)) {
1.172 - // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) {
1.173 - push_back(make_pair(e, m[e]));
1.174 - }
1.175 - sort();
1.176 - }
1.177 -
1.178 -// Key const& first(const_iterator i) const { return i->first; }
1.179 -// Key& first(iterator i) { return i->first; }
1.180 -
1.181 -// Val const& second(const_iterator i) const { return i->second; }
1.182 -// Val& second(iterator i) { return i->second; }
1.183 - };
1.184 -
1.185 -
1.186 -// template<typename Graph, typename Map>
1.187 -// class KruskalMapVec {
1.188 -// public:
1.189 -
1.190 -// typedef std::pair<typename Map::KeyType, Map::ValueType> value_type;
1.191 -
1.192 -// typedef std::vector<KeyType> Container;
1.193 -// Container container;
1.194 -// std::vector<typename Map::KeyType> container
1.195 -// const Map &m;
1.196 -
1.197 -
1.198 -// class iterator
1.199 -// {
1.200 -// Container::iterator i;
1.201 -// public:
1.202 -// iterator &operator ++() {++i;return *this;}
1.203 -// valuetype operator *() {return value_type(container(i),m[container(i)]);}
1.204 -// bool operator==(iterator b) {return i==b.i;}
1.205 -// iterator() {}
1.206 -// iterator(Container::iterator _i) i(_i) {}
1.207 -// };
1.208 -// class const_iterator
1.209 -// {
1.210 -// Container::const_iterator i;
1.211 -// public:
1.212 -// iterator &operator ++() {++i;return *this;}
1.213 -// valuetype operator *() {return value_type(container(i),m[container(i)]);}
1.214 -// bool operator==(iterator b) {return i==b.i;}
1.215 -// const_iterator() {}
1.216 -// const_iterator(Container::iterator _i) i(_i) {}
1.217 -// };
1.218 -
1.219 -// iterator begin() { return iterator(container.begin());}
1.220 -// const_iterator begin() const { return iterator(container.begin());}
1.221 -// iterator end() { return iterator(container.end());}
1.222 -// const_iterator end() const { return iterator(container.end());}
1.223 -
1.224 -// private:
1.225 -
1.226 -// class compareKeys {
1.227 -// const Map &m;
1.228 -// public:
1.229 -// compareKeys(Map const &_m) : m(_m) {}
1.230 -// bool operator()(KeyType const& a, KeyType const& b) {
1.231 -// return m[a] < m[b];
1.232 -// }
1.233 -// };
1.234 -
1.235 -// public:
1.236 -
1.237 -// KruskalMapVec(Map const& _m) : m(_m) {}
1.238 -
1.239 -// void sort() {
1.240 -// std::sort(begin(), end(), compareKeys(m));
1.241 -// }
1.242 -
1.243 -// // FIXME: nem nagyon illik ez ide...
1.244 -// template<typename Graph>
1.245 -// KruskalMapVec(Graph const& G, Map const& _m) : m(_m) {
1.246 -// typedef typename Graph::EdgeIt EdgeIt;
1.247 -
1.248 -// clear();
1.249 -// for(EdgeIt e(G);G.valid(e);G.next(e)) {
1.250 -// // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e))
1.251 -// push_back(e);
1.252 -// }
1.253 -// sort();
1.254 -// }
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 -// ValueType const& second(const_iterator i) const { return m[*i]; }
1.260 -// ValueType& second(iterator i) { return m[*i]; }
1.261 -// };
1.262 -
1.263 -
1.264 - /* ** ** Wrapper fuggvenyek ** ** */
1.265 -
1.266 -
1.267 - /// \brief Wrapper to Kruskal().
1.268 - /// Input is from an EdgeMap, output is a plain boolmap.
1.269 -
1.270 - ///\todo some more words would be nice here.
1.271 - ///
1.272 - template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap>
1.273 - inline
1.274 - typename EdgeCostMap::ValueType
1.275 - kruskalEdgeMap(Graph const& G,
1.276 - EdgeCostMap const& edge_costs,
1.277 - RetEdgeBoolMap &ret_bool_map) {
1.278 -
1.279 - typedef KruskalMapInput<Graph,EdgeCostMap> InputVec;
1.280 -
1.281 - InputVec iv(G, edge_costs);
1.282 - return kruskal(G, iv, ret_bool_map);
1.283 - }
1.284 -
1.285 -
1.286 - /// \brief Wrapper to Kruskal().
1.287 - /// Input is from an EdgeMap, output is to a sequence.
1.288 -
1.289 - ///\todo it does not follow the naming convention.
1.290 - ///
1.291 - template <typename Graph, typename EdgeCostMap, typename RetIterator>
1.292 - inline
1.293 - typename EdgeCostMap::ValueType
1.294 - kruskalEdgeMap_IteratorOut(const Graph& G,
1.295 - const EdgeCostMap& edge_costs,
1.296 - RetIterator ret_iterator)
1.297 - {
1.298 - typedef typename EdgeCostMap::ValueType ValueType;
1.299 -
1.300 - typedef SequenceOutput<RetIterator> OutMap;
1.301 - OutMap out(ret_iterator);
1.302 -
1.303 - typedef KruskalMapInput<Graph, EdgeCostMap> InputVec;
1.304 -
1.305 - InputVec iv(G, edge_costs);
1.306 -
1.307 - return kruskal(G, iv, out);
1.308 - }
1.309 -
1.310 - /// @}
1.311 -
1.312 -} //namespace hugo
1.313 -
1.314 -#endif //HUGO_KRUSKAL_H