1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/kruskal_min_spanning_tree.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,155 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +//
1.14 +#ifndef BOOST_GRAPH_MST_KRUSKAL_HPP
1.15 +#define BOOST_GRAPH_MST_KRUSKAL_HPP
1.16 +
1.17 +/*
1.18 + *Minimum Spanning Tree
1.19 + * Kruskal Algorithm
1.20 + *
1.21 + *Requirement:
1.22 + * undirected graph
1.23 + */
1.24 +
1.25 +#include <vector>
1.26 +#include <queue>
1.27 +#include <functional>
1.28 +
1.29 +#include <boost/property_map.hpp>
1.30 +#include <boost/graph/graph_concepts.hpp>
1.31 +#include <boost/graph/named_function_params.hpp>
1.32 +#include <boost/pending/disjoint_sets.hpp>
1.33 +#include <boost/pending/indirect_cmp.hpp>
1.34 +
1.35 +
1.36 +namespace boost {
1.37 +
1.38 + // Kruskal's algorithm for Minimum Spanning Tree
1.39 + //
1.40 + // This is a greedy algorithm to calculate the Minimum Spanning Tree
1.41 + // for an undirected graph with weighted edges. The output will be a
1.42 + // set of edges.
1.43 + //
1.44 +
1.45 + namespace detail {
1.46 +
1.47 + template <class Graph, class OutputIterator,
1.48 + class Rank, class Parent, class Weight>
1.49 + void
1.50 + kruskal_mst_impl(const Graph& G,
1.51 + OutputIterator spanning_tree_edges,
1.52 + Rank rank, Parent parent, Weight weight)
1.53 + {
1.54 + if (num_vertices(G) == 0) return; // Nothing to do in this case
1.55 + typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
1.56 + typedef typename graph_traits<Graph>::edge_descriptor Edge;
1.57 + function_requires<VertexListGraphConcept<Graph> >();
1.58 + function_requires<EdgeListGraphConcept<Graph> >();
1.59 + function_requires<OutputIteratorConcept<OutputIterator, Edge> >();
1.60 + function_requires<ReadWritePropertyMapConcept<Rank, Vertex> >();
1.61 + function_requires<ReadWritePropertyMapConcept<Parent, Vertex> >();
1.62 + function_requires<ReadablePropertyMapConcept<Weight, Edge> >();
1.63 + typedef typename property_traits<Weight>::value_type W_value;
1.64 + typedef typename property_traits<Rank>::value_type R_value;
1.65 + typedef typename property_traits<Parent>::value_type P_value;
1.66 + function_requires<ComparableConcept<W_value> >();
1.67 + function_requires<ConvertibleConcept<P_value, Vertex> >();
1.68 + function_requires<IntegerConcept<R_value> >();
1.69 +
1.70 + disjoint_sets<Rank, Parent> dset(rank, parent);
1.71 +
1.72 + typename graph_traits<Graph>::vertex_iterator ui, uiend;
1.73 + for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui)
1.74 + dset.make_set(*ui);
1.75 +
1.76 + typedef indirect_cmp<Weight, std::greater<W_value> > weight_greater;
1.77 + weight_greater wl(weight);
1.78 + std::priority_queue<Edge, std::vector<Edge>, weight_greater> Q(wl);
1.79 + /*push all edge into Q*/
1.80 + typename graph_traits<Graph>::edge_iterator ei, eiend;
1.81 + for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei)
1.82 + Q.push(*ei);
1.83 +
1.84 + while (! Q.empty()) {
1.85 + Edge e = Q.top();
1.86 + Q.pop();
1.87 + Vertex u = dset.find_set(source(e, G));
1.88 + Vertex v = dset.find_set(target(e, G));
1.89 + if ( u != v ) {
1.90 + *spanning_tree_edges++ = e;
1.91 + dset.link(u, v);
1.92 + }
1.93 + }
1.94 + }
1.95 +
1.96 + } // namespace detail
1.97 +
1.98 + // Named Parameters Variants
1.99 +
1.100 + template <class Graph, class OutputIterator>
1.101 + inline void
1.102 + kruskal_minimum_spanning_tree(const Graph& g,
1.103 + OutputIterator spanning_tree_edges)
1.104 + {
1.105 + typedef typename graph_traits<Graph>::vertices_size_type size_type;
1.106 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
1.107 + typedef typename property_map<Graph, vertex_index_t>::type index_map_t;
1.108 + if (num_vertices(g) == 0) return; // Nothing to do in this case
1.109 + typename graph_traits<Graph>::vertices_size_type
1.110 + n = num_vertices(g);
1.111 + std::vector<size_type> rank_map(n);
1.112 + std::vector<vertex_t> pred_map(n);
1.113 +
1.114 + detail::kruskal_mst_impl
1.115 + (g, spanning_tree_edges,
1.116 + make_iterator_property_map(rank_map.begin(), get(vertex_index, g), rank_map[0]),
1.117 + make_iterator_property_map(pred_map.begin(), get(vertex_index, g), pred_map[0]),
1.118 + get(edge_weight, g));
1.119 + }
1.120 +
1.121 + template <class Graph, class OutputIterator, class P, class T, class R>
1.122 + inline void
1.123 + kruskal_minimum_spanning_tree(const Graph& g,
1.124 + OutputIterator spanning_tree_edges,
1.125 + const bgl_named_params<P, T, R>& params)
1.126 + {
1.127 + typedef typename graph_traits<Graph>::vertices_size_type size_type;
1.128 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
1.129 + if (num_vertices(g) == 0) return; // Nothing to do in this case
1.130 + typename graph_traits<Graph>::vertices_size_type n;
1.131 + n = is_default_param(get_param(params, vertex_rank))
1.132 + ? num_vertices(g) : 1;
1.133 + std::vector<size_type> rank_map(n);
1.134 + n = is_default_param(get_param(params, vertex_predecessor))
1.135 + ? num_vertices(g) : 1;
1.136 + std::vector<vertex_t> pred_map(n);
1.137 +
1.138 + detail::kruskal_mst_impl
1.139 + (g, spanning_tree_edges,
1.140 + choose_param
1.141 + (get_param(params, vertex_rank),
1.142 + make_iterator_property_map
1.143 + (rank_map.begin(),
1.144 + choose_pmap(get_param(params, vertex_index), g, vertex_index), rank_map[0])),
1.145 + choose_param
1.146 + (get_param(params, vertex_predecessor),
1.147 + make_iterator_property_map
1.148 + (pred_map.begin(),
1.149 + choose_const_pmap(get_param(params, vertex_index), g, vertex_index),
1.150 + pred_map[0])),
1.151 + choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
1.152 + }
1.153 +
1.154 +} // namespace boost
1.155 +
1.156 +
1.157 +#endif // BOOST_GRAPH_MST_KRUSKAL_HPP
1.158 +