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 "unionfind.h" |
|
6 #include <algorithm> |
5 #include <algorithm> |
|
6 #include <unionfind.h> |
|
7 #include <for_each_macros.h> |
7 |
8 |
8 namespace hugo { |
9 namespace hugo { |
9 |
10 |
10 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
11 /// Kruskal's algorithm to compute a minimum cost tree |
11 typename EdgeCostMap::ValueType |
12 |
12 kruskal1(Graph const& G, EdgeCostMap const& edge_costs, |
13 template <typename Graph, typename InputEdgeOrder, typename OutBoolMap> |
13 RetEdgeBoolMap &ret_bool_map); |
14 typename InputEdgeOrder::ValueType |
14 |
15 Kruskal(Graph const& G, InputEdgeOrder const& edges, |
15 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
16 OutBoolMap& out_map) |
16 typename EdgeCostMap::ValueType |
|
17 kruskal2(Graph const& G, EdgeCostMap const& edge_costs, |
|
18 RetIterator ret_iterator); |
|
19 |
|
20 // FIXME: ret_iterator nem lehet referencia!!! |
|
21 |
|
22 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap> |
|
23 typename EdgeCostPairVec::value_type::second_type |
|
24 kruskal3(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, |
|
25 RetEdgeBoolMap &ret_bool_map); |
|
26 |
|
27 template <typename Graph, typename EdgeCostPairVec, typename RetIterator> |
|
28 typename EdgeCostPairVec::value_type::second_type |
|
29 kruskal4(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, |
|
30 RetIterator &ret_iterator); |
|
31 |
|
32 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap> |
|
33 int |
|
34 kruskal5(Graph const& G, EdgePairVec const& edge_pair_vec, |
|
35 RetEdgeBoolMap &ret_bool_map); |
|
36 |
|
37 template <typename Graph, typename EdgePairVec, typename RetIterator> |
|
38 int |
|
39 kruskal6(Graph const& G, EdgePairVec const& edge_pair_vec, |
|
40 RetIterator &ret_iterator); |
|
41 |
|
42 |
|
43 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap, |
|
44 typename RetIterator> |
|
45 typename EdgeCostMap::ValueType |
|
46 kruskal7(Graph const& G, EdgeCostMap const& edge_costs, |
|
47 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); |
|
48 |
|
49 template <typename Graph, typename EdgeCostPairVec, typename RetEdgeBoolMap, |
|
50 typename RetIterator> |
|
51 typename EdgeCostPairVec::value_type::second_type |
|
52 kruskal8(Graph const& G, EdgeCostPairVec const& edge_cost_pair_vec, |
|
53 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); |
|
54 |
|
55 template <typename Graph, typename EdgePairVec, typename RetEdgeBoolMap, |
|
56 typename RetIterator> |
|
57 int |
|
58 kruskal9(Graph const& G, EdgePairVec const& edge_pair_vec, |
|
59 RetEdgeBoolMap &ret_bool_map, RetIterator &ret_iterator); |
|
60 |
|
61 |
|
62 |
|
63 |
|
64 template <typename Graph, typename InputEdgeOrder, typename OutputObserver> |
|
65 class MinCostTreeKruskal |
|
66 { |
17 { |
67 |
|
68 typedef typename Graph::EdgeIt EdgeIt; |
|
69 typedef typename Graph::Edge Edge; |
|
70 |
|
71 public: |
|
72 typedef typename InputEdgeOrder::ValueType EdgeCost; |
18 typedef typename InputEdgeOrder::ValueType EdgeCost; |
73 |
19 typedef typename Graph::NodeMap<int> NodeIntMap; |
74 private: |
20 typedef typename Graph::Node Node; |
75 Graph const &G; |
21 |
76 InputEdgeOrder const &edges; |
22 NodeIntMap comp_map(G, -1); |
77 OutputObserver &out_obs; |
23 UnionFind<Node,NodeIntMap> uf(comp_map); |
78 |
24 |
79 public: |
25 EdgeCost tot_cost = 0; |
80 |
26 for (typename InputEdgeOrder::const_iterator p = edges.begin(); |
81 |
27 p!=edges.end(); ++p ) { |
82 MinCostTreeKruskal(Graph const& _G, InputEdgeOrder const& _edges, |
28 if ( uf.joinComponents(G.head(edges.first(p)), |
83 OutputObserver& _out_obs) : |
29 G.tail(edges.first(p))) ) { |
84 G(_G), edges(_edges), out_obs(_out_obs) {} |
30 out_map.set(edges.first(p), true); |
|
31 tot_cost += edges.second(p); |
|
32 } |
|
33 else { |
|
34 out_map.set(edges.first(p), false); |
|
35 } |
|
36 } |
|
37 return tot_cost; |
|
38 } |
|
39 |
|
40 |
85 |
41 |
86 |
42 /* ** ** Output-objektumok: egyszeruen extra bool mapek ** ** */ |
87 EdgeCost run() |
43 |
88 { |
44 /// A writable bool-map that makes a sequence of "true" keys |
89 typedef typename Graph::NodeMap<int> NodeIntMap; |
45 |
90 typedef typename Graph::Node Node; |
46 /// A writable bool-map that creates a sequence out of keys that receive |
91 NodeIntMap comp_map(G, -1); |
47 /// the value "true". |
92 UnionFind<Node,NodeIntMap> uf(comp_map); |
48 /// \warning Not a regular property map, as it doesn't know its KeyType |
93 |
49 |
94 EdgeCost tot_cost = 0; |
50 template<typename Iterator> |
95 for (typename InputEdgeOrder::const_iterator p = edges.begin(); |
51 class SequenceOutput { |
96 p!=edges.end(); ++p ) { |
52 Iterator it; |
97 if ( uf.joinComponents(G.head(edges.first(p)), |
53 |
98 G.tail(edges.first(p))) ) { |
54 public: |
99 out_obs.setTrue(edges.first(p)); |
55 typedef bool ValueType; |
100 tot_cost += edges.second(p); |
56 |
101 } |
57 SequenceOutput(Iterator const &_it) : it(_it) {} |
102 else { |
58 |
103 out_obs.setFalse(edges.first(p)); |
59 template<typename KeyType> |
104 } |
60 void set(KeyType const& k, bool v) { if(v) {*it=k; ++it;} } |
105 } |
|
106 return tot_cost; |
|
107 } |
|
108 |
|
109 }; |
61 }; |
110 |
62 |
111 |
63 template<typename Iterator> |
112 /* ** ** Output-objektumok (Observerek (?)) ** ** */ |
64 inline |
113 |
65 SequenceOutput<Iterator> |
114 template <typename BoolMap> |
66 makeSequenceOutput(Iterator it) { |
115 class BoolMapOutput { |
67 return SequenceOutput<Iterator>(it); |
116 BoolMap &bm; |
68 } |
117 typedef typename BoolMap::KeyType KeyType; |
|
118 |
|
119 public: |
|
120 BoolMapOutput(BoolMap &_bm) : bm(_bm) {} |
|
121 |
|
122 void setTrue(KeyType const& k) { bm.set(k, true); } |
|
123 void setFalse(KeyType const& k) { bm.set(k, false); } |
|
124 }; |
|
125 |
|
126 template <typename Iterator> |
|
127 class SequenceOutput { |
|
128 Iterator ⁢ |
|
129 |
|
130 public: |
|
131 SequenceOutput(Iterator &_it) : it(_it) {} |
|
132 |
|
133 template<typename KeyType> |
|
134 void setTrue(KeyType const& k) { *it=k; ++it; } |
|
135 template<typename KeyType> |
|
136 void setFalse(KeyType const& k) {} |
|
137 }; |
|
138 |
|
139 template <typename BoolMap, typename Iterator> |
|
140 class CombinedOutput : BoolMapOutput<BoolMap>, SequenceOutput<Iterator> { |
|
141 typedef BoolMapOutput<BoolMap> BMO; |
|
142 typedef SequenceOutput<Iterator> SO; |
|
143 public: |
|
144 CombinedOutput(BoolMap &_bm, Iterator &_it) : |
|
145 BMO(_bm), SO(_it) {} |
|
146 |
|
147 template<typename KeyType> |
|
148 void setTrue(KeyType const& k) { |
|
149 BMO::setTrue(k); |
|
150 SO::setTrue(k); |
|
151 } |
|
152 template<typename KeyType> |
|
153 void setFalse(KeyType const& k) { |
|
154 BMO::setFalse(k); |
|
155 SO::setFalse(k); |
|
156 } |
|
157 }; |
|
158 |
|
159 |
69 |
160 /* ** ** InputSource -ok ** ** */ |
70 /* ** ** InputSource -ok ** ** */ |
161 |
71 |
162 template<typename Key, typename Val> |
72 template<typename Key, typename Val> |
163 class PairVec : public std::vector< std::pair<Key,Val> > { |
73 class KruskalPairVec : public std::vector< std::pair<Key,Val> > { |
164 |
74 |
165 public: |
75 public: |
166 typedef std::vector< std::pair<Key,Val> > Parent; |
76 typedef std::vector< std::pair<Key,Val> > Parent; |
167 typedef Key KeyType; |
77 typedef Key KeyType; |
168 typedef Val ValueType; |
78 typedef Val ValueType; |
169 typedef std::pair<Key,Val> PairType; |
79 typedef std::pair<Key,Val> PairType; |
170 |
80 |
171 typedef typename Parent::iterator iterator; |
81 typedef typename Parent::iterator iterator; |
172 typedef typename Parent::const_iterator const_iterator; |
82 typedef typename Parent::const_iterator const_iterator; |
173 |
83 |
174 |
|
175 private: |
84 private: |
176 |
|
177 class comparePair { |
85 class comparePair { |
178 public: |
86 public: |
179 bool operator()(PairType const& a, PairType const& b) { |
87 bool operator()(PairType const& a, PairType const& b) { |
180 return a.second < b.second; |
88 return a.second < b.second; |
181 } |
89 } |
182 }; |
90 }; |
183 |
91 |
184 public: |
92 public: |
185 |
93 |
186 // FIXME: kell ez? |
94 // FIXME: kell ez? |
187 // PairVec(Parent const& p) : Parent(p) {} |
95 // KruskalPairVec(Parent const& p) : Parent(p) {} |
188 |
96 |
189 void sort() { |
97 void sort() { |
190 std::sort(begin(), end(), comparePair()); |
98 std::sort(begin(), end(), comparePair()); |
191 } |
99 } |
192 |
100 |
193 // FIXME: nem nagyon illik ez ide... |
101 // FIXME: nem nagyon illik ez ide... |
194 template<typename Graph, typename Map> |
102 template<typename Graph, typename Map> |
195 void readGraphEdgeMap(Graph const& G, Map const& m) { |
103 KruskalPairVec(Graph const& G, Map const& m) { |
196 typedef typename Graph::EdgeIt EdgeIt; |
104 typedef typename Graph::EdgeIt EdgeIt; |
197 |
105 |
198 clear(); |
106 clear(); |
199 for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
107 FOR_EACH_LOC(EdgeIt, e, G) { |
|
108 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
200 push_back(make_pair(e, m[e])); |
109 push_back(make_pair(e, m[e])); |
201 } |
110 } |
202 |
|
203 sort(); |
111 sort(); |
204 } |
112 } |
205 |
|
206 int alma() { return 5; /* FIXME */ } |
|
207 |
113 |
208 Key const& first(const_iterator i) const { return i->first; } |
114 Key const& first(const_iterator i) const { return i->first; } |
209 Key& first(iterator i) { return i->first; } |
115 Key& first(iterator i) { return i->first; } |
210 |
116 |
211 Val const& second(const_iterator i) const { return i->second; } |
117 Val const& second(const_iterator i) const { return i->second; } |
212 Val& second(iterator i) { return i->second; } |
118 Val& second(iterator i) { return i->second; } |
213 }; |
119 }; |
214 |
120 |
|
121 |
|
122 template <typename Map> |
|
123 class KruskalMapVec : public std::vector<typename Map::KeyType> { |
|
124 public: |
|
125 |
|
126 typedef typename Map::KeyType KeyType; |
|
127 typedef typename Map::ValueType ValueType; |
|
128 |
|
129 typedef typename std::vector<KeyType> Parent; |
|
130 typedef typename Parent::iterator iterator; |
|
131 typedef typename Parent::const_iterator const_iterator; |
|
132 |
|
133 private: |
|
134 |
|
135 const Map &m; |
|
136 |
|
137 class compareKeys { |
|
138 const Map &m; |
|
139 public: |
|
140 compareKeys(Map const &_m) : m(_m) {} |
|
141 bool operator()(KeyType const& a, KeyType const& b) { |
|
142 return m[a] < m[b]; |
|
143 } |
|
144 }; |
|
145 |
|
146 public: |
|
147 |
|
148 KruskalMapVec(Map const& _m) : m(_m) {} |
|
149 |
|
150 void sort() { |
|
151 std::sort(begin(), end(), compareKeys(m)); |
|
152 } |
|
153 |
|
154 // FIXME: nem nagyon illik ez ide... |
|
155 template<typename Graph> |
|
156 KruskalMapVec(Graph const& G, Map const& _m) : m(_m) { |
|
157 typedef typename Graph::EdgeIt EdgeIt; |
|
158 |
|
159 clear(); |
|
160 FOR_EACH_LOC(EdgeIt, e, G) { |
|
161 // for (EdgeIt e=G.template first<EdgeIt>(); G.valid(e); G.next(e)) { |
|
162 push_back(e); |
|
163 } |
|
164 sort(); |
|
165 } |
|
166 |
|
167 KeyType const& first(const_iterator i) const { return *i; } |
|
168 KeyType& first(iterator i) { return *i; } |
|
169 |
|
170 ValueType const& second(const_iterator i) const { return m[*i]; } |
|
171 ValueType& second(iterator i) { return m[*i]; } |
|
172 }; |
|
173 |
215 /* ** ** Wrapper fuggvenyek ** ** */ |
174 /* ** ** Wrapper fuggvenyek ** ** */ |
216 |
175 |
|
176 |
|
177 /// \brief Wrapper to Kruskal(). |
|
178 /// Input is from an EdgeMap, output is a plain boolmap. |
217 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
179 template <typename Graph, typename EdgeCostMap, typename RetEdgeBoolMap> |
218 typename EdgeCostMap::ValueType |
180 typename EdgeCostMap::ValueType |
219 kruskal1(Graph const& G, EdgeCostMap const& edge_costs, |
181 Kruskal_EdgeCostMapIn_BoolMapOut(Graph const& G, |
220 RetEdgeBoolMap &ret_bool_map) { |
182 EdgeCostMap const& edge_costs, |
221 typedef BoolMapOutput<RetEdgeBoolMap> OutObs; |
183 RetEdgeBoolMap &ret_bool_map) { |
222 OutObs out(ret_bool_map); |
184 |
223 |
185 typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> |
224 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> |
|
225 InputVec; |
186 InputVec; |
226 InputVec iv; |
187 InputVec iv(G, edge_costs); |
227 iv.readGraphEdgeMap(G, edge_costs); |
188 |
228 |
189 return Kruskal(G, iv, ret_bool_map); |
229 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out); |
190 } |
230 return mctk.run(); |
191 |
231 } |
192 |
232 |
193 /// \brief Wrapper to Kruskal(). |
|
194 /// Input is from an EdgeMap, output is to a sequence. |
233 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
195 template <typename Graph, typename EdgeCostMap, typename RetIterator> |
234 typename EdgeCostMap::ValueType |
196 typename EdgeCostMap::ValueType |
235 kruskal2(Graph const& G, EdgeCostMap const& edge_costs, |
197 Kruskal_EdgeCostMapIn_IteratorOut(Graph const& G, |
236 RetIterator ret_iterator) { |
198 EdgeCostMap const& edge_costs, |
237 typedef SequenceOutput<RetIterator> OutObs; |
199 RetIterator ret_iterator) { |
238 OutObs out(ret_iterator); |
200 typedef SequenceOutput<RetIterator> OutMap; |
239 |
201 OutMap out(ret_iterator); |
240 typedef PairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> |
202 |
|
203 typedef KruskalPairVec<typename Graph::Edge, typename EdgeCostMap::ValueType> |
241 InputVec; |
204 InputVec; |
242 InputVec iv; |
205 InputVec iv(G, edge_costs); |
243 iv.readGraphEdgeMap(G, edge_costs); |
206 |
244 |
207 return Kruskal(G, iv, out); |
245 MinCostTreeKruskal<Graph,InputVec,OutObs> mctk(G, iv, out); |
|
246 return mctk.run(); |
|
247 } |
208 } |
248 |
209 |
249 |
210 |
250 } //namespace hugo |
211 } //namespace hugo |
251 |
212 |