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
34namespace 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
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
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
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

source code of boost/boost/graph/kruskal_min_spanning_tree.hpp