1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
//
//=======================================================================
// 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 <vector>
#include <queue>
#include <functional>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/pending/indirect_cmp.hpp>
#include <boost/concept/assert.hpp>
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 <class Graph, class OutputIterator,
class Rank, class Parent, class Weight>
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<Graph>::vertex_descriptor Vertex;
typedef typename graph_traits<Graph>::edge_descriptor Edge;
BOOST_CONCEPT_ASSERT(( VertexListGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT(( EdgeListGraphConcept<Graph> ));
BOOST_CONCEPT_ASSERT(( OutputIteratorConcept<OutputIterator, Edge> ));
BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Rank, Vertex> ));
BOOST_CONCEPT_ASSERT(( ReadWritePropertyMapConcept<Parent, Vertex> ));
BOOST_CONCEPT_ASSERT(( ReadablePropertyMapConcept<Weight, Edge> ));
typedef typename property_traits<Weight>::value_type W_value;
typedef typename property_traits<Rank>::value_type R_value;
typedef typename property_traits<Parent>::value_type P_value;
BOOST_CONCEPT_ASSERT(( ComparableConcept<W_value> ));
BOOST_CONCEPT_ASSERT(( ConvertibleConcept<P_value, Vertex> ));
BOOST_CONCEPT_ASSERT(( IntegerConcept<R_value> ));
disjoint_sets<Rank, Parent> dset(rank, parent);
typename graph_traits<Graph>::vertex_iterator ui, uiend;
for (boost::tie(ui, uiend) = vertices(G); ui != uiend; ++ui)
dset.make_set(*ui);
typedef indirect_cmp<Weight, std::greater<W_value> > weight_greater;
weight_greater wl(weight);
std::priority_queue<Edge, std::vector<Edge>, weight_greater> Q(wl);
/*push all edge into Q*/
typename graph_traits<Graph>::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 <class Graph, class OutputIterator>
inline void
kruskal_minimum_spanning_tree(const Graph& g,
OutputIterator spanning_tree_edges)
{
typedef typename graph_traits<Graph>::vertices_size_type size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
typedef typename property_map<Graph, vertex_index_t>::type index_map_t;
if (num_vertices(g) == 0) return; // Nothing to do in this case
typename graph_traits<Graph>::vertices_size_type
n = num_vertices(g);
std::vector<size_type> rank_map(n);
std::vector<vertex_t> 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 <class Graph, class OutputIterator, class P, class T, class R>
inline void
kruskal_minimum_spanning_tree(const Graph& g,
OutputIterator spanning_tree_edges,
const bgl_named_params<P, T, R>& params)
{
typedef typename graph_traits<Graph>::vertices_size_type size_type;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
if (num_vertices(g) == 0) return; // Nothing to do in this case
typename graph_traits<Graph>::vertices_size_type n;
n = is_default_param(get_param(params, vertex_rank))
? num_vertices(g) : 1;
std::vector<size_type> rank_map(n);
n = is_default_param(get_param(params, vertex_predecessor))
? num_vertices(g) : 1;
std::vector<vertex_t> 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
|
