1 // 2 //======================================================================= 3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame. 4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek 5 // 6 // Distributed under the Boost Software License, Version 1.0. (See 7 // accompanying file LICENSE_1_0.txt or copy at 8 // http://www.boost.org/LICENSE_1_0.txt) 9 //======================================================================= 10 // 11 #ifndef BOOST_GRAPH_MST_KRUSKAL_HPP 12 #define BOOST_GRAPH_MST_KRUSKAL_HPP 13 14 /* 15 *Minimum Spanning Tree 16 * Kruskal Algorithm 17 * 18 *Requirement: 19 * undirected graph 20 */ 21 22 #include <vector> 23 #include <queue> 24 #include <functional> 25 26 #include <boost/property_map/property_map.hpp> 27 #include <boost/graph/graph_concepts.hpp> 28 #include <boost/graph/named_function_params.hpp> 29 #include <boost/pending/disjoint_sets.hpp> 30 #include <boost/pending/indirect_cmp.hpp> 31 #include <boost/concept/assert.hpp> 32 33 34 namespace boost { 35 36 // Kruskal's algorithm for Minimum Spanning Tree 37 // 38 // This is a greedy algorithm to calculate the Minimum Spanning Tree 39 // for an undirected graph with weighted edges. The output will be a 40 // set of edges. 41 // 42 43 namespace detail { 44 45 template <class Graph, class OutputIterator, 46 class Rank, class Parent, class Weight> 47 void kruskal_mst_impl(const Graph & G,OutputIterator spanning_tree_edges,Rank rank,Parent parent,Weight weight)48 kruskal_mst_impl(const Graph& G, 49 OutputIterator spanning_tree_edges, 50 Rank rank, Parent parent, Weight weight) 51 { 52 if (num_vertices(G) == 0) return; // Nothing to do in this case 53 typedef typename graph_traits<Graph>::vertex_descriptor Vertex; 54 typedef typename graph_traits<Graph>::edge_descriptor Edge; 55 BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> )); 56 BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> )); 57 BOOST_CONCEPT_ASSERT(( OutputIteratorConcept<OutputIterator, Edge> )); 58 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Rank, Vertex> )); 59 BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Parent, Vertex> )); 60 BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<Weight, Edge> )); 61 typedef typename property_traits<Weight>::value_type W_value; 62 typedef typename property_traits<Rank>::value_type R_value; 63 typedef typename property_traits<Parent>::value_type P_value; 64 BOOST_CONCEPT_ASSERT(( ComparableConcept<W_value> )); 65 BOOST_CONCEPT_ASSERT(( ConvertibleConcept<P_value, Vertex> )); 66 BOOST_CONCEPT_ASSERT(( IntegerConcept<R_value> )); 67 68 disjoint_sets<Rank, Parent> dset(rank, parent); 69 70 typename graph_traits<Graph>::vertex_iterator ui, uiend; 71 for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui) 72 dset.make_set(*ui); 73 74 typedef indirect_cmp<Weight, std::greater<W_value> > weight_greater; 75 weight_greater wl(weight); 76 std::priority_queue<Edge, std::vector<Edge>, weight_greater> Q(wl); 77 /*push all edge into Q*/ 78 typename graph_traits<Graph>::edge_iterator ei, eiend; 79 for (boost::tie(ei, eiend) = edges(G); ei != eiend; ++ei) 80 Q.push(*ei); 81 82 while (! Q.empty()) { 83 Edge e = Q.top(); 84 Q.pop(); 85 Vertex u = dset.find_set(source(e, G)); 86 Vertex v = dset.find_set(target(e, G)); 87 if ( u != v ) { 88 *spanning_tree_edges++ = e; 89 dset.link(u, v); 90 } 91 } 92 } 93 94 } // namespace detail 95 96 // Named Parameters Variants 97 98 template <class Graph, class OutputIterator> 99 inline void kruskal_minimum_spanning_tree(const Graph & g,OutputIterator spanning_tree_edges)100 kruskal_minimum_spanning_tree(const Graph& g, 101 OutputIterator spanning_tree_edges) 102 { 103 typedef typename graph_traits<Graph>::vertices_size_type size_type; 104 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; 105 if (num_vertices(g) == 0) return; // Nothing to do in this case 106 typename graph_traits<Graph>::vertices_size_type 107 n = num_vertices(g); 108 std::vector<size_type> rank_map(n); 109 std::vector<vertex_t> pred_map(n); 110 111 detail::kruskal_mst_impl 112 (g, spanning_tree_edges, 113 make_iterator_property_map(rank_map.begin(), get(vertex_index, g), rank_map[0]), 114 make_iterator_property_map(pred_map.begin(), get(vertex_index, g), pred_map[0]), 115 get(edge_weight, g)); 116 } 117 118 template <class Graph, class OutputIterator, class P, class T, class R> 119 inline void kruskal_minimum_spanning_tree(const Graph & g,OutputIterator spanning_tree_edges,const bgl_named_params<P,T,R> & params)120 kruskal_minimum_spanning_tree(const Graph& g, 121 OutputIterator spanning_tree_edges, 122 const bgl_named_params<P, T, R>& params) 123 { 124 typedef typename graph_traits<Graph>::vertices_size_type size_type; 125 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; 126 if (num_vertices(g) == 0) return; // Nothing to do in this case 127 typename graph_traits<Graph>::vertices_size_type n; 128 n = is_default_param(get_param(params, vertex_rank)) 129 ? num_vertices(g) : 1; 130 std::vector<size_type> rank_map(n); 131 n = is_default_param(get_param(params, vertex_predecessor)) 132 ? num_vertices(g) : 1; 133 std::vector<vertex_t> pred_map(n); 134 135 detail::kruskal_mst_impl 136 (g, spanning_tree_edges, 137 choose_param 138 (get_param(params, vertex_rank), 139 make_iterator_property_map 140 (rank_map.begin(), 141 choose_pmap(get_param(params, vertex_index), g, vertex_index), rank_map[0])), 142 choose_param 143 (get_param(params, vertex_predecessor), 144 make_iterator_property_map 145 (pred_map.begin(), 146 choose_const_pmap(get_param(params, vertex_index), g, vertex_index), 147 pred_map[0])), 148 choose_const_pmap(get_param(params, edge_weight), g, edge_weight)); 149 } 150 151 } // namespace boost 152 153 154 #endif // BOOST_GRAPH_MST_KRUSKAL_HPP 155 156