diff -r 666f914201fb -r 2fe1408b6811 epoc32/include/stdapis/boost/graph/kruskal_min_spanning_tree.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/epoc32/include/stdapis/boost/graph/kruskal_min_spanning_tree.hpp Tue Mar 16 16:12:26 2010 +0000 @@ -0,0 +1,155 @@ +// +//======================================================================= +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame. +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +//======================================================================= +// +#ifndef BOOST_GRAPH_MST_KRUSKAL_HPP +#define BOOST_GRAPH_MST_KRUSKAL_HPP + +/* + *Minimum Spanning Tree + * Kruskal Algorithm + * + *Requirement: + * undirected graph + */ + +#include +#include +#include + +#include +#include +#include +#include +#include + + +namespace boost { + + // Kruskal's algorithm for Minimum Spanning Tree + // + // This is a greedy algorithm to calculate the Minimum Spanning Tree + // for an undirected graph with weighted edges. The output will be a + // set of edges. + // + + namespace detail { + + template + void + kruskal_mst_impl(const Graph& G, + OutputIterator spanning_tree_edges, + Rank rank, Parent parent, Weight weight) + { + if (num_vertices(G) == 0) return; // Nothing to do in this case + typedef typename graph_traits::vertex_descriptor Vertex; + typedef typename graph_traits::edge_descriptor Edge; + function_requires >(); + function_requires >(); + function_requires >(); + function_requires >(); + function_requires >(); + function_requires >(); + typedef typename property_traits::value_type W_value; + typedef typename property_traits::value_type R_value; + typedef typename property_traits::value_type P_value; + function_requires >(); + function_requires >(); + function_requires >(); + + disjoint_sets dset(rank, parent); + + typename graph_traits::vertex_iterator ui, uiend; + for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui) + dset.make_set(*ui); + + typedef indirect_cmp > weight_greater; + weight_greater wl(weight); + std::priority_queue, weight_greater> Q(wl); + /*push all edge into Q*/ + typename graph_traits::edge_iterator ei, eiend; + for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei) + Q.push(*ei); + + while (! Q.empty()) { + Edge e = Q.top(); + Q.pop(); + Vertex u = dset.find_set(source(e, G)); + Vertex v = dset.find_set(target(e, G)); + if ( u != v ) { + *spanning_tree_edges++ = e; + dset.link(u, v); + } + } + } + + } // namespace detail + + // Named Parameters Variants + + template + inline void + kruskal_minimum_spanning_tree(const Graph& g, + OutputIterator spanning_tree_edges) + { + typedef typename graph_traits::vertices_size_type size_type; + typedef typename graph_traits::vertex_descriptor vertex_t; + typedef typename property_map::type index_map_t; + if (num_vertices(g) == 0) return; // Nothing to do in this case + typename graph_traits::vertices_size_type + n = num_vertices(g); + std::vector rank_map(n); + std::vector pred_map(n); + + detail::kruskal_mst_impl + (g, spanning_tree_edges, + make_iterator_property_map(rank_map.begin(), get(vertex_index, g), rank_map[0]), + make_iterator_property_map(pred_map.begin(), get(vertex_index, g), pred_map[0]), + get(edge_weight, g)); + } + + template + inline void + kruskal_minimum_spanning_tree(const Graph& g, + OutputIterator spanning_tree_edges, + const bgl_named_params& params) + { + typedef typename graph_traits::vertices_size_type size_type; + typedef typename graph_traits::vertex_descriptor vertex_t; + if (num_vertices(g) == 0) return; // Nothing to do in this case + typename graph_traits::vertices_size_type n; + n = is_default_param(get_param(params, vertex_rank)) + ? num_vertices(g) : 1; + std::vector rank_map(n); + n = is_default_param(get_param(params, vertex_predecessor)) + ? num_vertices(g) : 1; + std::vector pred_map(n); + + detail::kruskal_mst_impl + (g, spanning_tree_edges, + choose_param + (get_param(params, vertex_rank), + make_iterator_property_map + (rank_map.begin(), + choose_pmap(get_param(params, vertex_index), g, vertex_index), rank_map[0])), + choose_param + (get_param(params, vertex_predecessor), + make_iterator_property_map + (pred_map.begin(), + choose_const_pmap(get_param(params, vertex_index), g, vertex_index), + pred_map[0])), + choose_const_pmap(get_param(params, edge_weight), g, edge_weight)); + } + +} // namespace boost + + +#endif // BOOST_GRAPH_MST_KRUSKAL_HPP +