[150] | 1 | // -*- c++ -*- // |
---|
| 2 | #ifndef HUGO_KRUSKAL_H |
---|
| 3 | #define HUGO_KRUSKAL_H |
---|
| 4 | |
---|
| 5 | #include <algorithm> |
---|
[737] | 6 | #include <hugo/unionfind.h> |
---|
[150] | 7 | |
---|
[682] | 8 | ///\file |
---|
| 9 | ///\brief Kruskal's algorithm to compute a minimum cost tree |
---|
| 10 | |
---|
[150] | 11 | namespace hugo { |
---|
| 12 | |
---|
[737] | 13 | /// Kruskal's algorithm to find a minimum cost tree of a graph. |
---|
| 14 | |
---|
| 15 | /// This function runs Kruskal's algorithm to find a minimum cost tree. |
---|
| 16 | /// \param G The graph the algorithm runs on. |
---|
| 17 | /// \param in This object is used to describe the edge costs. It must |
---|
| 18 | /// be an STL 'forward container' |
---|
| 19 | /// with value_type <tt> std::pair<Graph::Edge,X> </tt>, |
---|
| 20 | /// where X is the type of the costs. It must contain every edge in |
---|
| 21 | /// cost-ascending order. |
---|
| 22 | /// \retval out This must be a writeable EdgeMap. After running the algorithm |
---|
| 23 | /// this will contain the found minimum cost spanning tree: the value of an |
---|
| 24 | /// edge will be set to \c true if it belongs to the tree, otherwise it will |
---|
| 25 | /// be set to \c false. The value of each edge will be set exactly once.\n |
---|
| 26 | /// For the sake of simplicity, there is a helper class KruskalPairVec, |
---|
| 27 | /// which converts a |
---|
| 28 | /// simple EdgeMap to an input of this form. Alternatively, you can use |
---|
| 29 | /// the function \ref kruskalEdgeMap to compute the minimum cost tree if |
---|
| 30 | /// the edge costs are given by an EdgeMap. |
---|
| 31 | /// \return The cost of the found tree. |
---|
[150] | 32 | |
---|
[349] | 33 | template <typename Graph, typename InputEdgeOrder, typename OutBoolMap> |
---|
[737] | 34 | typename InputEdgeOrder::value_type::second_type |
---|
| 35 | kruskal(Graph const& G, InputEdgeOrder const& in, |
---|
| 36 | OutBoolMap& out) |
---|
[349] | 37 | { |
---|
[737] | 38 | typedef typename InputEdgeOrder::value_type::second_type EdgeCost; |
---|
| 39 | typedef typename Graph::template NodeMap<int> NodeIntMap; |
---|
[349] | 40 | typedef typename Graph::Node Node; |
---|
[246] | 41 | |
---|
[737] | 42 | NodeIntMap comp(G, -1); |
---|
| 43 | UnionFind<Node,NodeIntMap> uf(comp); |
---|
[349] | 44 | |
---|
| 45 | EdgeCost tot_cost = 0; |
---|
[737] | 46 | for (typename InputEdgeOrder::const_iterator p = in.begin(); |
---|
| 47 | p!=in.end(); ++p ) { |
---|
| 48 | if ( uf.join(G.head((*p).first), |
---|
| 49 | G.tail((*p).first)) ) { |
---|
| 50 | out.set((*p).first, true); |
---|
| 51 | tot_cost += (*p).second; |
---|
[349] | 52 | } |
---|
| 53 | else { |
---|
[737] | 54 | out.set((*p).first, false); |
---|
[349] | 55 | } |
---|
| 56 | } |
---|
| 57 | return tot_cost; |
---|
| 58 | } |
---|
[246] | 59 | |
---|
[352] | 60 | /* A work-around for running Kruskal with const-reference bool maps... */ |
---|
| 61 | |
---|
| 62 | template<typename Map> |
---|
| 63 | class NonConstMapWr { |
---|
| 64 | const Map &m; |
---|
| 65 | public: |
---|
| 66 | typedef typename Map::ValueType ValueType; |
---|
| 67 | |
---|
| 68 | NonConstMapWr(const Map &_m) : m(_m) {} |
---|
| 69 | |
---|
| 70 | template<typename KeyType> |
---|
| 71 | void set(KeyType const& k, ValueType const &v) const { m.set(k,v); } |
---|
| 72 | }; |
---|
| 73 | |
---|
| 74 | template <typename Graph, typename InputEdgeOrder, typename OutBoolMap> |
---|
| 75 | inline |
---|
| 76 | typename InputEdgeOrder::ValueType |
---|
[737] | 77 | kruskal(Graph const& G, InputEdgeOrder const& edges, |
---|
[352] | 78 | OutBoolMap const& out_map) |
---|
| 79 | { |
---|
| 80 | NonConstMapWr<OutBoolMap> map_wr(out_map); |
---|
[737] | 81 | return kruskal(G, edges, map_wr); |
---|
[352] | 82 | } |
---|
[246] | 83 | |
---|
[349] | 84 | |
---|
| 85 | /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */ |
---|
| 86 | |
---|
| 87 | /// A writable bool-map that makes a sequence of "true" keys |
---|
[246] | 88 | |
---|
[737] | 89 | /// A writable bool-map that creates a sequence out of keys that receives |
---|
[349] | 90 | /// the value "true". |
---|
| 91 | /// \warning Not a regular property map, as it doesn't know its KeyType |
---|
[246] | 92 | |
---|
[349] | 93 | template<typename Iterator> |
---|
| 94 | class SequenceOutput { |
---|
[352] | 95 | mutable Iterator it; |
---|
[150] | 96 | |
---|
[218] | 97 | public: |
---|
[349] | 98 | typedef bool ValueType; |
---|
[150] | 99 | |
---|
[349] | 100 | SequenceOutput(Iterator const &_it) : it(_it) {} |
---|
[150] | 101 | |
---|
[349] | 102 | template<typename KeyType> |
---|
[352] | 103 | void set(KeyType const& k, bool v) const { if(v) {*it=k; ++it;} } |
---|
[218] | 104 | }; |
---|
[150] | 105 | |
---|
[349] | 106 | template<typename Iterator> |
---|
| 107 | inline |
---|
| 108 | SequenceOutput<Iterator> |
---|
| 109 | makeSequenceOutput(Iterator it) { |
---|
| 110 | return SequenceOutput<Iterator>(it); |
---|
| 111 | } |
---|
[246] | 112 | |
---|
| 113 | /* ** ** InputSource -ok ** ** */ |
---|
| 114 | |
---|
[737] | 115 | /// Kruskal input source. |
---|
[246] | 116 | |
---|
[737] | 117 | /// Kruskal input source. |
---|
| 118 | /// |
---|
| 119 | template<typename Graph, typename Map> |
---|
| 120 | class KruskalPairVec |
---|
| 121 | : public std::vector< std::pair<typename Graph::Edge, |
---|
| 122 | typename Map::ValueType> > { |
---|
| 123 | |
---|
[246] | 124 | public: |
---|
[737] | 125 | typedef std::vector< std::pair<typename Graph::Edge, |
---|
| 126 | typename Map::ValueType> > Parent; |
---|
| 127 | typedef typename Parent::value_type value_type; |
---|
| 128 | // typedef Key KeyType; |
---|
| 129 | // typedef Val ValueType; |
---|
| 130 | // typedef std::pair<Key,Val> PairType; |
---|
| 131 | // typedef typename Parent::iterator iterator; |
---|
| 132 | // typedef typename Parent::const_iterator const_iterator; |
---|
[246] | 133 | |
---|
| 134 | private: |
---|
| 135 | class comparePair { |
---|
| 136 | public: |
---|
[737] | 137 | bool operator()(const value_type& a, |
---|
| 138 | const value_type& b) { |
---|
[246] | 139 | return a.second < b.second; |
---|
| 140 | } |
---|
| 141 | }; |
---|
| 142 | |
---|
| 143 | public: |
---|
| 144 | |
---|
| 145 | // FIXME: kell ez? |
---|
[349] | 146 | // KruskalPairVec(Parent const& p) : Parent(p) {} |
---|
[246] | 147 | |
---|
| 148 | void sort() { |
---|
[737] | 149 | std::sort(this->begin(), this->end(), comparePair()); |
---|
[246] | 150 | } |
---|
| 151 | |
---|
| 152 | // FIXME: nem nagyon illik ez ide... |
---|
[349] | 153 | KruskalPairVec(Graph const& G, Map const& m) { |
---|
[246] | 154 | typedef typename Graph::EdgeIt EdgeIt; |
---|
[737] | 155 | |
---|
| 156 | this->clear(); |
---|
| 157 | for(EdgeIt e(G);G.valid(e);G.next(e)) { |
---|
| 158 | // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
---|
[246] | 159 | push_back(make_pair(e, m[e])); |
---|
| 160 | } |
---|
| 161 | sort(); |
---|
| 162 | } |
---|
| 163 | |
---|
[737] | 164 | // Key const& first(const_iterator i) const { return i->first; } |
---|
| 165 | // Key& first(iterator i) { return i->first; } |
---|
[246] | 166 | |
---|
[737] | 167 | // Val const& second(const_iterator i) const { return i->second; } |
---|
| 168 | // Val& second(iterator i) { return i->second; } |
---|
[246] | 169 | }; |
---|
| 170 | |
---|
[349] | 171 | |
---|
[737] | 172 | // template <typename Map> |
---|
| 173 | // class KruskalMapVec : public std::vector<typename Map::KeyType> { |
---|
| 174 | // public: |
---|
| 175 | |
---|
| 176 | // typedef typename Map::KeyType KeyType; |
---|
| 177 | // typedef typename Map::ValueType ValueType; |
---|
[349] | 178 | |
---|
[737] | 179 | // typedef typename std::vector<KeyType> Parent; |
---|
| 180 | // typedef typename Parent::iterator iterator; |
---|
| 181 | // typedef typename Parent::const_iterator const_iterator; |
---|
[349] | 182 | |
---|
[737] | 183 | // private: |
---|
[349] | 184 | |
---|
[737] | 185 | // const Map &m; |
---|
[349] | 186 | |
---|
[737] | 187 | // class compareKeys { |
---|
| 188 | // const Map &m; |
---|
| 189 | // public: |
---|
| 190 | // compareKeys(Map const &_m) : m(_m) {} |
---|
| 191 | // bool operator()(KeyType const& a, KeyType const& b) { |
---|
| 192 | // return m[a] < m[b]; |
---|
| 193 | // } |
---|
| 194 | // }; |
---|
[349] | 195 | |
---|
[737] | 196 | // public: |
---|
[349] | 197 | |
---|
[737] | 198 | // KruskalMapVec(Map const& _m) : m(_m) {} |
---|
[349] | 199 | |
---|
[737] | 200 | // void sort() { |
---|
| 201 | // std::sort(begin(), end(), compareKeys(m)); |
---|
| 202 | // } |
---|
[349] | 203 | |
---|
[737] | 204 | // // FIXME: nem nagyon illik ez ide... |
---|
| 205 | // template<typename Graph> |
---|
| 206 | // KruskalMapVec(Graph const& G, Map const& _m) : m(_m) { |
---|
| 207 | // typedef typename Graph::EdgeIt EdgeIt; |
---|
[349] | 208 | |
---|
[737] | 209 | // clear(); |
---|
| 210 | // for(EdgeIt e(G);G.valid(e);G.next(e)) { |
---|
| 211 | // // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) |
---|
| 212 | // push_back(e); |
---|
| 213 | // } |
---|
| 214 | // sort(); |
---|
| 215 | // } |
---|
[349] | 216 | |
---|
[737] | 217 | // KeyType const& first(const_iterator i) const { return *i; } |
---|
| 218 | // KeyType& first(iterator i) { return *i; } |
---|
[349] | 219 | |
---|
[737] | 220 | // ValueType const& second(const_iterator i) const { return m[*i]; } |
---|
| 221 | // ValueType& second(iterator i) { return m[*i]; } |
---|
| 222 | // }; |
---|
[349] | 223 | |
---|
[246] | 224 | /* ** ** Wrapper fuggvenyek ** ** */ |
---|
| 225 | |
---|
[349] | 226 | |
---|
| 227 | /// \brief Wrapper to Kruskal(). |
---|
| 228 | /// Input is from an EdgeMap, output is a plain boolmap. |
---|
[737] | 229 | |
---|
| 230 | ///\todo some more words would be nice here. |
---|
| 231 | /// |
---|
[246] | 232 | template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
---|
[352] | 233 | inline |
---|
[246] | 234 | typename EdgeCostMap::ValueType |
---|
[737] | 235 | kruskalEdgeMap(Graph const& G, |
---|
| 236 | EdgeCostMap const& edge_costs, |
---|
| 237 | RetEdgeBoolMap &ret_bool_map) { |
---|
| 238 | |
---|
| 239 | typedef KruskalPairVec<Graph,EdgeCostMap> InputVec; |
---|
| 240 | |
---|
[349] | 241 | InputVec iv(G, edge_costs); |
---|
[737] | 242 | return kruskal(G, iv, ret_bool_map); |
---|
[246] | 243 | } |
---|
| 244 | |
---|
[349] | 245 | |
---|
| 246 | /// \brief Wrapper to Kruskal(). |
---|
| 247 | /// Input is from an EdgeMap, output is to a sequence. |
---|
[737] | 248 | |
---|
| 249 | ///\todo it does not follow the naming convention. |
---|
| 250 | /// |
---|
[246] | 251 | template <typename Graph, typename EdgeCostMap, typename RetIterator> |
---|
[352] | 252 | inline |
---|
[246] | 253 | typename EdgeCostMap::ValueType |
---|
[737] | 254 | kruskalEdgeMap_IteratorOut(const Graph& G, |
---|
| 255 | const EdgeCostMap& edge_costs, |
---|
| 256 | RetIterator ret_iterator) |
---|
| 257 | { |
---|
| 258 | typedef typename EdgeCostMap::ValueType ValueType; |
---|
| 259 | |
---|
[349] | 260 | typedef SequenceOutput<RetIterator> OutMap; |
---|
| 261 | OutMap out(ret_iterator); |
---|
[246] | 262 | |
---|
[737] | 263 | typedef KruskalPairVec<Graph, EdgeCostMap> InputVec; |
---|
| 264 | |
---|
[349] | 265 | InputVec iv(G, edge_costs); |
---|
[246] | 266 | |
---|
[737] | 267 | return kruskal(G, iv, out); |
---|
[246] | 268 | } |
---|
| 269 | |
---|
[150] | 270 | |
---|
| 271 | } //namespace hugo |
---|
| 272 | |
---|
| 273 | #endif //HUGO_KRUSKAL_H |
---|