1 // -*- c++ -*- // |
1 // -*- c++ -*- // |
2 #ifndef HUGO_KRUSKAL_H |
2 #ifndef HUGO_KRUSKAL_H |
3 #define HUGO_KRUSKAL_H |
3 #define HUGO_KRUSKAL_H |
4 |
4 |
5 #include <algorithm> |
5 #include <algorithm> |
6 #include <unionfind.h> |
6 #include <hugo/unionfind.h> |
7 #include <for_each_macros.h> |
|
8 |
7 |
9 ///\file |
8 ///\file |
10 ///\brief Kruskal's algorithm to compute a minimum cost tree |
9 ///\brief Kruskal's algorithm to compute a minimum cost tree |
11 |
10 |
12 namespace hugo { |
11 namespace hugo { |
13 |
12 |
14 /// Kruskal's algorithm to compute a minimum cost tree |
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. |
15 |
32 |
16 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap> |
33 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap> |
17 typename InputEdgeOrder::ValueType |
34 typename InputEdgeOrder::value_type::second_type |
18 Kruskal(Graph const& G, InputEdgeOrder const& edges, |
35 kruskal(Graph const& G, InputEdgeOrder const& in, |
19 OutBoolMap& out_map) |
36 OutBoolMap& out) |
20 { |
37 { |
21 typedef typename InputEdgeOrder::ValueType EdgeCost; |
38 typedef typename InputEdgeOrder::value_type::second_type EdgeCost; |
22 typedef typename Graph::NodeMap<int> NodeIntMap; |
39 typedef typename Graph::template NodeMap<int> NodeIntMap; |
23 typedef typename Graph::Node Node; |
40 typedef typename Graph::Node Node; |
24 |
41 |
25 NodeIntMap comp_map(G, -1); |
42 NodeIntMap comp(G, -1); |
26 UnionFind<Node,NodeIntMap> uf(comp_map); |
43 UnionFind<Node,NodeIntMap> uf(comp); |
27 |
44 |
28 EdgeCost tot_cost = 0; |
45 EdgeCost tot_cost = 0; |
29 for (typename InputEdgeOrder::const_iterator p = edges.begin(); |
46 for (typename InputEdgeOrder::const_iterator p = in.begin(); |
30 p!=edges.end(); ++p ) { |
47 p!=in.end(); ++p ) { |
31 if ( uf.join(G.head(edges.first(p)), |
48 if ( uf.join(G.head((*p).first), |
32 G.tail(edges.first(p))) ) { |
49 G.tail((*p).first)) ) { |
33 out_map.set(edges.first(p), true); |
50 out.set((*p).first, true); |
34 tot_cost += edges.second(p); |
51 tot_cost += (*p).second; |
35 } |
52 } |
36 else { |
53 else { |
37 out_map.set(edges.first(p), false); |
54 out.set((*p).first, false); |
38 } |
55 } |
39 } |
56 } |
40 return tot_cost; |
57 return tot_cost; |
41 } |
58 } |
42 |
59 |
93 return SequenceOutput<Iterator>(it); |
110 return SequenceOutput<Iterator>(it); |
94 } |
111 } |
95 |
112 |
96 /* ** ** InputSource -ok ** ** */ |
113 /* ** ** InputSource -ok ** ** */ |
97 |
114 |
98 template<typename Key, typename Val> |
115 /// Kruskal input source. |
99 class KruskalPairVec : public std::vector< std::pair<Key,Val> > { |
116 |
100 |
117 /// Kruskal input source. |
101 public: |
118 /// |
102 typedef std::vector< std::pair<Key,Val> > Parent; |
119 template<typename Graph, typename Map> |
103 typedef Key KeyType; |
120 class KruskalPairVec |
104 typedef Val ValueType; |
121 : public std::vector< std::pair<typename Graph::Edge, |
105 typedef std::pair<Key,Val> PairType; |
122 typename Map::ValueType> > { |
106 |
123 |
107 typedef typename Parent::iterator iterator; |
124 public: |
108 typedef typename Parent::const_iterator const_iterator; |
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; |
109 |
133 |
110 private: |
134 private: |
111 class comparePair { |
135 class comparePair { |
112 public: |
136 public: |
113 bool operator()(PairType const& a, PairType const& b) { |
137 bool operator()(const value_type& a, |
|
138 const value_type& b) { |
114 return a.second < b.second; |
139 return a.second < b.second; |
115 } |
140 } |
116 }; |
141 }; |
117 |
142 |
118 public: |
143 public: |
119 |
144 |
120 // FIXME: kell ez? |
145 // FIXME: kell ez? |
121 // KruskalPairVec(Parent const& p) : Parent(p) {} |
146 // KruskalPairVec(Parent const& p) : Parent(p) {} |
122 |
147 |
123 void sort() { |
148 void sort() { |
124 std::sort(begin(), end(), comparePair()); |
149 std::sort(this->begin(), this->end(), comparePair()); |
125 } |
150 } |
126 |
151 |
127 // FIXME: nem nagyon illik ez ide... |
152 // FIXME: nem nagyon illik ez ide... |
128 template<typename Graph, typename Map> |
|
129 KruskalPairVec(Graph const& G, Map const& m) { |
153 KruskalPairVec(Graph const& G, Map const& m) { |
130 typedef typename Graph::EdgeIt EdgeIt; |
154 typedef typename Graph::EdgeIt EdgeIt; |
131 |
155 |
132 clear(); |
156 this->clear(); |
133 FOR_EACH_LOC(EdgeIt, e, G) { |
157 for(EdgeIt e(G);G.valid(e);G.next(e)) { |
134 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
158 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
135 push_back(make_pair(e, m[e])); |
159 push_back(make_pair(e, m[e])); |
136 } |
160 } |
137 sort(); |
161 sort(); |
138 } |
162 } |
139 |
163 |
140 Key const& first(const_iterator i) const { return i->first; } |
164 // Key const& first(const_iterator i) const { return i->first; } |
141 Key& first(iterator i) { return i->first; } |
165 // Key& first(iterator i) { return i->first; } |
142 |
166 |
143 Val const& second(const_iterator i) const { return i->second; } |
167 // Val const& second(const_iterator i) const { return i->second; } |
144 Val& second(iterator i) { return i->second; } |
168 // Val& second(iterator i) { return i->second; } |
145 }; |
169 }; |
146 |
170 |
147 |
171 |
148 template <typename Map> |
172 // template <typename Map> |
149 class KruskalMapVec : public std::vector<typename Map::KeyType> { |
173 // class KruskalMapVec : public std::vector<typename Map::KeyType> { |
150 public: |
174 // public: |
151 |
175 |
152 typedef typename Map::KeyType KeyType; |
176 // typedef typename Map::KeyType KeyType; |
153 typedef typename Map::ValueType ValueType; |
177 // typedef typename Map::ValueType ValueType; |
154 |
178 |
155 typedef typename std::vector<KeyType> Parent; |
179 // typedef typename std::vector<KeyType> Parent; |
156 typedef typename Parent::iterator iterator; |
180 // typedef typename Parent::iterator iterator; |
157 typedef typename Parent::const_iterator const_iterator; |
181 // typedef typename Parent::const_iterator const_iterator; |
158 |
182 |
159 private: |
183 // private: |
160 |
184 |
161 const Map &m; |
185 // const Map &m; |
162 |
186 |
163 class compareKeys { |
187 // class compareKeys { |
164 const Map &m; |
188 // const Map &m; |
165 public: |
189 // public: |
166 compareKeys(Map const &_m) : m(_m) {} |
190 // compareKeys(Map const &_m) : m(_m) {} |
167 bool operator()(KeyType const& a, KeyType const& b) { |
191 // bool operator()(KeyType const& a, KeyType const& b) { |
168 return m[a] < m[b]; |
192 // return m[a] < m[b]; |
169 } |
193 // } |
170 }; |
194 // }; |
171 |
195 |
172 public: |
196 // public: |
173 |
197 |
174 KruskalMapVec(Map const& _m) : m(_m) {} |
198 // KruskalMapVec(Map const& _m) : m(_m) {} |
175 |
199 |
176 void sort() { |
200 // void sort() { |
177 std::sort(begin(), end(), compareKeys(m)); |
201 // std::sort(begin(), end(), compareKeys(m)); |
178 } |
202 // } |
179 |
203 |
180 // FIXME: nem nagyon illik ez ide... |
204 // // FIXME: nem nagyon illik ez ide... |
181 template<typename Graph> |
205 // template<typename Graph> |
182 KruskalMapVec(Graph const& G, Map const& _m) : m(_m) { |
206 // KruskalMapVec(Graph const& G, Map const& _m) : m(_m) { |
183 typedef typename Graph::EdgeIt EdgeIt; |
207 // typedef typename Graph::EdgeIt EdgeIt; |
184 |
208 |
185 clear(); |
209 // clear(); |
186 FOR_EACH_LOC(EdgeIt, e, G) { |
210 // for(EdgeIt e(G);G.valid(e);G.next(e)) { |
187 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
211 // // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) |
188 push_back(e); |
212 // push_back(e); |
189 } |
213 // } |
190 sort(); |
214 // sort(); |
191 } |
215 // } |
192 |
216 |
193 KeyType const& first(const_iterator i) const { return *i; } |
217 // KeyType const& first(const_iterator i) const { return *i; } |
194 KeyType& first(iterator i) { return *i; } |
218 // KeyType& first(iterator i) { return *i; } |
195 |
219 |
196 ValueType const& second(const_iterator i) const { return m[*i]; } |
220 // ValueType const& second(const_iterator i) const { return m[*i]; } |
197 ValueType& second(iterator i) { return m[*i]; } |
221 // ValueType& second(iterator i) { return m[*i]; } |
198 }; |
222 // }; |
199 |
223 |
200 /* ** ** Wrapper fuggvenyek ** ** */ |
224 /* ** ** Wrapper fuggvenyek ** ** */ |
201 |
225 |
202 |
226 |
203 /// \brief Wrapper to Kruskal(). |
227 /// \brief Wrapper to Kruskal(). |
204 /// Input is from an EdgeMap, output is a plain boolmap. |
228 /// Input is from an EdgeMap, output is a plain boolmap. |
|
229 |
|
230 ///\todo some more words would be nice here. |
|
231 /// |
205 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
232 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
206 inline |
233 inline |
207 typename EdgeCostMap::ValueType |
234 typename EdgeCostMap::ValueType |
208 Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G, |
235 kruskalEdgeMap(Graph const& G, |
209 EdgeCostMap const& edge_costs, |
236 EdgeCostMap const& edge_costs, |
210 RetEdgeBoolMap &ret_bool_map) { |
237 RetEdgeBoolMap &ret_bool_map) { |
211 |
238 |
212 typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> |
239 typedef KruskalPairVec<Graph,EdgeCostMap> InputVec; |
213 InputVec; |
240 |
214 InputVec iv(G, edge_costs); |
241 InputVec iv(G, edge_costs); |
215 |
242 return kruskal(G, iv, ret_bool_map); |
216 return Kruskal(G, iv, ret_bool_map); |
|
217 } |
243 } |
218 |
244 |
219 |
245 |
220 /// \brief Wrapper to Kruskal(). |
246 /// \brief Wrapper to Kruskal(). |
221 /// Input is from an EdgeMap, output is to a sequence. |
247 /// Input is from an EdgeMap, output is to a sequence. |
|
248 |
|
249 ///\todo it does not follow the naming convention. |
|
250 /// |
222 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
251 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
223 inline |
252 inline |
224 typename EdgeCostMap::ValueType |
253 typename EdgeCostMap::ValueType |
225 Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G, |
254 kruskalEdgeMap_IteratorOut(const Graph& G, |
226 EdgeCostMap const& edge_costs, |
255 const EdgeCostMap& edge_costs, |
227 RetIterator ret_iterator) { |
256 RetIterator ret_iterator) |
|
257 { |
|
258 typedef typename EdgeCostMap::ValueType ValueType; |
|
259 |
228 typedef SequenceOutput<RetIterator> OutMap; |
260 typedef SequenceOutput<RetIterator> OutMap; |
229 OutMap out(ret_iterator); |
261 OutMap out(ret_iterator); |
230 |
262 |
231 typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> |
263 typedef KruskalPairVec<Graph, EdgeCostMap> InputVec; |
232 InputVec; |
264 |
233 InputVec iv(G, edge_costs); |
265 InputVec iv(G, edge_costs); |
234 |
266 |
235 return Kruskal(G, iv, out); |
267 return kruskal(G, iv, out); |
236 } |
268 } |
237 |
269 |
238 |
270 |
239 } //namespace hugo |
271 } //namespace hugo |
240 |
272 |