246 |
246 |
247 } |
247 } |
248 |
248 |
249 /// \ingroup spantree |
249 /// \ingroup spantree |
250 /// |
250 /// |
251 /// \brief Kruskal algorithm to find a minimum cost spanning tree of |
251 /// \brief Kruskal's algorithm for finding a minimum cost spanning tree of |
252 /// a graph. |
252 /// a graph. |
253 /// |
253 /// |
254 /// This function runs Kruskal's algorithm to find a minimum cost |
254 /// This function runs Kruskal's algorithm to find a minimum cost |
255 /// spanning tree. |
255 /// spanning tree of a graph. |
256 /// Due to some C++ hacking, it accepts various input and output types. |
256 /// Due to some C++ hacking, it accepts various input and output types. |
257 /// |
257 /// |
258 /// \param g The graph the algorithm runs on. |
258 /// \param g The graph the algorithm runs on. |
259 /// It can be either \ref concepts::Digraph "directed" or |
259 /// It can be either \ref concepts::Digraph "directed" or |
260 /// \ref concepts::Graph "undirected". |
260 /// \ref concepts::Graph "undirected". |
262 /// undirected by disregarding the direction of the arcs. |
262 /// undirected by disregarding the direction of the arcs. |
263 /// |
263 /// |
264 /// \param in This object is used to describe the arc/edge costs. |
264 /// \param in This object is used to describe the arc/edge costs. |
265 /// It can be one of the following choices. |
265 /// It can be one of the following choices. |
266 /// - An STL compatible 'Forward Container' with |
266 /// - An STL compatible 'Forward Container' with |
267 /// <tt>std::pair<GR::Arc,X></tt> or |
267 /// <tt>std::pair<GR::Arc,C></tt> or |
268 /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where |
268 /// <tt>std::pair<GR::Edge,C></tt> as its <tt>value_type</tt>, where |
269 /// \c X is the type of the costs. The pairs indicates the arcs/edges |
269 /// \c C is the type of the costs. The pairs indicates the arcs/edges |
270 /// along with the assigned cost. <em>They must be in a |
270 /// along with the assigned cost. <em>They must be in a |
271 /// cost-ascending order.</em> |
271 /// cost-ascending order.</em> |
272 /// - Any readable arc/edge map. The values of the map indicate the |
272 /// - Any readable arc/edge map. The values of the map indicate the |
273 /// arc/edge costs. |
273 /// arc/edge costs. |
274 /// |
274 /// |
275 /// \retval out Here we also have a choice. |
275 /// \retval out Here we also have a choice. |
276 /// - It can be a writable \c bool arc/edge map. After running the |
276 /// - It can be a writable arc/edge map with \c bool value type. After |
277 /// algorithm it will contain the found minimum cost spanning |
277 /// running the algorithm it will contain the found minimum cost spanning |
278 /// tree: the value of an arc/edge will be set to \c true if it belongs |
278 /// tree: the value of an arc/edge will be set to \c true if it belongs |
279 /// to the tree, otherwise it will be set to \c false. The value of |
279 /// to the tree, otherwise it will be set to \c false. The value of |
280 /// each arc/edge will be set exactly once. |
280 /// each arc/edge will be set exactly once. |
281 /// - It can also be an iteraror of an STL Container with |
281 /// - It can also be an iteraror of an STL Container with |
282 /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its |
282 /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its |
299 /// |
299 /// |
300 /// \note If the input graph is not (weakly) connected, a spanning |
300 /// \note If the input graph is not (weakly) connected, a spanning |
301 /// forest is calculated instead of a spanning tree. |
301 /// forest is calculated instead of a spanning tree. |
302 |
302 |
303 #ifdef DOXYGEN |
303 #ifdef DOXYGEN |
304 template <class Graph, class In, class Out> |
304 template <typename Graph, typename In, typename Out> |
305 Value kruskal(GR const& g, const In& in, Out& out) |
305 Value kruskal(const Graph& g, const In& in, Out& out) |
306 #else |
306 #else |
307 template <class Graph, class In, class Out> |
307 template <class Graph, class In, class Out> |
308 inline typename _kruskal_bits::KruskalValueSelector<In>::Value |
308 inline typename _kruskal_bits::KruskalValueSelector<In>::Value |
309 kruskal(const Graph& graph, const In& in, Out& out) |
309 kruskal(const Graph& graph, const In& in, Out& out) |
310 #endif |
310 #endif |
312 return _kruskal_bits::KruskalInputSelector<Graph, In, Out>:: |
312 return _kruskal_bits::KruskalInputSelector<Graph, In, Out>:: |
313 kruskal(graph, in, out); |
313 kruskal(graph, in, out); |
314 } |
314 } |
315 |
315 |
316 |
316 |
317 |
|
318 |
|
319 template <class Graph, class In, class Out> |
317 template <class Graph, class In, class Out> |
320 inline typename _kruskal_bits::KruskalValueSelector<In>::Value |
318 inline typename _kruskal_bits::KruskalValueSelector<In>::Value |
321 kruskal(const Graph& graph, const In& in, const Out& out) |
319 kruskal(const Graph& graph, const In& in, const Out& out) |
322 { |
320 { |
323 return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>:: |
321 return _kruskal_bits::KruskalInputSelector<Graph, In, const Out>:: |