equal
deleted
inserted
replaced
17 #ifndef LEMON_KRUSKAL_H |
17 #ifndef LEMON_KRUSKAL_H |
18 #define LEMON_KRUSKAL_H |
18 #define LEMON_KRUSKAL_H |
19 |
19 |
20 #include <algorithm> |
20 #include <algorithm> |
21 #include <lemon/unionfind.h> |
21 #include <lemon/unionfind.h> |
|
22 #include<lemon/utility.h> |
22 |
23 |
23 /** |
24 /** |
24 @defgroup spantree Minimum Cost Spanning Tree Algorithms |
25 @defgroup spantree Minimum Cost Spanning Tree Algorithms |
25 @ingroup galgs |
26 @ingroup galgs |
26 \brief This group containes the algorithms for finding a minimum cost spanning |
27 \brief This group containes the algorithms for finding a minimum cost spanning |
64 /// this will contain the found minimum cost spanning tree: the value of an |
65 /// this will contain the found minimum cost spanning tree: the value of an |
65 /// edge will be set to \c true if it belongs to the tree, otherwise it will |
66 /// edge will be set to \c true if it belongs to the tree, otherwise it will |
66 /// be set to \c false. The value of each edge will be set exactly once. |
67 /// be set to \c false. The value of each edge will be set exactly once. |
67 /// |
68 /// |
68 /// \return The cost of the found tree. |
69 /// \return The cost of the found tree. |
|
70 /// |
|
71 /// \todo Discuss the case of undirected graphs: In this case the algorithm |
|
72 /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some |
|
73 /// people would expect. So, one should be careful not to add both of the |
|
74 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>. |
|
75 /// (\ref kruskalEdgeMap() and \ref KruskalMapInput are kind enough to do so.) |
69 |
76 |
70 template <class GR, class IN, class OUT> |
77 template <class GR, class IN, class OUT> |
71 typename IN::value_type::second_type |
78 typename IN::value_type::second_type |
72 kruskal(GR const& G, IN const& in, |
79 kruskal(GR const& G, IN const& in, |
73 OUT& out) |
80 OUT& out) |
164 const value_type& b) { |
171 const value_type& b) { |
165 return a.second < b.second; |
172 return a.second < b.second; |
166 } |
173 } |
167 }; |
174 }; |
168 |
175 |
|
176 template<class _GR> |
|
177 typename enable_if<typename _GR::UndirTag,void>::type |
|
178 fillWithEdges(const _GR& G, const Map& m,dummy<0> = 0) |
|
179 { |
|
180 for(typename GR::UndirEdgeIt e(G);e!=INVALID;++e) |
|
181 push_back(value_type(typename GR::Edge(e,true), m[e])); |
|
182 } |
|
183 |
|
184 template<class _GR> |
|
185 typename disable_if<typename _GR::UndirTag,void>::type |
|
186 fillWithEdges(const _GR& G, const Map& m,dummy<1> = 1) |
|
187 { |
|
188 for(typename GR::EdgeIt e(G);e!=INVALID;++e) |
|
189 push_back(value_type(e, m[e])); |
|
190 } |
|
191 |
|
192 |
169 public: |
193 public: |
170 |
194 |
171 void sort() { |
195 void sort() { |
172 std::sort(this->begin(), this->end(), comparePair()); |
196 std::sort(this->begin(), this->end(), comparePair()); |
173 } |
197 } |
174 |
198 |
175 KruskalMapInput(GR const& G, Map const& m) { |
199 KruskalMapInput(GR const& G, Map const& m) { |
176 typedef typename GR::EdgeIt EdgeIt; |
200 fillWithEdges(G,m); |
177 |
|
178 for(EdgeIt e(G);e!=INVALID;++e) push_back(value_type(e, m[e])); |
|
179 sort(); |
201 sort(); |
180 } |
202 } |
181 }; |
203 }; |
182 |
204 |
183 /// Creates a KruskalMapInput object for \ref kruskal() |
205 /// Creates a KruskalMapInput object for \ref kruskal() |