49 /// This function runs Kruskal's algorithm to find a minimum cost tree. |
49 /// This function runs Kruskal's algorithm to find a minimum cost tree. |
50 /// Due to hard C++ hacking, it accepts various input and output types. |
50 /// Due to hard C++ hacking, it accepts various input and output types. |
51 /// |
51 /// |
52 /// \param g The graph the algorithm runs on. |
52 /// \param g The graph the algorithm runs on. |
53 /// It can be either \ref concept::StaticGraph "directed" or |
53 /// It can be either \ref concept::StaticGraph "directed" or |
54 /// \ref concept::UndirGraph "undirected". |
54 /// \ref concept::UGraph "undirected". |
55 /// If the graph is directed, the algorithm consider it to be |
55 /// If the graph is directed, the algorithm consider it to be |
56 /// undirected by disregarding the direction of the edges. |
56 /// undirected by disregarding the direction of the edges. |
57 /// |
57 /// |
58 /// \param in This object is used to describe the edge costs. It can be one |
58 /// \param in This object is used to describe the edge costs. It can be one |
59 /// of the following choices. |
59 /// of the following choices. |
87 /// \endcode |
87 /// \endcode |
88 /// |
88 /// |
89 /// \return The cost of the found tree. |
89 /// \return The cost of the found tree. |
90 /// |
90 /// |
91 /// \warning If kruskal is run on an |
91 /// \warning If kruskal is run on an |
92 /// \ref lemon::concept::UndirGraph "undirected graph", be sure that the |
92 /// \ref lemon::concept::UGraph "undirected graph", be sure that the |
93 /// map storing the tree is also undirected |
93 /// map storing the tree is also undirected |
94 /// (e.g. UndirListGraph::UndirEdgeMap<bool>, otherwise the values of the |
94 /// (e.g. ListUGraph::UEdgeMap<bool>, otherwise the values of the |
95 /// half of the edges will not be set. |
95 /// half of the edges will not be set. |
96 /// |
96 /// |
97 /// \todo Discuss the case of undirected graphs: In this case the algorithm |
97 /// \todo Discuss the case of undirected graphs: In this case the algorithm |
98 /// also require <tt>Edge</tt>s instead of <tt>UndirEdge</tt>s, as some |
98 /// also require <tt>Edge</tt>s instead of <tt>UEdge</tt>s, as some |
99 /// people would expect. So, one should be careful not to add both of the |
99 /// people would expect. So, one should be careful not to add both of the |
100 /// <tt>Edge</tt>s belonging to a certain <tt>UndirEdge</tt>. |
100 /// <tt>Edge</tt>s belonging to a certain <tt>UEdge</tt>. |
101 /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.) |
101 /// (\ref kruskal() and \ref KruskalMapInput are kind enough to do so.) |
102 |
102 |
103 #ifdef DOXYGEN |
103 #ifdef DOXYGEN |
104 template <class GR, class IN, class OUT> |
104 template <class GR, class IN, class OUT> |
105 typename IN::value_type::second_type |
105 typename IN::value_type::second_type |
223 return a.second < b.second; |
223 return a.second < b.second; |
224 } |
224 } |
225 }; |
225 }; |
226 |
226 |
227 template<class _GR> |
227 template<class _GR> |
228 typename enable_if<typename _GR::UndirTag,void>::type |
228 typename enable_if<typename _GR::UTag,void>::type |
229 fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) |
229 fillWithEdges(const _GR& g, const Map& m,dummy<0> = 0) |
230 { |
230 { |
231 for(typename GR::UndirEdgeIt e(g);e!=INVALID;++e) |
231 for(typename GR::UEdgeIt e(g);e!=INVALID;++e) |
232 push_back(value_type(g.direct(e, true), m[e])); |
232 push_back(value_type(g.direct(e, true), m[e])); |
233 } |
233 } |
234 |
234 |
235 template<class _GR> |
235 template<class _GR> |
236 typename disable_if<typename _GR::UndirTag,void>::type |
236 typename disable_if<typename _GR::UTag,void>::type |
237 fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) |
237 fillWithEdges(const _GR& g, const Map& m,dummy<1> = 1) |
238 { |
238 { |
239 for(typename GR::EdgeIt e(g);e!=INVALID;++e) |
239 for(typename GR::EdgeIt e(g);e!=INVALID;++e) |
240 push_back(value_type(e, m[e])); |
240 push_back(value_type(e, m[e])); |
241 } |
241 } |