boost/graph/kruskal_min_spanning_tree.hpp

0001 //
0002 //=======================================================================
0003 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
0004 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010 //
0011 #ifndef BOOST_GRAPH_MST_KRUSKAL_HPP
0012 #define BOOST_GRAPH_MST_KRUSKAL_HPP
0013
0014 /*
0015  *Minimum Spanning Tree
0016  *         Kruskal Algorithm
0017  *
0018  *Requirement:
0019  *      undirected graph
0020  */
0021
0022 #include <vector>
0023 #include <queue>
0024 #include <functional>
0025
0026 #include <boost/property_map/property_map.hpp>
0027 #include <boost/graph/graph_concepts.hpp>
0028 #include <boost/graph/named_function_params.hpp>
0029 #include <boost/pending/disjoint_sets.hpp>
0030 #include <boost/pending/indirect_cmp.hpp>
0031 #include <boost/concept/assert.hpp>
0032
0033 namespace boost
0034 {
0035
0036 // Kruskal's algorithm for Minimum Spanning Tree
0037 //
0038 // This is a greedy algorithm to calculate the Minimum Spanning Tree
0039 // for an undirected graph with weighted edges. The output will be a
0040 // set of edges.
0041 //
0042
0043 namespace detail
0044 {
0045
0046     template < class Graph, class OutputIterator, class Rank, class Parent,
0047         class Weight >
0048     void kruskal_mst_impl(const Graph& G, OutputIterator spanning_tree_edges,
0049         Rank rank, Parent parent, Weight weight)
0050     {
0051         if (num_vertices(G) == 0)
0052             return; // Nothing to do in this case
0053         typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0054         typedef typename graph_traits< Graph >::edge_descriptor Edge;
0055         BOOST_CONCEPT_ASSERT((VertexListGraphConcept< Graph >));
0056         BOOST_CONCEPT_ASSERT((EdgeListGraphConcept< Graph >));
0057         BOOST_CONCEPT_ASSERT((OutputIteratorConcept< OutputIterator, Edge >));
0058         BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< Rank, Vertex >));
0059         BOOST_CONCEPT_ASSERT((ReadWritePropertyMapConcept< Parent, Vertex >));
0060         BOOST_CONCEPT_ASSERT((ReadablePropertyMapConcept< Weight, Edge >));
0061         typedef typename property_traits< Weight >::value_type W_value;
0062         typedef typename property_traits< Rank >::value_type R_value;
0063         typedef typename property_traits< Parent >::value_type P_value;
0064         BOOST_CONCEPT_ASSERT((ComparableConcept< W_value >));
0065         BOOST_CONCEPT_ASSERT((ConvertibleConcept< P_value, Vertex >));
0066         BOOST_CONCEPT_ASSERT((IntegerConcept< R_value >));
0067
0068         disjoint_sets< Rank, Parent > dset(rank, parent);
0069
0070         typename graph_traits< Graph >::vertex_iterator ui, uiend;
0071         for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui)
0072             dset.make_set(*ui);
0073
0074         typedef indirect_cmp< Weight, std::greater< W_value > > weight_greater;
0075         weight_greater wl(weight);
0076         std::priority_queue< Edge, std::vector< Edge >, weight_greater > Q(wl);
0077         /*push all edge into Q*/
0078         typename graph_traits< Graph >::edge_iterator ei, eiend;
0079         for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei)
0080             Q.push(*ei);
0081
0082         while (!Q.empty())
0083         {
0084             Edge e = Q.top();
0085             Q.pop();
0086             Vertex u = dset.find_set(source(e, G));
0087             Vertex v = dset.find_set(target(e, G));
0088             if (u != v)
0089             {
0090                 *spanning_tree_edges++ = e;
0091                 dset.link(u, v);
0092             }
0093         }
0094     }
0095
0096 } // namespace detail
0097
0098 // Named Parameters Variants
0099
0100 template < class Graph, class OutputIterator >
0101 inline void kruskal_minimum_spanning_tree(
0102     const Graph& g, OutputIterator spanning_tree_edges)
0103 {
0104     typedef typename graph_traits< Graph >::vertices_size_type size_type;
0105     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0106     if (num_vertices(g) == 0)
0107         return; // Nothing to do in this case
0108     typename graph_traits< Graph >::vertices_size_type n = num_vertices(g);
0109     std::vector< size_type > rank_map(n);
0110     std::vector< vertex_t > pred_map(n);
0111
0112     detail::kruskal_mst_impl(g, spanning_tree_edges,
0113         make_iterator_property_map(
0114             rank_map.begin(), get(vertex_index, g), rank_map[0]),
0115         make_iterator_property_map(
0116             pred_map.begin(), get(vertex_index, g), pred_map[0]),
0117         get(edge_weight, g));
0118 }
0119
0120 template < class Graph, class OutputIterator, class P, class T, class R >
0121 inline void kruskal_minimum_spanning_tree(const Graph& g,
0122     OutputIterator spanning_tree_edges,
0123     const bgl_named_params< P, T, R >& params)
0124 {
0125     typedef typename graph_traits< Graph >::vertices_size_type size_type;
0126     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
0127     if (num_vertices(g) == 0)
0128         return; // Nothing to do in this case
0129     typename graph_traits< Graph >::vertices_size_type n;
0130     n = is_default_param(get_param(params, vertex_rank)) ? num_vertices(g) : 1;
0131     std::vector< size_type > rank_map(n);
0132     n = is_default_param(get_param(params, vertex_predecessor))
0133         ? num_vertices(g)
0134         : 1;
0135     std::vector< vertex_t > pred_map(n);
0136
0137     detail::kruskal_mst_impl(g, spanning_tree_edges,
0138         choose_param(get_param(params, vertex_rank),
0139             make_iterator_property_map(rank_map.begin(),
0140                 choose_pmap(get_param(params, vertex_index), g, vertex_index),
0141                 rank_map[0])),
0142         choose_param(get_param(params, vertex_predecessor),
0143             make_iterator_property_map(pred_map.begin(),
0144                 choose_const_pmap(
0145                     get_param(params, vertex_index), g, vertex_index),
0146                 pred_map[0])),
0147         choose_const_pmap(get_param(params, edge_weight), g, edge_weight));
0148 }
0149
0150 } // namespace boost
0151
0152 #endif // BOOST_GRAPH_MST_KRUSKAL_HPP